406308: GYM102348 K Moonbound

Monocarp plays a computer game called Moonbound. The main goal of this game is to save the galaxy from the invasion of alien forces using the Matter Manipulator — a very powerful artifact. Though Monocarp is not busy saving the galaxy — in fact, now he is simply building a house for his character.

Now Monocarp has to build a wall for the house. The whole world of Moonbound consists of square blocks, and the wall which Monocarp wants to build is not an exception. The wall will have the form of a square, it will consist of $$$n$$$ horizontal rows, each containing $$$n$$$ blocks ($$$n$$$ is even). Let's denote the position where the $$$j$$$-th block in the $$$i$$$-th row will be placed as ($$$i$$$, $$$j$$$).

Monocarp wants to build a wall of two types of blocks: stone bricks and sand bricks. Monocarp thinks that the wall will be beautiful if the blocks of different types are placed in chequered fashion: the left upper block should be a stone brick, the block to the right of it should be a sand brick, the block to the right of that block should be stone, and so on; the first block in the second row should be sand, the second block in the second row — stone, and so on. Formally, if $$$i + j$$$ is divisible by $$$2$$$, then the position ($$$i$$$, $$$j$$$) should contain a stone block, otherwise it should contain a sand block.

The Matter Manipulator can place blocks in two different modes, but both modes have special requirements for the positions where the blocks will be placed. Let's call an empty (not containing any block) position ($$$i$$$, $$$j$$$) free, if either it is on the border ($$$i = 1$$$, $$$i = n$$$, $$$j = 1$$$ or $$$j = n$$$), or it shares a side with at least one position that already contains a block.

The blocks can be placed in two modes — either choose any free position and place there a block of chosen type, or choose a square $$$2 \times 2$$$ which contains at least one free position, and fill all empty positions in this square with blocks of the same chosen type.

Monocarp wants to build the wall using the Matter Manipulator no more than $$$\frac{3n^2}{4}$$$ times. If he places a block in a position where a block of other type should be, then he will have to destroy a section of the wall, and it will take a lot of time — so Monocarp won't perform any action which places a block of wrong type in any position. Help him to come up with a plan of actions!

The only line contains one even integer $$$n$$$ ($$$2 \le n \le 50$$$) — the number of rows in the wall (and the number of blocks in each row).

In the first line print $$$k$$$ ($$$1 \le k \le \frac{3n^2}{4}$$$) — the number of uses of the Matter Manipulator required to build the wall. Then print the plan of actions in next $$$k$$$ lines, one action per line. Each action should be described with four integers $$$t$$$ $$$x$$$ $$$y$$$ $$$b$$$:

1. $$$t$$$ is the type of the action; it is $$$1$$$ if only one position is filled, or $$$2$$$ if a square $$$2 \times 2$$$ is filled;
2. $$$x$$$ $$$y$$$ are the coordinates of the position Monocarp fills. If the action has type $$$1$$$, then ($$$x$$$, $$$y$$$) is filled — and it should be free before the action; if the action has type $$$2$$$, then positions ($$$x$$$, $$$y$$$), ($$$x$$$, $$$y + 1$$$), ($$$x + 1$$$, $$$y$$$) and ($$$x + 1$$$, $$$y + 1$$$) are filled — at at least one of them should be free;
3. $$$b$$$ is the type of the block that all empty positions are filled with ($$$1$$$ if it is a stone brick, or $$$2$$$ if it is a sand brick).

No action should lead to the situation where some position contains a block that doesn't belong there. When a square $$$2 \times 2$$$ is being filled, no position belonging to it should be outside the wall (so if $$$t = 2$$$, then $$$1 \le x, y \le n - 1$$$).

If there are multiple possible plans with $$$k \le \frac{3n^2}{4}$$$, print any of them. Note that the blocks of different types should be placed in chequered fashion, and the position ($$$1$$$, $$$1$$$) should contain a stone block.

2

3
1 1 1 1
1 2 2 1
2 1 1 2

The sequence of actions in the first example (white color corresponds to an empty position, dark grey — to stone block, light gray — to sand block):