Это интерактивная задача

Омкар только что наткнулся на утку! Утка ходит по сетке с $$$n$$$ строками и $$$n$$$ столбцами ($$$2 \leq n \leq 25$$$), так что сетка содержит в общей сложности $$$n^2$$$ ячеек. Обозначим как $$$(x, y)$$$ ячейку в $$$x$$$-й строке сверху и $$$y$$$-м столбце слева. Прямо сейчас утка находится в ячейке $$$(1, 1)$$$ (ячейка в левом верхнем углу) и хочет дойти до ячейки $$$(n, n)$$$ (ячейка в правом нижнем углу), перемещаясь каждую секунду либо вниз на $$$1$$$ ячейку, либо вправо на $$$1$$$ ячейку.

Так как Омкар считает, что утки это весело, он хочет поиграть с вами в игру, основанную на движении утки. Сначала для каждой ячейки $$$(x, y)$$$ в сетке вы скажете Омкару целое неотрицательное $$$a_{x,y}$$$, не превышающее $$$10^{16}$$$, а затем Омкар положит $$$a_{x,y}$$$ неинтересных задач в ячейку $$$(x, y)$$$. После этого утка начнет свое путешествие с $$$(1, 1)$$$ до $$$(n, n)$$$. Для каждой ячейки $$$(x, y)$$$, которую утка посещает во время своего путешествия (включая ячейки $$$(1, 1)$$$ и $$$(n, n)$$$), утка съест $$$a_{x,y}$$$ неинтересных задач в этой ячейке. После того как утка завершит свое путешествие, Омкар измерит ее массу, чтобы определить общее количество $$$k$$$ неинтересных задач, которые утка съела во время своего путешествия, а затем скажет вам $$$k$$$.

Ваша задача, зная $$$k$$$, состоит в том, чтобы точно воспроизвести утиный путь, т.е. точно сказать Омкару, какие клетки утка посетила во время своего путешествия. Чтобы быть уверенным в вашем мастерстве в этой игре, Омкар заставит утку выполнить $$$q$$$ различных путешествий ($$$1 \leq q \leq 10^3$$$). Обратите внимание, что все путешествия независимы: в начале каждого путешествия ячейка $$$(x, y)$$$ все так же будет содержать $$$a_{x,y}$$$ неинтересных задач.

Взаимодействие начнется со строки, содержащей одно целое $$$n$$$ ($$$2 \leq n \leq 25$$$) — количество строк и столбцов в сетке. Считайте его.

Затем ваша программа должна вывести $$$n$$$ строк. $$$x$$$-я строка должна содержать $$$n$$$ целых чисел $$$a_{x,1}, a_{x,2}, \dotsc, a_{x,n}$$$, удовлетворяющих $$$0 \leq a_{x,y} \leq 10^{16}$$$, где $$$a_{x,y}$$$  — это количество неинтересных задач, которые Омкар должен поместить в ячейку $$$(x, y)$$$.

После этого вы получите одно целое $$$q$$$, количество путешествий, которые совершит утка. Затем последуют $$$q$$$ запросов; каждый запрос будет состоять из одной строки, содержащей целое число $$$k$$$  — количество неинтересных задач, которые утка съела в этой поездке. После каждого запроса, когда вы определили, что утка посетила ячейки $$$(x_1, y_1), (x_2, y_2), \dotsc, (x_{2n - 1}, y_{2n - 1})$$$ в таком порядке (всегда должно выполняться $$$(x_1, y_1) = (1, 1)$$$ и $$$(x_{2n - 1}, y_{2n - 1}) = (n, n)$$$), нужно вывести $$$2n - 1$$$ строк, в $$$j$$$-й из которых должно быть два целых числа $$$x_j, y_j$$$.

Обратите внимание, что если сумма на вашем пути равна $$$k$$$, но ваш путь отличается от загаданного, то ваше решение все еще неверное!

После вывода очередной строки не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Формат взломов

Для взлома сначала выведите строку, содержащую $$$n$$$, а затем другую строку, содержащую $$$q$$$. Должно выполняться $$$2 \leq n \leq 25$$$ и $$$1 \leq q \leq 1000$$$. Затем выведите $$$q$$$ путешествий, сделанных уткой в том же формате, как описано выше: для каждого путешествия, если утка посещала ячейки $$$(x_1, y_1), (x_2, y_2), \dotsc, (x_{2n - 1}, y_{2n - 1})$$$ в таком порядке, нужно вывести $$$2n - 1$$$ строк, в $$$j$$$-й строке должны быть два целых числа $$$x_j, y_j$$$. Должно выполняться $$$(x_1, y_1) = (1, 1)$$$ и $$$(x_{2n - 1}, y_{2n - 1}) = (n, n)$$$. Кроме того, для каждого $$$j$$$ такого, что $$$2 \leq j \leq 2n - 1$$$, должно быть верно, что $$$1 \leq x_j, y_j \leq n$$$ и либо $$$(x_j, y_j) = (x_{j - 1} + 1, y_{j - 1})$$$ либо $$$(x_j, y_j) = (x_{j - 1}, y_{j - 1} + 1)$$$.