Это интерактивная задача
Омкар только что наткнулся на утку! Утка ходит по сетке с \(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)\).