You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡偷偷告诉你一颗大小为 $n$ 的树，编号从 $0$ 到 $n-1$。同时每个点有个 $[0,n-1]$ 之间的颜色。

巡有 $q$ 次询问，每次给定 $u,c$。你需要告诉巡 $u$ 祖先当中深度最大且颜色为 $c$ 的节点的编号。

你观摩了巡生成数据方法之强悍，但是发现了致命的缺点，就是生成所有点的颜色后，巡进行了随机重排。你决定利用这个漏洞爆标！

你知道巡最大点跑了 $2400\text{ ms}$，如果你的代码一共跑了 $x\text{ ms}$。

• 如果 $x\leq 1200$，你会获得该测试点的满分。
• 如果 $x\in(1200,2400]$你的得分将会是 $(\frac {2400 - x} {1200}) ^ 2$ 倍该测试点的最大得分。
• 否则，您将会获得零分的好成绩！

输入格式

由于本题输入量较大，我们采用交互题的方式进行评测。

你不需要也不应该实现主函数 main，你需要实现以下两个函数：

extern "C" void init(int n,vector<int> fa,vector<int> col)

• $n$：节点的个数。
• $fa$：长度为 $n$ 的数组，$fa_i$ 表示节点 $i$ 的父亲。特别地，$fa_0=-1$。
• $col$：长度为 $n$ 的数组，$col_i$ 表示节点 $i$ 的颜色。再次强调：$col$ 在数据生成完之后进行了一次随机打乱。
• 这个函数会被调用恰好一次，它给了你树的信息。你可以在这次函数调用的时候计算一些需要用到的信息。

extern "C"  int query(int x,int c)

• $x$：查询的节点编号。
• $c$：查询的颜色。
• 你应该返回 $x$ 的祖先中离 $x$ 最近的颜色为 $c$ 的节点的编号。若不存在这样的节点，返回 -1。
• 这个函数恰好被调用 $q$ 次。
• 每次调用函数时你并不知道以后的询问，也就是说，询问是 强制在线 的。

使用下发 grader 测试代码时，输入格式为：

• 第一行输入两个数 $n,q$。
• 第二行输入 $n$ 个数 $fa_0,\cdots,fa_{n-1}$。
• 第三行输入 $n$ 个数 $col_0,\cdots,col_{n-1}$。
• 接下来 $q$ 行，每行两个数 $x,c$，表示一组询问。

输出格式

测试代码时，输出格式为：

• $q$ 行，每行一个数，表示答案。
• 接下来，下发 grader 会输出你的耗时（注意这里并不会检查正确性）。

注意：这里给出的输入输出格式为下发 grader 的输入输出格式，仅为测试使用，你实现的函数不应该对标准输入输出流进行任何操作。

样例 #1

【样例输入】

5 25
-1 0 1 1 0
0 1 0 2 2
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
3 0
3 1
3 2
3 3
3 4
4 0
4 1
4 2
4 3
4 4

【样例输出】

0
-1
-1
-1
-1
0
1
-1
-1
-1
2
1
-1
-1
-1
0
1
3
-1
-1
0
-1
4
-1
-1

提示

对于所有数据，$2\leq n\leq 2\times 10^6$，$q\leq 10^7$，$-1\leq fa_i<i$，$0\leq col_i<n$，$fa_0=-1$ 且对任意 $1\leq i < n$，$fa_i\geq 0$。

• 子任务 1（$5$ 分）：$n\leq 1000$。
• 子任务 2（$20$ 分）：$n\leq 200000$。
• 子任务 3（$30$ 分）：$fa_i=i-1$。
• 子任务 4（$45$ 分）：无特殊限制。

每个子任务评分方式为子任务内所有点的得分取最小值。交互库运行时长不超过 600ms，消耗空间不超过 140MB。