联合国区域发展署 (UNRDA) 拥有一个定义非常明确的组织结构。它总共雇佣了 $N$ 名员工，每名员工来自全球 $R$ 个地理上不同的区域之一。员工按资历顺序编号为 $1$ 到 $N$，其中 $1$ 号员工（主席）资历最深。区域编号为 $1$ 到 $R$，无特定顺序。除主席外，每名员工都有一名直接主管。主管的资历总是比其下属深。

我们称员工 $A$ 是员工 $B$ 的管理者，当且仅当 $A$ 是 $B$ 的直接主管，或者 $A$ 是 $B$ 的直接主管的管理者。因此，例如，主席是每一位其他员工的管理者。此外，显然没有两名员工可以互为对方的管理者。

不幸的是，联合国调查局 (UNBI) 最近收到了一些投诉，称 UNRDA 的组织结构不平衡，偏袒全球某些区域。为了调查这些指控，UNBI 希望建立一个计算机系统，该系统在获得 UNRDA 的监督结构后，能够回答以下形式的查询：给定两个不同的区域 $r_1$ 和 $r_2$，机构中存在多少对员工 $e_1$ 和 $e_2$，使得员工 $e_1$ 来自区域 $r_1$，员工 $e_2$ 来自区域 $r_2$，且 $e_1$ 是 $e_2$ 的管理者。每个查询有两个参数：区域 $r_1$ 和 $r_2$；其结果是一个整数：满足上述条件的员工对 $(e_1, e_2)$ 的数量。

任务

编写一个程序，在给定所有员工的所属区域以及谁受谁监督的数据后，交互式地回答上述查询。

数据范围

• $1 \le N \le 200,000$ 员工总数
• $1 \le R \le 25,000$ 区域总数
• $1 \le Q \le 200,000$ 程序需要回答的查询总数
• $1 \le H_k \le R$ 员工 $k$ 的所属区域（对于 $1 \le k \le N$）
• $1 \le S_k < k$ 员工 $k$ 的直接主管（对于 $2 \le k \le N$）
• $1 \le r_1, r_2 \le R$ 查询中询问的区域

输入格式

程序必须从标准输入读取以下数据：

• 第一行包含整数 $N$、$R$ 和 $Q$，按顺序排列，以空格分隔。
• 接下来的 $N$ 行按资历顺序描述了机构的 $N$ 名员工。其中第 $k$ 行描述了编号为 $k$ 的员工。第一行（即描述主席的那一行）包含一个整数：主席的所属区域 $H_1$。其余 $N-1$ 行中的每一行包含两个以空格分隔的整数：员工 $k$ 的直接主管 $S_k$ 和员工 $k$ 的所属区域 $H_k$。

交互

读取输入数据后，程序必须交替从标准输入读取查询并向标准输出写入查询结果。$Q$ 个查询必须逐个回答；程序必须在接收下一个查询之前发送对已接收查询的响应。

每个查询在标准输入的一行中给出，由两个不同的整数组成，以空格分隔：两个区域 $r_1$ 和 $r_2$。

对每个查询的响应必须是标准输出上的一行，包含一个整数：满足 $e_1$ 的所属区域为 $r_1$，$e_2$ 的所属区域为 $r_2$，且 $e_1$ 是 $e_2$ 的管理者的员工对 $(e_1, e_2)$ 的数量。

说明：测试数据将确保任何查询的正确答案始终小于 $1,000,000,000$。

重要说明：为了与评测系统正确交互，程序需要在每次输出查询结果后刷新标准输出。同时需要避免在读取标准输入时发生意外阻塞（例如使用 scanf("%d\n") 时可能发生的情况）。请参阅技术信息表以获取有关如何正确执行此操作的说明。

子任务

• 对于部分测试点，总分 $30$ 分，$R$ 不超过 $500$。
• 对于部分测试点，总分 $55$ 分，没有任何区域拥有超过 $500$ 名员工。
• 同时满足上述两个条件的测试点得 $15$ 分。
• 至少满足上述两个条件之一的测试点得 $70$ 分。

样例

样例输入 1

6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1

样例输出 1

1
3
2
1

说明

如果您希望通过竞赛系统的测试接口测试您的解决方案，您提供的输入文件应同时包含输入数据和所有查询，如上面的样例输入所示。