Gary 有一面巨大的正方形墙,高和宽均为 $2 \times 10^9$ 纳米。墙上放置了一个圆形飞镖靶,其半径在 $A$ 到 $B$ 纳米之间(包含 $A$ 和 $B$)。飞镖靶完全位于墙内,但可以接触墙的边缘。飞镖靶的圆心距离墙的每一条边均为整数纳米。
Gary 邀请他的朋友 Mika 来玩一个有趣的游戏。Gary 蒙住 Mika 的眼睛,并挑战她向飞镖靶的中心投掷飞镖。为了帮助她,每当 Mika 向墙上投掷飞镖时,Gary 都会告诉她飞镖是否击中了飞镖靶。
Mika 不知道飞镖靶在墙上的位置,但由于 Mika 飞镖技术精湛,她可以以纳米级的精度投掷飞镖。也就是说,她可以瞄准并击中距离墙的每一条边均为整数纳米的任何点。在每次投掷飞镖后,Gary 会立即告诉她是否击中了飞镖靶的中心、飞镖靶的其他部分,或者完全没中而击中了光秃秃的墙面。
你能帮助 Mika 击中飞镖靶的中心,且投掷次数不超过 300 次吗?
输入格式
程序首先应读取一行,包含三个整数 $T$、$A$ 和 $B$,分别表示测试用例的数量以及飞镖靶半径的最小值和最大值(包含)。(注意:对于同一个测试集中的每个测试用例,$A$ 和 $B$ 是相同的。)
然后,你需要处理 $T$ 个测试用例。
我们将飞镖可以瞄准的点表示为坐标对 $(x, y)$,其中 $x$ 和 $y$ 是 $-10^9$ 到 $10^9$ 之间的整数(包含)。坐标对 $(x, y)$ 表示距离墙左边缘 $x + 10^9$ 纳米、距离墙底边缘 $y + 10^9$ 纳米的点。因此,点 $(0, 0)$ 位于墙的中心。
对于每个测试用例,裁判会以设计好的(非随机)方式在限制范围内秘密选择一个半径 $R$ 和一个飞镖靶中心 $(X, Y)$。对于每个测试用例,你需要与裁判进行最多 300 次交互。你的程序代表 Mika,裁判程序代表 Gary。
第 $i$ 次交互中,你的程序首先输出一行,包含两个整数 $X_i$ 和 $Y_i$,两者均在 $-10^9$ 到 $10^9$ 之间(包含),裁判会回复一行,内容为以下之一:
CENTER,如果 $X_i = X$ 且 $Y_i = Y$HIT,如果 $0 < (X - X_i)^2 + (Y - Y_i)^2 \leq R^2$MISS,在其他所有情况下。
在发送 CENTER 后,裁判将开始等待下一个测试用例的第一次交互(如果有的话)。
如果你输出的格式不正确或包含越界的值,裁判将回复一行 WRONG。如果在没有收到 CENTER 的情况下进行了 300 次交互(包括裁判的 300 次回复),或者如果你收到了 WRONG,裁判将结束所有通信。
数据范围
时间限制:每个测试集 30 秒。 内存限制:1GB。 $1 \leq T \leq 20$。 $A \leq R \leq B$。 $-10^9 + R \leq X \leq 10^9 - R$。 $-10^9 + R \leq Y \leq 10^9 - R$。
子任务
测试集 1(可见判决) $A = B = 10^9 - 5$。
测试集 2(可见判决) $A = B = 10^9 - 50$。
测试集 3(隐藏判决) $A = 10^9 / 2$。 $B = 10^9$。
样例
// 以下读取 20 到 t,999999995 到 a 和 b。 t, a, b = readline_int_list() // 裁判秘密选择 R = 999999995(此处无选择余地)以及 X = -1, Y = 3(此处有选择余地)。 // (注意:实际的测试集 1 不一定使用此示例中的值。) // 我们尝试瞄准墙的左上角,飞镖靶不覆盖该点。 printline -1000000000 1000000000 to stdout flush stdout r = readline_string() // 读取 MISS。 // 我们尝试瞄准墙的中心。这击中了飞镖靶,但不是中心。 printline 0 0 to stdout flush stdout r = readline_string() // 读取 HIT。 // 我们做了一个超级幸运的选择,瞄准了飞镖靶的中心。 printline -1 3 to stdout flush stdout r = readline_string() // 读取 CENTER。 // 裁判开始下一个测试用例。它秘密选择 R = 999999995 且 X = 5, Y = 5。 // 我们不小心投掷了一个超出允许范围的飞镖。 printline -1234567890 1234567890 to stdout flush stdout r = readline_string() // 读取 WRONG。 exit // 退出以避免模糊的 TLE 错误。