题目背景

这是一道交互题。

题目描述

小 X 陷入了一个奇怪的梦。在梦境里，她在和小 Q 下一种奇怪的棋。

这是一个 $2^{2n}\times 2n$ 的棋盘，小 X 执黑先行，小 Q 执白后行。

每次操作，需要在当前未满的第一行内，任意选择一格下棋。一格内只能有一个棋子。

下满之后，共有 $2^{2n}$ 行棋子，小 X 的得分为本质不同的行数。

小 X 想最大化她的得分，但小 Q 想最小化小 X 的得分。

你的任务是，扮演小 X 或小 Q，最大化或最小化得分。

若你是小 X，在满足最大化得分 $ans$ 的同时，你也要最大化前 $ans$ 行中本质不同的行数。

交互格式

你要先从标准输入读入一行两个整数 $T,tp$，表示数据组数和你扮演的角色。保证 $tp\in\{0,1\}$。若 $tp=0$，表示你扮演小 Q（后手）；若 $tp=1$，表示你扮演小 X（先手）。

接下来每一组数据，你要先从标准输入读入一行一个正整数 $n$，含义见题目描述。

接下来会进行 $2^{2n}\times n$ 次交互。

在每次交互中：

• 若 $tp=0$，你要先从标准输入读入一行一个正整数 $x$，表示小 X 下了黑棋在当前未满的第一行的第 $x$ 列，接下来你要向标准输出输出一个正整数 $y$，表示你下了白棋在当前未满的第一行的第 $y$ 列；
• 若 $tp=1$，你要先向标准输出输出一个正整数 $x$，表示你下了黑棋在当前未满的第一行的第 $x$ 列，接下来你要从标准输入读入一行一个正整数 $y$ 表示小 Q 下了白棋在当前未满的第一行的第 $y$ 列。

你的输出都要换行并清空缓存区。

你需要保证你下棋的位置不能已有棋子。同时，交互库也会保证其下棋的位置不会已有棋子。

输入格式

见「交互格式」。

输出格式

见「交互格式」。

1 1
1

2

1

2

1

1

2

1

2

提示

【样例解释】

读入的 $n=1$，因此棋盘的大小是 $4\times 2$ 的。两人模拟如动图所示。最终结果如下图所示：

可以观察发现，最终本质不同的行数为 $2$。容易发现，这是小 X 能最大化的得分。同时，前 $2$ 行中本质不同行数为 $2$，显然无法达到更大的值。

【数据范围与规模】

对于所有的数据，保证 $1 \le n \le 7$，$1 \le T \le 3$，$tp\in\{0,1\}$。

【提示】

• 您可以使用如下语句来清空缓冲区：

  • 对于 C/C++：fflush(stdout)；
  • 对于 C++：std::cout << std::flush；
  • 对于 Java：System.out.flush()；
  • 对于 Python：stdout.flush()；
  • 对于 Pascal：flush(output)；
  • 对于其他语言，请自行查阅对应语言的帮助文档。
  • 特别的，对于 C++ 语言，在输出换行时使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

• 我们保证交互库耗时在 $1.5\text{s}$ 内，空间消耗可以忽略不计。