Background

You are right, but in [NOIP2022] Meow Meow, Little P did not output the number of operations and achieved a great score of $0$ points.

Problem Description

Little P has fallen in love with a game called "Woof Woof". This game has a deck of cards and a pyramid-shaped board, and there are $3$ levels in total. Specifically, as shown in the figure, the side length of the board is $n$. The $i$-th row has $i$ cells, so there are $\dfrac{n(n+1)}{2}$ cells in total.

In the deck, there are infinitely many copies of number cards $1, 2 \dots n$. You need to place these number cards into the corresponding cells on the board, with exactly one number card in each cell, and you must ensure that the first element of each row is distinct from all others.

Little P found that the difficulty of the game increases with the level number:

• In level $0$, you do not need to satisfy any other conditions.
• In level $1$, you need to ensure that any two adjacent numbers in the same row are different, and that all unordered pairs formed by any two adjacent numbers in any row are pairwise distinct.
• In level $2$, you need to satisfy the constraints of level $1$, and additionally all numbers in the same row must be pairwise distinct.

For example, the following is a placement that can pass level $2$ when $n = 5$:

Now, given $n$ and the level number, please help Little P find a valid placement to pass this level. It can be proven that under the game constraints, there always exists a way to pass.

Input Format

Read input from standard input.

There is only one line containing two integers $n, t$, where $t$ denotes the level number.

Output Format

Write output to standard output.

Output $n$ lines. The $i$-th line contains $i$ positive integers (separated by spaces), representing all numbers in the $i$-th row of the board from left to right.

If there are multiple valid solutions, you may output any one of them.

2 1

1
2 1

5 2

1
2 3
4 2 5
3 5 1 4
5 4 3 1 2

Hint

[Explanation and Hints]

A checker (checker.cpp) is provided for this problem. After compiling checker.cpp into an executable file checker, you can run checker woof.in woof.out woof.ans in the current directory to verify whether your output meets the requirements. Here, woof.in can be replaced by the corresponding input file name, woof.out can be replaced by the corresponding output file name (i.e., your constructed result), and woof.ans can be any file.

Explanation of the returned results:

• The numbers are not in the valid range.: Your output does not satisfy that every number is in the range $1 \sim n$.
• The first column does not satisfice.: Your output does not satisfy that the first number of each row is pairwise distinct.
• The pairs of numbers are not distinct.: Your output does not satisfy that all unordered pairs formed by any two adjacent numbers in any row are pairwise distinct.
• The adjacent numbers are not distinct.: The current level number is $\ge 1$, and your output does not satisfy the conditions of level $1$.
• The numbers in a row are not distinct.: The current level number is $\ge 2$, and your output does not satisfy the conditions of level $2$.
• Well done.: Your construction satisfies the requirements.

[Constraints]

• Special Property A: It is guaranteed that $n + 1$ or $n + 2$ is a prime number.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 4000$ and $t \in \{0, 1, 2\}$.

Translated by ChatGPT 5