CF1673F.Anti-Theft Road Planning

This is an interactive problem.

A city has $n^2$ buildings divided into a grid of $n$ rows and $n$ columns. You need to build a road of some length $D(A,B)$ of your choice between each pair of adjacent by side buildings $A$ and $B$. Due to budget limitations and legal restrictions, the length of each road must be a positive integer and the total length of all roads should not exceed $48\,000$.

There is a thief in the city who will start from the topmost, leftmost building (in the first row and the first column) and roam around the city, occasionally stealing artifacts from some of the buildings. He can move from one building to another adjacent building by travelling through the road which connects them.

You are unable to track down what buildings he visits and what path he follows to reach them. But there is one tracking mechanism in the city. The tracker is capable of storing a single integer $x$ which is initially $0$. Each time the thief travels from a building $A$ to another adjacent building $B$ through a road of length $D(A,B)$, the tracker changes $x$ to $x\oplus D(A,B)$. Each time the thief steals from a building, the tracker reports the value $x$ stored in it and resets it back to $0$.

It is known beforehand that the thief will steal in exactly $k$ buildings but you will know the values returned by the tracker only after the thefts actually happen. Your task is to choose the lengths of roads in such a way that no matter what strategy or routes the thief follows, you will be able to exactly tell the location of all the buildings where the thefts occurred from the values returned by the tracker.

Interaction

First read a single line containing two integers $n$ $(2\leq n\leq 32)$ and $k$ $(1\leq k\leq 1024)$ denoting the number of rows and number of thefts respectively.

Let's denote the $j$-th building in the $i$-th row by $B_{i,j}$.

Then print $n$ lines each containing $n-1$ integers. The $j$-th integer of the $i$-th line must be the value of $D(B_{i,j},B_{i,j+1})$.

Then print $n-1$ lines each containing $n$ integers. The $j$-th integer of the $i$-th line must be the value of $D(B_{i,j},B_{i+1,j})$.

Remember that the total length of the roads must not exceed $48\,000$.

Then answer $k$ queries. First read the value $x$ returned by the tracker. Then print two integers denoting the row number and column number of the building where the theft occurred. After that you will be able to answer the next query (if such exists).

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

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

Hacks

You cannot make hacks in this problem.

这是一个交互式问题。

一座城市中有 $n^2$ 栋建筑，排列成 $n$ 行 $n$ 列的网格。你需要为每一对边相邻（即共享一条边）的建筑 $A$ 和 $B$ 构建一条长度为 $D(A,B)$ 的道路，其中 $D(A,B)$ 由你自行选定。受限于预算和法律约束，每条道路的长度必须是正整数，且所有道路长度之和不得超过 $48\,000$。

城中有一名小偷，他将从最左上角的建筑（即第 $1$ 行第 $1$ 列的建筑）出发，在城市中四处游荡，并不时地从若干栋建筑中盗取文物。他可在两栋相邻建筑之间沿连接它们的道路移动。

你无法获知小偷访问了哪些建筑、也无法得知他所走的具体路径。但城市中存在一种追踪机制：该追踪器可存储一个整数 $x$，初始值为 $0$。每当小偷经由一条长度为 $D(A,B)$ 的道路从建筑 $A$ 移动到相邻建筑 $B$ 时，追踪器会将 $x$ 更新为 $x \oplus D(A,B)$（其中 $\oplus$ 表示按位异或运算）。每当小偷在某栋建筑中实施盗窃时，追踪器会报告当前存储的值 $x$，并立即将 $x$ 重置为 $0$。

已知小偷恰好会在 $k$ 栋建筑中行窃，但你只有在盗窃实际发生后才能得知追踪器返回的数值。你的任务是：以某种方式为所有道路指定长度，使得无论小偷采取何种策略或路径，你都能根据追踪器返回的 $k$ 个数值，唯一确定每次盗窃发生的建筑位置（即其行列坐标）。

交互流程

首先读入一行，包含两个整数 $n$（$2 \leq n \leq 32$）和 $k$（$1 \leq k \leq 1024$），分别表示网格的行数与盗窃次数。

我们用 $B_{i,j}$ 表示第 $i$ 行第 $j$ 列的建筑。

接着输出 $n$ 行，每行包含 $n-1$ 个整数。其中第 $i$ 行的第 $j$ 个整数应为 $D(B_{i,j}, B_{i,j+1})$（即同一行内第 $j$ 列与第 $j+1$ 列建筑之间的道路长度）。

然后输出 $n-1$ 行，每行包含 $n$ 个整数。其中第 $i$ 行的第 $j$ 个整数应为 $D(B_{i,j}, B_{i+1,j})$（即同一列内第 $i$ 行与第 $i+1$ 行建筑之间的道路长度）。

注意：所有道路长度之和不得超过 $48\,000$。

随后需回答 $k$ 个查询。对每个查询：

• 首先读入追踪器返回的值 $x$；
• 然后输出两个整数，分别表示盗窃发生的建筑所在的行号与列号；
• 此后即可处理下一个查询（若还存在）。

输出答案后，务必输出换行符并刷新输出缓冲区；否则将收到判定结果 “Idleness limit exceeded”（空闲时间超限）。刷新缓冲区的方法如下：

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

Hack（数据生成）

本题不允许进行 Hack。

For the sample test, $n=2$ and $k=4$.

You choose to build the roads of the following lengths:

The thief follows the following strategy:

1. Start at $B_{1,1}$.
2. Move Right to $B_{1,2}$.
3. Move Down to $B_{2,2}$.
4. Move Left to $B_{2,1}$.
5. Move Up to $B_{1,1}$.
6. Move Right to $B_{1,2}$.
7. Steal from $B_{1,2}$.
8. Move Left to $B_{1,1}$.
9. Steal from $B_{1,1}$.
10. Move Down to $B_{2,1}$.
11. Move Right to $B_{2,2}$.
12. Move Up to $B_{1,2}$.
13. Steal from $B_{1,2}$.
14. Move Left to $B_{1,1}$.
15. Move Down to $B_{2,1}$.
16. Steal from $B_{2,1}$.

The tracker responds in the following way:

1. Initialize $x=0$.
2. Change $x$ to $x\oplus 1=0\oplus1=1$.
3. Change $x$ to $x\oplus 4=1\oplus4=5$.
4. Change $x$ to $x\oplus 8=5\oplus8=13$.
5. Change $x$ to $x\oplus 2=13\oplus2=15$.
6. Change $x$ to $x\oplus 1=15\oplus1=14$.
7. Return $x=14$ and re-initialize $x=0$.
8. Change $x$ to $x\oplus 1=0\oplus1=1$.
9. Return $x=1$ and re-initialize $x=0$.
10. Change $x$ to $x\oplus 2=0\oplus2=2$.
11. Change $x$ to $x\oplus 8=2\oplus8=10$.
12. Change $x$ to $x\oplus 4=10\oplus4=14$.
13. Return $x=14$ and re-initialize $x=0$.
14. Change $x$ to $x\oplus 1=0\oplus1=1$.
15. Change $x$ to $x\oplus 2=1\oplus2=3$.
16. Return $x=3$ and re-initialize $x=0$.

对于样例测试，$n=2$ 且 $k=4$。

你选择修建如下长度的道路：

小偷采用如下策略：

1. 从 $B_{1,1}$ 出发。
2. 向右移动至 $B_{1,2}$。
3. 向下移动至 $B_{2,2}$。
4. 向左移动至 $B_{2,1}$。
5. 向上移动至 $B_{1,1}$。
6. 向右移动至 $B_{1,2}$。
7. 在 $B_{1,2}$ 处行窃。
8. 向左移动至 $B_{1,1}$。
9. 在 $B_{1,1}$ 处行窃。
10. 向下移动至 $B_{2,1}$。
11. 向右移动至 $B_{2,2}$。
12. 向上移动至 $B_{1,2}$。
13. 在 $B_{1,2}$ 处行窃。
14. 向左移动至 $B_{1,1}$。
15. 向下移动至 $B_{2,1}$。
16. 在 $B_{2,1}$ 处行窃。

追踪器按如下方式响应：

1. 初始化 $x=0$。
2. 将 $x$ 更新为 $x\oplus 1=0\oplus1=1$。
3. 将 $x$ 更新为 $x\oplus 4=1\oplus4=5$。
4. 将 $x$ 更新为 $x\oplus 8=5\oplus8=13$。
5. 将 $x$ 更新为 $x\oplus 2=13\oplus2=15$。
6. 将 $x$ 更新为 $x\oplus 1=15\oplus1=14$。
7. 返回 $x=14$，并重新初始化 $x=0$。
8. 将 $x$ 更新为 $x\oplus 1=0\oplus1=1$。
9. 返回 $x=1$，并重新初始化 $x=0$。
10. 将 $x$ 更新为 $x\oplus 2=0\oplus2=2$。
11. 将 $x$ 更新为 $x\oplus 8=2\oplus8=10$。
12. 将 $x$ 更新为 $x\oplus 4=10\oplus4=14$。
13. 返回 $x=14$，并重新初始化 $x=0$。
14. 将 $x$ 更新为 $x\oplus 1=0\oplus1=1$。
15. 将 $x$ 更新为 $x\oplus 2=1\oplus2=3$。
16. 返回 $x=3$，并重新初始化 $x=0$。