CF1438F.Olha and Igor

This is an interactive problem.

Igor wants to find the key to Olha's heart. The problem is, that it's at the root of a binary tree.

There is a perfect binary tree of height $h$ consisting of $n = 2^{h} - 1$ nodes. The nodes have been assigned distinct labels from $1$ to $n$. However, Igor only knows $h$ and does not know which label corresponds to which node.

To find key to Olha's heart he needs to find the label assigned to the root by making queries of the following type at most $n+420$ times:

• Select three distinct labels $u$, $v$ and $w$ ($1 \leq u,v,w \leq n$).
• In response, Olha (the grader) will tell him the label of the lowest common ancestor of nodes labelled $u$ and $v$, if the tree was rooted at the node labelled $w$ instead.

Help Igor to find the root!

Note: the grader is not adaptive: the labels are fixed before any queries are made.

这是一个交互式问题。

伊戈尔想找到打开奥尔哈芳心的钥匙。问题是，这把钥匙位于一棵二叉树的根节点上。

存在一棵高度为 $h$ 的完美二叉树，共包含 $n = 2^{h} - 1$ 个节点。这些节点被赋予了从 $1$ 到 $n$ 的互不相同的标签。然而，伊戈尔只知道 $h$，并不知道哪个标签对应哪个节点。

为了找到打开奥尔哈芳心的钥匙，他需要通过至多 $n+420$ 次如下类型的查询，确定根节点所对应的标签：

• 选择三个互不相同的标签 $u$、$v$ 和 $w$（满足 $1 \leq u,v,w \leq n$）；
• 作为回应，奥尔哈（评测程序）将告诉他：若将标签为 $w$ 的节点设为整棵树的根，则标签为 $u$ 和 $v$ 的两个节点的最低公共祖先（LCA） 所对应的标签。

请帮助伊戈尔找出根节点！

注意：评测程序是非自适应的，即所有节点的标签在任何查询发起前就已固定。

The first and only line contains a single integer $h$ ($3 \le h \le 18$) — the height of the tree.

第一行且唯一一行包含一个整数 $h$（$3 \le h \le 18$）——树的高度。

The labels corresponding to the tree in the example are [$4$,$7$,$2$,$6$,$1$,$5$,$3$], meaning the root is labelled $4$, and for $1 \lt i \le n$, the parent of $p_i$ is $p_{ \lfloor{\frac{i}{2}}\rfloor }$.

示例中树对应的标签为 [$4$,$7$,$2$,$6$,$1$,$5$,$3$]，表示根节点的标签为 $4$，且对 $1 \lt i \le n$，节点 $p_i$ 的父节点为 $p_{ \lfloor{\frac{i}{2}}\rfloor }$。