#P18574. XOR of All Children

XOR of All Children

XOR of All Children

给定一棵有 nn 个顶点的有根树,每个顶点上有一个整数。

每过一秒,所有顶点的值同时更新:一个顶点的新值,等于它当前的值与它的所有直接孩子当前值的异或。也就是说,计算这一秒的所有新值时,都使用更新前的值。

有 qq 个相互独立的询问。每个询问给出 (v,t)(v,t),请计算从最初状态开始恰好经过 tt 秒后,顶点 vv 上的值。

输入格式

第一行包含两个整数 n,qn,q(1≤n≤5⋅1051\le n\le5\cdot10^5,1≤q≤5⋅1051\le q\le5\cdot10^5),分别表示顶点数和询问数。

第二行包含 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n(0≤ci<2320\le c_i<2^{32}),表示各顶点的初始值。最大可能值为 42949672954294967295。

第三行包含 n−1n-1 个整数 p2,p3,…,pnp_2,p_3,\ldots,p_n(1≤pi<i1\le p_i<i),其中 pip_i 是顶点 ii 的父亲,顶点 11 为根。n=1n=1 时这一行没有整数。

接下来 qq 行,每行包含两个整数 v,tv,t(1≤v≤n1\le v\le n,0≤t≤2⋅1050\le t\le2\cdot10^5),描述一个询问。

输入只有这一棵树,不含测试组数。所有询问都从给定的初始数组出发,不承接上一个询问的时间或状态。

输出格式

对每个询问输出一行一个整数,表示顶点 vv 在经过 tt 秒后的值。按照普通非负十进制整数输出;异或结果仍在 0..232−10..2^{32}-1 内。

样例

输入

7 9
5 3 6 1 4 7 2
1 1 2 2 3 3
1 0
1 1
1 2
2 1
2 2
3 3
4 5
5 2
6 1

输出

5
0
5
6
3
3
1
4
7