CF1392E.Omkar and Duck

This is an interactive problem.

Omkar has just come across a duck! The duck is walking on a grid with $n$ rows and $n$ columns ($2 \leq n \leq 25$) so that the grid contains a total of $n^2$ cells. Let's denote by $(x, y)$ the cell in the $x$-th row from the top and the $y$-th column from the left. Right now, the duck is at the cell $(1, 1)$ (the cell in the top left corner) and would like to reach the cell $(n, n)$ (the cell in the bottom right corner) by moving either down $1$ cell or to the right $1$ cell each second.

Since Omkar thinks ducks are fun, he wants to play a game with you based on the movement of the duck. First, for each cell $(x, y)$ in the grid, you will tell Omkar a nonnegative integer $a_{x,y}$ not exceeding $10^{16}$, and Omkar will then put $a_{x,y}$ uninteresting problems in the cell $(x, y)$. After that, the duck will start their journey from $(1, 1)$ to $(n, n)$. For each cell $(x, y)$ that the duck crosses during their journey (including the cells $(1, 1)$ and $(n, n)$), the duck will eat the $a_{x,y}$ uninteresting problems in that cell. Once the duck has completed their journey, Omkar will measure their mass to determine the total number $k$ of uninteresting problems that the duck ate on their journey, and then tell you $k$.

Your challenge, given $k$, is to exactly reproduce the duck's path, i. e. to tell Omkar precisely which cells the duck crossed on their journey. To be sure of your mastery of this game, Omkar will have the duck complete $q$ different journeys ($1 \leq q \leq 10^3$). Note that all journeys are independent: at the beginning of each journey, the cell $(x, y)$ will still contain $a_{x,y}$ uninteresting tasks.

Interaction

The interaction will begin with a line containing a single integer $n$ ($2 \leq n \leq 25$), the amount of rows and columns in the grid. Read it.

Your program should then print $n$ lines. The $x$-th line should contain $n$ integers $a_{x,1}, a_{x,2}, \dotsc, a_{x,n}$ satisfying $0 \leq a_{x,y} \leq 10^{16}$, where $a_{x,y}$ is the amount of uninteresting problems Omkar should place in the cell $(x, y)$.

After that, you will first receive a single integer $q$, the amount of journeys that the duck will take. $q$ queries will follow; each query will consist of a single line containing an integer $k$, the amount of uninteresting problems that the duck ate on that journey. After each query, given that you have determined that the duck visited the cells $(x_1, y_1), (x_2, y_2), \dotsc, (x_{2n - 1}, y_{2n - 1})$ in that order (it should always be true that $(x_1, y_1) = (1, 1)$ and $(x_{2n - 1}, y_{2n - 1}) = (n, n)$), you should output $2n - 1$ lines so that the $j$-th line contains the two integers $x_j, y_j$.

Bear in mind that if the sum on your path is $k$, but your path is different from the actual hidden path, then your solution is still wrong!

After printing each line do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Hack Format

To hack, first output a line containing $n$ and another line containing $q$. It must be true that $2 \leq n \leq 25$ and $1 \leq q \leq 1000$. Then, output the $q$ journeys taken by the duck in the same format as described above: for each journey, given that the duck visited the cells $(x_1, y_1), (x_2, y_2), \dotsc, (x_{2n - 1}, y_{2n - 1})$ in that order, you should output $2n - 1$ lines so that the $j$-th line contains the two integers $x_j, y_j$. It must be true that $(x_1, y_1) = (1, 1)$ and $(x_{2n - 1}, y_{2n - 1}) = (n, n)$. Additionally, for each $j$ such that $2 \leq j \leq 2n - 1$, it must be true that $1 \leq x_j, y_j \leq n$ and either $(x_j, y_j) = (x_{j - 1} + 1, y_{j - 1})$ or $(x_j, y_j) = (x_{j - 1}, y_{j - 1} + 1)$.

这是一个交互式问题。

Omkar 刚刚遇到了一只鸭子！这只鸭子正行走在一张 $n$ 行 $n$ 列的网格上（$2 \leq n \leq 25$），因此该网格共包含 $n^2$ 个格子。我们用 $(x, y)$ 表示从上往下数第 $x$ 行、从左往右数第 $y$ 列的格子。此时，鸭子位于格子 $(1, 1)$（即左上角格子），并希望每次向下移动一格或向右移动一格（每秒移动一次），最终到达格子 $(n, n)$（即右下角格子）。

由于 Omkar 认为鸭子很有趣，他想和你玩一个基于鸭子移动的游戏。首先，对于网格中每个格子 $(x, y)$，你需要告诉 Omkar 一个非负整数 $a_{x,y}$（满足 $0 \leq a_{x,y} \leq 10^{16}$），Omkar 将在格子 $(x, y)$ 中放置 $a_{x,y}$ 道无趣的题目。之后，鸭子将从 $(1, 1)$ 出发，前往 $(n, n)$。在鸭子整个旅程中所经过的每一个格子 $(x, y)$（包括起点 $(1, 1)$ 和终点 $(n, n)$），鸭子都会吃掉该格子中的全部 $a_{x,y}$ 道无趣题目。当鸭子完成旅程后，Omkar 将称量其体重，从而确定鸭子在本次旅程中总共吃掉的无趣题目数量 $k$，并把该值 $k$ 告诉你。

你的任务是：在已知 $k$ 的前提下，精确还原鸭子的路径，即准确告诉 Omkar 鸭子在旅程中依次经过了哪些格子。为了验证你对这个游戏的完全掌握，Omkar 将让鸭子完成 $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}$ 表示 Omkar 应在格子 $(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$，但该路径与实际隐藏路径不同，则你的解答仍是错误的！

每次输出一行后，请务必输出换行符并刷新输出缓冲区。否则，你将收到“Idleness limit exceeded”（空闲超时）错误。为此，请使用以下方式：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请查阅相应文档。

Hack 格式

用于 hack 时，首先输出一行包含 $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)$。此外，对每个满足 $2 \leq j \leq 2n - 1$ 的 $j$，必须满足 $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)$。

The duck's three journeys are illustrated below.

$1 + 2 + 3 + 2 + 10 + 3 + 2 = 23$

$1 + 4 + 9 + 0 + 7 + 3 + 2 = 26$

$1 + 2 + 3 + 6 + 10 + 3 + 2 = 27$

鸭子的三次旅程如下图所示。

$1 + 2 + 3 + 2 + 10 + 3 + 2 = 23$

$1 + 4 + 9 + 0 + 7 + 3 + 2 = 26$

$1 + 2 + 3 + 6 + 10 + 3 + 2 = 27$