阿霍伊！你听说过海盗和他们的宝藏吗？Bytie 在格丁尼亚（Gdynia）的海滩上散步时发现了一个旧瓶子。里面的信写着如何找到隐藏的宝藏，但它相当难以破译。Bytie 唯一可以确定的是，他需要找到附近公园里的两个特殊点，而宝藏就在连接这两个点的路径的中点上。

公园里有几条小径。除此之外，公园里的森林非常茂密，因此只有小径上的位置是人类可以到达的。小径的结构有一个有趣的性质：对于小径上的任意两个点，都存在唯一的一条路径连接它们。这条路径可能会沿着多条小径延伸，但它绝不会重复经过任何一个点。

Bytie 邀请他的朋友们帮忙探索公园。他们将从公园的某个点开始寻宝，该点位于其中一条小径上。他们将分阶段探索公园。在每个阶段中，其中一位朋友会选择一个已经探索过的点，并沿着一条小径从该点出发走若干步，期间只经过之前所有朋友都未曾到达过的点。

在探索过程中，Bytie 将仔细分析公园的结构。Bytie 可能会不时猜测决定宝藏位置的两个特殊点。对于每一次这样的猜测，他都想知道连接这两个点的唯一路径的中点。你的任务是帮助 Bytie 确定这些中点。

交互

你应该编写一个与评测程序交互的库。该库应包含以下三个函数，这些函数将由评测程序调用（如果需要，你也可以定义更多其他函数）：

• init —— 该函数将在程序开始执行时被精确调用一次。用于初始化你的数据结构等。

  • C/C++: void init();
  • Pascal: procedure init();

  当该函数被调用时，你应该假设公园中已经有一个被探索过的点，标记为数字 $1$。

• path —— 表示其中一位朋友在公园中探索了一条新路径。该函数用于构建表示小径的数据结构。

  • C/C++: void path(int a, int s);
  • Pascal: procedure path(a, s: longint);

  该路径起点为编号为 $a$ 的点（该点已被探索），并沿着小径走 $s$ 步（$s > 0$）。每走一步，当前所在的点就会被分配一个新编号：尚未被使用的最小正整数。该函数将至少被调用一次。

• dig —— 询问在何处挖掘宝藏。

  • C/C++: int dig(int a, int b);
  • Pascal: function dig(a, b: longint) : longint;

  它应该返回连接编号为 $a$ 和 $b$ 的点的路径中点所对应的编号。你可以假设点 $a$ 和 $b$ 已经被探索过，且 $a \neq b$。如果路径的中点不是一个具有分配编号的点（因为路径的长度为奇数），则该函数应返回路径的两个中点中距离 $a$ 较近的那一个点的编号（另请参阅下面的样例）。该函数将至少被调用一次。

你的库不能从标准输入或任何文件中读取任何内容，也不能向标准输出或任何文件写入任何内容。你的库可以向标准错误流/文件（stderr）写入内容。但是，你应该注意，这在程序执行期间会消耗时间。

如果你使用 C/C++ 编写，你的库不能包含 main 函数。如果你使用 Pascal，你必须提供一个单元（unit）（请参阅你磁盘上的示例程序）。

编译

你的库 —— tre.c、tre.cpp 或 tre.pas —— 将使用以下命令与评测程序一起编译：

• C: gcc -O2 -static -lm tre.c tregrader.c -o tre
• C++: g++ -O2 -static -lm tre.cpp tregrader.cpp -o tre
• Pascal:

  ppc386 -O2 -XS -Xt tre.pas
  ppc386 -O2 -XS -Xt tregrader.pas
  mv tregrader tre

样例说明

下表显示了一个样例调用序列以及 dig 调用的正确结果。该样例运行对应的公园小径结构如图所示。

数据范围

• 对函数（init、path 和 dig）的调用次数最多为 $400\,000$ 次，且 Bytie 的朋友们探索的点数最多为 $1\,000\,000\,000$。
• 在总分值为 $50$ 分的测试用例中，探索的点数将不超过 $400\,000$。
• 在总分值为 $20$ 分的测试用例中，探索的点数将不超过 $5\,000$，且对函数 init、path 和 dig 的调用次数最多为 $5\,000$ 次。

测试

为了让你测试你的解决方案，在你的机器上的 /home/zawodnik/tre/ 目录下提供了示例评测程序，文件名为 tregrader.c、tregrader.cpp 和 tregrader.pas。

为了使用评测程序进行测试，你应该将你的解决方案放在相应目录（c、cpp 或 pas）下的以下文件中： tre.c、tre.cpp 或 tre.pas。

在比赛开始时，在这些文件中的每一个中，你都可以找到该问题的一个示例错误解决方案。你可以使用以下命令编译你的解决方案：

make tre

只要你在相应的目录下编译程序，该命令的工作方式就与“编译”部分中描述的完全一致。C/C++ 编译需要文件 treinc.h，该文件也位于相应的目录中。

生成的二进制文件从标准输入读取函数名称和参数列表，调用你解决方案中的相应函数，并将 dig 函数调用的结果写入标准输出。输入中的函数列表格式应如下：第一行包含指令数量 $q$。接下来的 $q$ 行，每行包含一个字符 i、p 或 d，后跟两个非负整数。该字符决定了应该调用哪个函数：i 代表 init，p 代表 path，d 代表 dig。这些整数表示函数的参数：对于 path 为 $a$ 和 $s$，对于 dig 为 $a$ 和 $b$。如果字符是 i，则两个整数都等于 $0$。请注意，示例评测程序不会检查输入格式是否正确，或者是否满足“交互”和“数据范围”部分中列出的要求。

你将获得文件 tre0.in，它表示上述的样例执行过程。

要从该文件中读取数据，请使用以下命令：

./tre < tre0.in

你的解决方案返回的 dig 调用结果将被写入标准输出。

样例

样例输入 1

12
i 0 0
p 1 2
d 1 3
p 2 5
d 7 3
d 3 7
p 1 2
p 3 3
d 10 11
p 5 1
d 14 8
d 2 4

样例输出 1

2
5
4
1
6
2

说明

你可以通过将你的解决方案提交到评测系统（SIO）来验证你的解决方案对样例测试用例的输出是否正确。