黑箱开关

题目背景

你处在一个黑暗的房间中。圆桌上有若干黑箱排成一个环，每个黑箱内有一个开关。只有所有开关都处于关闭状态时，打开固定位置的总开关，房间的灯才会亮起。

若打开总开关后灯没有亮，圆桌会旋转一个你不知道的角度。你还拥有一个检测器，它可以查询指定开关集合中，处于开启状态的开关数的奇偶性。

本题为交互题。

题目描述

交互器维护一个长度为 $n$ 的二进制串 $a$。保证 $n$ 是 $2$ 的幂。下标从 $0$ 开始。

你的目标是使 $a$ 的所有位均变为 $0$。你可以执行以下三种操作。

操作 1：翻转

给出一个整数 $b$，满足 $0\le b<2^n$。

把 $b$ 写成二进制后，从低到高的第 $i$ 位记作 $b_i$，交互器执行

$$a_i\leftarrow a_i\oplus b_i\qquad(0\le i<n).$$

该操作没有返回值。

操作 2：奇偶性查询

给出一个整数 $b$，满足 $0\le b<2^n$。交互器返回

$$\bigoplus_{i=0}^{n-1}(a_i\mathbin{\&}b_i).$$

返回值为 $0$ 或 $1$。

操作 3：检查

查询 $a$ 是否每一位均为 $0$。

• 若是，交互器返回 $1$，本测试点通过；
• 否则，交互器返回 $0$，随后秘密选择一个非负整数 $t$，并执行循环位移

$$a_i\leftarrow a_{(i+t)\bmod n}\qquad(0\le i<n).$$

每次失败后选择的 $t$ 可以不同，你无法获知 $t$。交互器可以根据此前的交互过程选择旋转方式。

你至多可以执行 $x$ 次操作 2 和 $y$ 次操作 3。操作 1 的次数不受限制，但不能连续执行两次操作 1。

若用完全部 $y$ 次操作 3 后仍未得到返回值 $1$，则本测试点判为错误。

交互协议

交互开始时，你的程序需要读入三个整数：

n x y

随后，你可以输出以下命令。

执行操作 1

1 b

交互器不返回内容。

执行操作 2

2 b

然后读入一个整数 $0$ 或 $1$。

执行操作 3

3

然后读入一个整数 $0$ 或 $1$。读到 $1$ 后，你的程序应立即正常结束。

每次输出需要交互器回答的命令后，都必须刷新输出缓冲区。例如，C++ 可使用 cout << flush 或 endl。

若输出了非法命令、非法掩码、超过查询次数限制、连续执行两次操作 1，或在成功前提前结束程序，均会被判为错误。

数据范围

对于所有测试点：

$$1\le n\le 16,$$ $$0\le x\le n,$$ $$2^x\times y=2^n,$$

且存在非负整数 $k$，使得 $n=2^k$。

本题共 $36$ 个测试点，各测试点独立计分。

测试点编号	$n$	$x$	单点分值
$1\sim2$	$1$	$T-1$	$1$
$3\sim5$	$2$	$T-3$	$2$
$6$	$4$	$T-6$	$12$
$7\sim8$			$8$
$9\sim10$			$1$
$11$	$8$	$T-11$	$10$
$12\sim17$			$2$
$18\sim19$			$1$
$20$	$16$	$T-20$	$8$
$21\sim34$			$2$
$35\sim36$			$1$

其中 $T$ 表示测试点编号。