这是一道 IO 交互题。

小老鼠在 UOJ 十周年庆典上的所作所为被上报给跳蚤国王后，跳蚤国王大怒，下令伏特一定要抓住这只捣乱的小老鼠。

根据目击者的证词，伏特知道小老鼠目前藏身于水仙平原，这可以表示为一个从 $0$ 到 $2\times {10}^f$ 的一维数轴。

• 偶数位置：在 $[0,2\times {10}^f]$ 范围内，每个偶数整点的位置（包括 $0$ 和 $2\times {10}^f$ 两个端点）都有一株水仙花。
• 奇数位置：在 $[0,2\times {10}^f]$ 范围内，每个奇数整点的位置都有一只跳蚤。然而，有一个奇数位置 $y$ 例外，这个位置没有跳蚤，小老鼠就藏身于此。小老鼠混进跳蚤中间，试图逃避捕捉。

伏特的目标是确定小老鼠 $y$ 的确切位置。为此，他可以向众神的使者赫尔墨斯发起一系列询问。

1. 关于一次询问

伏特可以通过指定任意一个偶数 $x$（满足 $0\le x\le 2\times {10}^f$）来向赫尔墨斯发出查询，格式为 ? x。

赫尔墨斯将会回答：

• 如果 $x<y$，回答 <，表示查询的水仙花在小老鼠的左边。
• 如果 $x>y$，回答 >，表示查询的水仙花在小老鼠的右边。

然而，赫尔墨斯有时会决定说假话。如果他决定说假话，他会将原本的回答反转：

• 如果 $x<y$，反而回答 >。
• 如果 $x>y$，反而回答 <。

2. 关于假话

在赫尔墨斯做出回答之前，他会预先决定这一次是说真话还是说假话。

如果他决定说假话，那么他一定会反转自己的回答。

赫尔墨斯的回答必须遵循一系列禁忌。一个禁忌是一个由 F（表示假话）和 T（表示真话）组成的非空字符串。例如：

• 如果 FF 是一条禁忌，意味着赫尔墨斯不能连续说两次假话。
• 如果 FTF 是一条禁忌，意味着赫尔墨斯不能连续做出三个回答，其中第一个和第三个回答说的是假话，而第二个回答说的是真话。

有一个非空字符串集合 $S$，包含了所有赫尔墨斯的回答必须遵循的禁忌。

• 在不违反这些禁忌的前提下，赫尔墨斯可以自由决定说真话还是说假话。
• 保证 $S$ 中的所有字符串既以 F 开头又以 F 结尾。

你的目标

帮助伏特确定小老鼠 $y$ 的确切位置。你最多可以进行 $1.5\times {10}^5$ 次查询。最终，你需要将小老鼠的可能位置 $y$ 确定在最多 ${10}^g$ 个奇数位置的范围内。

交互格式

1. 输入部分

首先，从标准输入读取一行三个整数 $n,f,g$：

• $n=|S|$，表示禁忌的个数。
• $f$ 表示数轴的范围为 $[0,2\times {10}^f]$。
• $g$ 表示最终答案集合允许的最大大小（$\le {10}^g$）。

然后，从标准输入读取 $n$ 行，每行一个由 F 和 T 组成的不同非空模式字符串 $s_i$，表示第 $i$ 个禁忌。

2. 交互过程

读取上述信息之后，你可以开始进行一系列询问：

1. 做出一次询问：
   • 向标准输出打印一行 ? x，其中 $x$ 是 $[0,2\times {10}^f]$ 内的偶数。
   • 交互库会向标准输入打印一行 < 或 >，表示赫尔墨斯对此次询问的回答。
2. 做出最终回答：
   • 当你有信心确定小老鼠的位置后，向标准输出打印一行 ! t a[1] a[2] ...... a[t]，其中：
     • $t$ 是 $[1,{10}^g]$ 之间的整数。
     • 每个 $a_i$ 是 $[0,2\times {10}^f]$ 内的奇数，表示小老鼠 $y$ 的一个可能位置。

每次做出一个询问或最终回答后，都需要刷新缓冲区，以便交互库能读取你输出的内容。

当你做出最终回答并刷新缓冲区后，整个交互过程结束。然后系统会验证你回答的正确性：

• 交互库是 自适应 的。这意味着只要存在一个小老鼠的可能位置 $y$ 不在你打印的集合中，就算错误。只有当小老鼠所有可能的位置都包含在你打印的集合中，才算正确。如果集合中的某个 $y$ 小老鼠实际上不可能在那里，这并不算错误。
• 保证在交互过程中，任何时刻小老鼠始终存在至少一个可能的位置 $y$。

计分规则

本题首先受到与传统题相同的限制。如果你 TLE、MLE 或 RE，只能获得零分。

如果超过 $1.5\times {10}^5$ 次查询、最终回答错误、违反交互协议，或做出了不合法的询问／回答，统统只能获得零分。

如果最终回答正确，我们首先以 $32$ 分为满分计算你的得分 $E$。假设你在打印 ! 之前使用了 $q$ 次询问，得分根据 $q$ 的大小确定，$q$ 越小得分越高。

我们有两个合理的算法 compute_lower_bound() 和 compute_upper_bound()，会根据 $f,g$ 的值、禁忌集合的大小，以及每个禁忌字符串（即 $n,f,g$ 以及所有 $s_i$）综合计算询问次数 $q$ 的下界 $L$ 和上界 $R$。

这两个值 $L,R$ 不会向选手透露。但是我们保证：

1. 我们编写了一个明确的程序 interactor.cpp，如果使用这个 interactor.cpp 进行交互，无论你如何进行询问，交互库都会给出刁钻的回答。要将小老鼠的位置确定在不超过 ${10}^g$ 个奇数整点的范围内，至少需要 $L$ 次询问。
2. 我们编写了一个明确的程序 std.cpp，如果使用这个 std.cpp，无论交互库做出什么回答，这个程序都会给出合适的询问。在不超过 $R$ 次询问内，这个程序一定能够将小老鼠的位置确定在不超过 ${10}^g$ 个奇数整点的范围内。
3. 我们使用的所有输入数据，在经过上述两个函数计算后，全部满足 $2^{1/48}<R/L<2^{1/24}$。

使用不超过 $R$ 次询问可以获得满分。即使超过 $R$ 次也没有关系，你可以获得部分分：

• 如果 $q\le R$，你得 $32$ 分。
• 如果 $R<q\le 4R$，求出最小的正整数 $k$ 满足 $q\le 2^{k/12}R$，你得 $29-k$ 分。
• 如果 $q>4R$，你得 $4$ 分。

例外：$S=\{$F$\}$ 的情况是唯一的例外。这个时候 $L=R$，并且只要 $q>R$，一律得 $16$ 分。

最终，你在这个测试点的得分比例等于 $E/32$ 的值。

一个子任务的得分等于该子任务本身及其所有依赖子任务中所有测试点得分比例的最小值，乘以该子任务本身的总分值。

样例零

input

1 1 0
F
<
>
<

output

? 10
? 14
? 12
! 1 13

explanation

如果 F 是一条禁忌，意味着赫尔墨斯根本不能说假话。那么可以直接进行二分查找。

请注意，该样例不会在评测时被测试。

样例一～七

见下发文件，它们分别对应子任务 $1\sim 7$。

保证选手测样例使用的 interactor.cpp 与最终评测使用的 interactor.cpp 是同一份代码。

如果你不确定自己的程序是否正确，可以直接提交一次，看看测样例的结果。

限制与约定

本题采用捆绑测试，其中子任务 $7$ 依赖子任务 $6$。

对于所有数据，保证：$1\le n\le {10}^4$，$1\le \sum |s_i|\le 5\times {10}^5$，$1\le max|s_i|\le 100$，$1\le L\le R\le 1.5\times {10}^5$。

输入数据满足所有 $s_i$ 既以 F 开头又以 F 结尾，并且计算出的 $2^{1/48}<R/L<2^{1/24}$（$S=\{$F$\}$ 的情况例外）。

时间限制：$15\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$