Chanek 先生有一个果园,其结构为一棵有根三元树,其 $$$N$$$ 顶点编号从 $$$1$$$ 到 $$$N$$$。树的根是顶点$$$1$$$。 $$$P_i$$$ 表示顶点 $$$i$$$ 的父节点,对于 $$$(2 \le i \le N)$$$。有趣的是,树的高度不大于$$$10$$$。树的高度定义为树中从根到顶点的最大距离。
树的每个顶点都有一个灌木丛。最初,所有灌木丛都结出果实。水果不会生长在当前已经有水果的灌木丛上。顶点$$$i$$$处的灌木将在自上次收获后$$$A_i$$$天后结出果实。
Chanek 先生将参观他的果园 $$$Q$$$ 天。在 $$$i$$$ 天,他将收获顶点 $$$X_i$$$ 子树上所有有果实的灌木丛。对于每一天,确定从每个收获的灌木丛到 $$$X_i$$$ 的距离总和,以及当天收获的灌木丛的数量。收获灌木丛意味着收集灌木丛上的所有果实。
例如,如果 Chanek 先生收获了顶点 $$$X$$$ 子树上的所有水果,并收获了灌木丛 $$$[Y_1, Y_2, \dots, Y_M]$$$,则距离总和为 $$$\sum_{i = 1}^M \text{distance}(X, Y_i)$$$
树中的 $$$\text{distance}(U, V)$$$ 被定义为从 $$$U$$$ 到 $$$V$$$ 的简单路径上的边数。
输入
第一行包含两个整数 $$$N$$$ 和 $$$Q$$$ $$$(1 \le N,\ Q,\le 5 \cdot 10^4)$$$,表示顶点数和 Chanek 先生访问果园的天数。
第二行包含 $$$N$$$ 整数 $$$A_i$$$ $$$(1 \le A_i \le 5 \cdot 10^4)$$$,表示顶点 $$$i$$$ 处灌木上果实的生长速度,对于 $$$(1 \le i \le N)$$$。
第三行包含 $$$N-1$$$ 整数 $$$P_i$$$ $$$(1 \le P_i \le N, P_i \ne i)$$$,表示树中顶点 $$$i$$$ 的父节点,$$$(2 \le i \le N)$$$。保证每个顶点最多可以是 $$$3$$$ 个其他顶点的父顶点。还保证树的高度不大于$$$10$$$。
接下来的 $$$Q$$$ 行包含一个整数 $$$X_i$$$ $$$(1 \le X_i \le N)$$$,表示 Chanek 先生在 $$$i$$$ 那天的访问开始,即 $$$(1 \le i \le Q)$$$。
输出
输出 $$$Q$$$ 行,$$$i$$$ 行给出从收获的灌木丛到 $$$X_i$$$ 的距离总和,以及收获的灌木丛的数量。
示例
输入 #1
2 3 1 2 1 2 1 1
输出 #1
0 1 0 1 1 2
输入 #2
5 3 2 1 1 3 2 1 2 2 1 1 1 1
输出 #2
6 5 3 2 4 4
注意
对于第一个示例:
- 在第 1 天,Chanek 先生从顶点 $$$2$$$ 开始,可以在顶点 2 收获灌木丛。
- 第 2 天,Chanek 先生从顶点 $$$1$$$ 开始,仅从灌木丛 $$$1$$$ 收获(灌木丛 2 的果实尚未生长)。
- 第 3 天,Chanek 先生从顶点 $$$1$$$ 开始,收获灌木 $$$1$$$ 和 $$$2$$$ 上的果实。从每个收获的灌木丛到 $$$1$$$ 的距离总和为 $$$1$$$。
对于第二个示例,Chanek 先生始终从顶点 $$$1$$$ 开始。查内克先生在第一天、第二天和第三天收获的灌木丛分别为 $$$[1, 2, 3, 4, 5], [2, 3], [1, 2, 3, 5]$$$。