题目背景

签到题

由于举办选丑大赛消耗了太多钱财，ac 决定派出 Push_Y 去收税。

题目描述

丑国由 $n$ 座城市组成，编号 $1$ 的为首都。这 $n$ 座城市由 $n-1$ 条长度为 $1$ 的双向道路连接。从编号为 $x$ 的城市出发，往远离首都的方向（即往儿子节点走），距离不超过 $h$ 的就是这座城市要收税的范围。

第 $i$ 座城市将要上缴 $a_i$ 元的所得税。但由于收税官 Push_Y 很喜欢异或，因此每座城市最终上缴的所得税将是在其收税范围内每座城市应缴税额的异或和。

Push_Y 将向你提出 $m$ 个询问，他将问你城市 $x$ 在收税距离为 $h$ 时将收到多少千元的所得税。

简化版题意：

给定一棵 $n$ 个点的树，根节点为 $1$ 号点，第 $i$ 个点的点权为 $a_i$，$dep_u$ 表示 $u$ 点的深度，根节点的深度为 $1$，$q$ 次询问，每次给定两个整数 $x,h$，表示询问 $\bigoplus_{u\in son(x)\land dep_u-dep_x\le h}a_i$ 除以 $1000$ 后的值。

其中 $\bigoplus_{i=1}^ni$ 表示 $1\operatorname{xor} 2\operatorname{xor}\cdots\operatorname{xor} n$。

此处 $\land$ 是“且”，$\operatorname{xor}$ 是异或。

输入格式

第一行两个正整数 $n,m$，表示城市数和询问数。

第二行 $n$ 个正整数 $a_i$， 表示每座城市应缴的所得税额。

第三行 $n-1$ 个正整数，其中第 $i$ 个数 $f_i$ 表示城市 $i+1$ 与城市 $f_i$ 有一条路相连。

从第 $4$ 行开始 $m$ 行，每行两个正整数 $x,h$，表示一组询问。

输出格式

对于每组询问，输出一行，一个实数，表示这座城市收取的税额。

答案保留三位小数。

6 3
604 545 402 378 25 13
1 2 2 3 3
1 2
3 0
2 4

0.149
0.402
0.733

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

0.004
0.004
0.001

提示

对于 $30\%$ 的数据，$1\le n,m\le 10^3$。

对于 $70\%$ 的数据，$1\le n,m\le5 \times 10^4$。其中有 $20\%$ 的数据是链。

对于 $100\%$ 的数据，$1\le n,m\le 10^6$，$1 \le a_i \le 10^9$，$1\le x \le n$，$0 \le h \le n$。