CF1061F.Lost Root

The graph is called tree if it is connected and has no cycles. Suppose the tree is rooted at some vertex. Then tree is called to be perfect $k$-ary tree if each vertex is either a leaf (has no children) or has exactly $k$ children. Also, in perfect $k$-ary tree all leafs must have same depth.

For example, the picture below illustrates perfect binary tree with $15$ vertices:

There is a perfect $k$-ary tree with $n$ nodes. The nodes are labeled with distinct integers from $1$ to $n$, however you don't know how nodes are labelled. Still, you want to find the label of the root of the tree.

You are allowed to make at most $60 \cdot n$ queries of the following type:

• "? $a$ $b$ $c$", the query returns "Yes" if node with label $b$ lies on the path from $a$ to $c$ and "No" otherwise.

Both $a$ and $c$ are considered to be lying on the path from $a$ to $c$.

When you are ready to report the root of the tree, print

• "! $s$", where $s$ is the label of the root of the tree.

It is possible to report the root only once and this query is not counted towards limit of $60 \cdot n$ queries.

Interaction

The first line of the standard input stream contains two integers $n$ and $k$ ($3 \le n \le 1500$, $2 \le k \lt n$) — the number of nodes in the tree and the value of $k$.

It is guaranteed that $n$ is such that the tree forms a perfect $k$-ary tree.

You can ask at most $60 \cdot n$ queries. To ask a query, print a line of form "? $a$ $b$ $c$", where $1 \le a, b, c \le n$. After that you should read a single line containing "Yes" or "No" depending on the answer of the query.

The tree is fixed for each test and it doesn't depend on your queries.

When you are ready to print the answer, print a line of the form "! $s$", where $s$ is the label of the root vertex and then terminate your program.

After printing each query do not forget to print end of line and flush the output. Otherwise you may get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• See documentation for other languages.

In case your program will make more than $60 \cdot n$ queries, but in other aspects would follow the interaction protocol and terminate coorectly, it will get verdict «Wrong Answer».

Hacks

To hack the solution use the following test format:

The first line should contain integers $n$ and $k$ ($3 \le n \le 1500$, $2 \le k \le 1500$) — the number of vertices and the $k$ parameter of the tree.

Of course, the value of $n$ must correspond to the size of the valid $k$-ary tree of some depth.

The second line should contain $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the labels of the tree in the natural order, all labels must be distinct.

Let's call the following ordering of the tree vertices to be natural: first the root of the tree goes, then go all vertices on depth of one edge from root, ordered from left to right, then go all vertices on depth of two edges from root, ordered from left to right, and so on until the maximum depth.

This way, the $a_1$ is the answer for the hack.

图被称为树，当且仅当它是连通的且不含环。假设该树以某个顶点为根。若树中每个顶点要么是叶子（即没有子节点），要么恰好有 $k$ 个子节点，则称该树为完美 $k$-叉树。此外，在完美 $k$-叉树中，所有叶子节点的深度必须相同。

例如，下图展示了一棵含 $15$ 个顶点的完美二叉树：

已知存在一棵含 $n$ 个节点的完美 $k$-叉树。这些节点被赋予了从 $1$ 到 $n$ 的互异整数标签，但你并不知道具体的标签分配方式。尽管如此，你仍希望找出树根节点的标签。

你最多可进行 $60 \cdot n$ 次如下形式的查询：

• "? $a$ $b$ $c$"：若标签为 $b$ 的节点位于从 $a$ 到 $c$ 的路径上，则返回 "Yes"；否则返回 "No"。

注意：$a$ 和 $c$ 均被视为位于从 $a$ 到 $c$ 的路径上。

当你确定了树根节点的标签，需输出：

• "! $s$"，其中 $s$ 为树根节点的标签。

你仅可报告一次根节点，且该次输出不计入 $60 \cdot n$ 次查询限制。

交互流程

标准输入的第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 1500$，$2 \le k \lt n$）—— 分别表示树中节点总数与参数 $k$。

保证 $n$ 的取值使得该树可构成一棵完美 $k$-叉树。

你最多可进行 $60 \cdot n$ 次查询。每次查询需输出形如 "? $a$ $b$ $c$" 的一行，其中 $1 \le a, b, c \le n$。随后需读入一行，其内容为 "Yes" 或 "No"，取决于查询结果。

对每个测试用例，树的结构是固定的，且不依赖于你的查询。

当你准备输出答案时，请输出形如 "! $s$" 的一行，其中 $s$ 是树根节点的标签，然后终止程序。

每次输出查询后，务必输出换行符并刷新输出缓冲区；否则可能收到 “Idleness limit exceeded” 判定。为此，请使用以下方式：

• C++ 中：fflush(stdout) 或 cout.flush()；
• Java 中：System.out.flush()；
• Pascal 中：flush(output)；
• Python 中：stdout.flush()；
• 其他语言请参阅相应文档。

若你的程序查询次数超过 $60 \cdot n$ 次，但其余方面均符合交互协议并能正常终止，则将被判为 «Wrong Answer»。

Hack（构造测试数据）

要 hack 一个解法，请按如下格式提供测试数据：

第一行应包含两个整数 $n$ 和 $k$（$3 \le n \le 1500$，$2 \le k \le 1500$）—— 分别表示树的顶点数及参数 $k$。

当然，$n$ 的取值必须对应某深度下的合法 $k$-叉树的大小。

第二行应包含 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）—— 表示按自然顺序排列的树节点标签，所有标签互异。

我们定义树节点的自然顺序如下：首先为树根；其次为所有与根距离为 $1$ 条边的节点，从左到右排序；接着为所有与根距离为 $2$ 条边的节点，从左到右排序；依此类推，直至最大深度。

据此，$a_1$ 即为该 hack 测试的正确答案。

The tree in the example is as follows:

The input and output for example illustrate possible interaction on that test (empty lines are inserted only for clarity).

The hack corresponding to the example would look like:

3 2
2 3 1

示例中的树如下所示：

示例的输入与输出展示了在该测试用例上可能发生的交互过程（空行仅为增强可读性而插入）。

对应于该示例的 hack 输入格式如下：

3 2
2 3 1