Can a man build a staircase with tetrominoes? Maybe he can, maybe he cannot, or maybe he would be confused by what the question means. Let me make this clear. The world in which we are living is submerged in chaos -- it has no rules, no regular patterns, and even if you insist it does, you must admit that clearly it is not tidy at all. But the world of Tetris is different. The whole world can be constructed by only 7 kinds of tetrominoes. You get a piece of tetromino, rotate it, move it, then place it somewhere, and if you luckily filled an entire row,"whew!", that row is eliminated – and this is the only rule applied to this world. It is rather easy to construct a staircase in such a regular, tidy world -- well, maybe it is.
If you still don't understand what you should do (probably you don't), follow the instructions below carefully -- we are going to examine this problem seriously from now on.
Consider a staircase we have been talking about with length N as a staircase-shaped grid with N rows and N columns, and for the i-th row, it has i grids in it. To clarify this, a staircase with length 4 would look like this:
Tetrominoes refers to a set of blocks originated from the game Tetris, which includes 7 kinds of blocks and each of them occupies exactly 4 grids. Figure below shows the shapes of these tetrominoes.
Given an integer N, you should cover the staircase-shaped grid (or staircase for short) with tetrominoes. For each piece of tetromino you use, you can rotate it by 0, 90, 180 or 270 degrees, then place it somewhere aligned with grid lines in the staircase. The tetrominoes you place should not overlap with each other, or outreach the staircase. Every grid in the staircase should be covered by a tetromino. The tetrominoes you place will never be eliminated, since this is not a real Tetris game.
You can use any amount of each kind of tetrominoes you want to build the staircase. However, there is one restriction: you should use as many kinds of tetrominoes as possible. That is, if there exists a solution that uses up all 7 kinds of tetrominoes, your answer which uses only 6 kinds of tetrominoes will be not acceptable.
Since there might be multiple solutions for a given N, you may output any one of them. To output your solution, you should assign a block number (ranging from 0 to 231-1) to each grid in the staircase to specify which tetromino covers this grid. Two consecutive grids (sharing a common edge) with the same block number will be considered as covered by the same tetromino. The block numbers do not need to be unique among all the tetrominoes, as long as any two tetrominoes with the same block number are not adjacent (sharing at least one common edge).
2 15 2
1 1 1 2 1 3 2 3 3 1 2 3 1 1 1 2 4 4 2 2 1 1 4 4 2 1 1 1 1 1 1 2 3 3 3 3 2 2 2 1 1 2 2 2 4 2 1 3 2 1 2 3 3 4 4 1 1 3 2 1 4 3 3 4 3 3 1 3 3 2 3 4 4 1 1 1 3 3 4 4 4 2 3 3 4 1 3 3 2 2 1 3 4 1 1 3 2 2 2 3 3 2 1 1 4 3 3 3 1 1 2 1 1 1 1 2 1 4 4 4 -1