Монокарп играет в компьютерную игру Moonbound. Цель игры — спасти галактику от вторжения неизвестной силы при помощи мощного артефакта под названием «Манипулятор материи». Впрочем, Монокарп не занимается спасением галактики — сейчас он просто строит дом для своего персонажа.
Сейчас Монокарпу осталось построить одну из стен своего дома. Весь мир в Moonbound состоит из квадратных блоков, и стена, которую собирается строить Монокарп, — не исключение: она будет квадратной, состоять из $$$n$$$ горизонтальных рядов, в каждом из которых будет по $$$n$$$ блоков (гарантируется, что $$$n$$$ четно). Обозначим позицию, в которой будет находиться $$$j$$$-й блок в $$$i$$$-м ряду, как ($$$i$$$, $$$j$$$).
Монокарп решил построить стену из двух видов кирпича — каменного и песчаного. По мнению Монокарпа, стена будет красивой, если каменные и песчаные блоки будут располагаться в шахматном порядке: левый верхний блок должен быть каменным, блок справа от него — песчаным, блок справа от этого — каменным, и так далее; первый блок во втором ряду — песчаным, второй блок во втором ряду — каменным, и так далее. Формально, если $$$i + j$$$ делится на $$$2$$$, то в позиции ($$$i$$$, $$$j$$$) должен находиться каменный блок, иначе — песчаный.
Манипулятор материи позволяет ставить блоки в двух режимах, но у обоих этих режимов есть особые требования к позициям, в которые ставятся блоки. Назовем позицию ($$$i$$$, $$$j$$$), в которой еще не стоит блок, доступной, если она либо на границе (то есть $$$i = 1$$$, $$$i = n$$$, $$$j = 1$$$ или $$$j = n$$$), либо является соседней по стороне с какой-то позицией, в которой уже стоит блок.
Ставить блоки при помощи манипулятора материи можно двумя способами — либо выбрать какую-то доступную позицию и поставить в нее блок выбранного типа, либо выбрать квадрат $$$2 \times 2$$$, в котором есть хотя бы одна доступная позиция, и заполнить все пустые позиции в этом квадрате блоками одного и того же выбранного типа.
Монокарп хочет построить всю стену за не более чем $$$\frac{3n^2}{4}$$$ применений манипулятора. Если он поставит блок в какую-то позицию, в которой должен находиться блок другого типа, то ему придется разрушать секцию стены, а это займет очень много времени — поэтому он никогда не будет выполнять действие, которое ставит блок неправильного типа на какую-то позицию. Помогите ему составить план действий!
В единственной строке задано одно целое четное число $$$n$$$ ($$$2 \le n \le 50$$$) — количество рядов в стене (а также количество блоков в каждом ряду).
В первой строке выведите $$$k$$$ ($$$1 \le k \le \frac{3n^2}{4}$$$) — количество применений манипулятора материи, необходимых для построения стены. После этого выведите план действий Монокарпа в следующих $$$k$$$ строках, по одному действию в строке. Каждое действие должно быть описано в формате $$$t$$$ $$$x$$$ $$$y$$$ $$$b$$$:
- $$$t$$$ — тип действия: $$$1$$$, если заполняется одна позиция для блока, и $$$2$$$, если заполняется квадрат $$$2 \times 2$$$;
- $$$x$$$ $$$y$$$ — заполняемая позиция. Если действие типа $$$1$$$, то заполняется позиция ($$$x$$$, $$$y$$$) — и она должна быть доступной; если действие типа $$$2$$$, то заполняются позиции ($$$x$$$, $$$y$$$), ($$$x$$$, $$$y + 1$$$), ($$$x + 1$$$, $$$y$$$) и ($$$x + 1$$$, $$$y + 1$$$) — и хотя бы одна из них должна быть доступной;
- $$$b$$$ — тип блока, которым заполняются свободные позиции ($$$1$$$, если это каменный блок, и $$$2$$$, если песчаный).
Ни одно действие в плане не должно приводить к тому, что в какую-то позицию попадает блок того типа, который там не должен находиться. При заполнении квадрата $$$2 \times 2$$$ ни одна принадлежащая ему позиция не должна выходить за пределы (то есть если $$$t = 2$$$, то $$$1 \le x, y \le n - 1$$$).
Если существует несколько возможных планов с $$$k \le \frac{3n^2}{4}$$$, выведите любой из них. Помните, что блоки разных типов в построенной стене должны чередоваться в шахматном порядке, а блок в позиции ($$$1$$$, $$$1$$$) должен быть каменным.
2
3 1 1 1 1 1 2 2 1 2 1 1 2
Последовательность действий в первом примере (белый цвет обозначает пустую позицию, темно-серый — каменный блок, светло-серый — песчаный блок):
