这是一个交互式问题。

给定两个长度为 $n$ 的非负整数数组 $a$ 和 $b$。 存在一个隐藏的从 $0$ 到 $2^{64}-1$ 的整数置换 $p(0), p(1), \dots, p(2^{64}-1)$。已知 $p(0) = 0$。 由于 $p$ 是一个置换，我们可以定义 $p^{-1}(x) = y$，当且仅当 $p(y) = x$。 此外，给定一个整数 $B$。一个正整数 $x$ 被称为“可爱（cute）”的，当且仅当满足以下两个条件： $x$ 的二进制表示（视为长度为 $B$ 的字符串）是一个回文串。 如果 $x$ 的二进制表示中某一位为 $1$，则该位必须位于前 $6$ 位或后 $6$ 位中。例如，若 $B = 14$，则中间的两位必须均为 $0$。

你需要支持两种类型的查询。 第一种查询是修改其中一个数组中的元素。 第二种查询是回答以下问题：如果我们列出 $2n$ 个整数 $p(a_1), p(a_1)+p(a_2), \dots, p(a_1)+p(a_2)+\dots+p(a_n)$ 以及 $p(b_1), p(b_1)+p(b_2), \dots, p(b_1)+p(b_2)+\dots+p(b_n)$，并将它们排序得到 $c_1, c_2, \dots, c_{2n}$，那么 $p^{-1}(c_k)$ 是多少？保证 $k$ 是一个“可爱”的数。

你可以调用以下两个交互函数： add(x, y)：返回 $p^{-1}(p(x)+p(y))$。 cmp(x, y)：返回 $p^{-1}(\min(p(x), p(y)))$。

请注意，如果 $p(x)+p(y) \ge 2^{64}$，则调用 add(x, y) 是无效的。 为了帮助你避免无效调用，保证在任何时刻都满足：$\max(p(a_1)+p(a_2)+\dots+p(a_n), p(b_1)+p(b_2)+\dots+p(b_n)) < 2^{64}$。

输入格式

交互开始时，读取三个整数：$n, q, B$ ($1 \le n \le 1.6 \cdot 10^4; 1 \le q \le 2 \cdot 10^4; 1 \le B \le 16$)。 然后，读取两行，第一行包含数组 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{64}$)，第二行包含数组 $b_1, b_2, \dots, b_n$ ($0 \le b_i < 2^{64}$)。 之后，读取 $q$ 个查询的内容。 接下来的 $q$ 行中，第一个整数 type 表示查询类型 ($1 \le \text{type} \le 2$)。 如果 type = 1，后面跟着三个整数：$t, \text{pos}, x$ ($1 \le t \le 2; 1 \le \text{pos} \le n; 0 \le x < 2^{64}$)。 若 $t = 1$，设置 $a_{\text{pos}} = x$。 若 $t = 2$，设置 $b_{\text{pos}} = x$。 如果 type = 2，后面跟着一个整数 $k$ ($1 \le k \le \min(2^B-1, 2 \cdot n)$)。保证 $k$ 是一个“可爱”的数。

保证至少有 $1$ 次且最多有 $5000$ 次类型为 $1$ 的查询。

交互

读取所有输入后，你最多可以进行 $1.6 \cdot 10^6$ 次函数调用。 对于每次调用，打印一行格式为 “$t \ x \ y$” 的内容，其中 $t$ 为 “A” 或 “C”，$x$ 和 $y$ 为整数 ($0 \le x, y < 2^{64}$)。然后刷新输出，并读取一行返回的整数 $z$： 如果 $t$ 为 “A”，你将得到 $z = p^{-1}(p(x)+p(y))$。 如果 $t$ 为 “C”，你将得到 $z = p^{-1}(\min(p(x), p(y)))$。

如果你进行了过多的调用或进行了无效调用，你将收到 Wrong Answer 判决。 在计算出所有类型为 $2$ 的查询答案后，打印两行。第一行应为 “! $m$”，其中 $m$ 是类型为 $2$ 的查询数量。第二行应包含 $m$ 个整数 $q_1, \dots, q_m$：分别为对应类型为 $2$ 的查询的答案。注意，打印答案不计入 $1.6 \cdot 10^6$ 次调用总数。打印这两行后，程序应终止。

样例

输入 1

2 3 2
1 3
5 7
2 3
1 2 2 9
2 3

输出 1

A 1 3
A 5 7
C 4 12
A 5 9
C 4 14
! 2
12 4