Bit Twister on a Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given a rooted tree consisting of n nodes, numbered 1 through n. Each of the nodes has an integer A_{i} assigned to it.
Let's define children(v) as a sequence of the children of v placed in the increasing order of their ids. Let's define children(v, d) as the following:
 children(v, 0) = [v]
 children(v, 1) = children(v)
 children(v, d) = children(children(v)[1], d  1) + children(children(v)[2], d  1) + ... + children(children(v)[children(v)], d  1) if d > 1
Here '+' denotes concatenation of two sequences and children(v)[i] denotes accessing the i'th element of children(v).
Let's define bitTwister(x, y) function using the following code snippet written in Python:
def bitTwister(x, y): x ^= x >> 11 x ^= (x << 7) & 2636928640 x ^= (x << 15) & 4022730752 x ^= (x >> 18) return (1812433253 * (x ^ (x >> 30)) + y) & 4294967295
Let's define reducedByBitTwister(X_{1}, X_{2}, ..., X_{k}) as following:
 reducedByBitTwister(X_{1}) = X_{1}
 reducedByBitTwister(X_{1}, ..., X_{k  1}, X_{k}) = bitTwister(reducedByBitTwister(X_{1}, ..., X_{k  1}), X_{k}) if k > 1
Your are asked to process q queries of the following kind:
Your are given two integers v and d (1 ≤ v ≤ n). For convenience, let's denote children(v, d) as a node sequence V_{1}, V_{2}, ..., V_{k}. Your should calculate reducedByBitTwister(A_{V1}, ..., A_{Vk}). It's guaranteed, that children(v, d) is a nonempty sequence for each query.
Input
The first line of the input contains an integer T denoting the number of test cases.
The first line of the test case description contains two integers n and q. The next line contains n integers denoting A_{1}, A_{2}, ..., A_{n}. The next line contains n  1 integers P_{2}, ..., P_{n} denoting, that P_{i} is the direct ancestor of i. The first node of the tree is the root, so it has no ancestors.
Each of the next q lines contains two integers v and d denoting a query to process.
Output
For each of the queries, output the result on a separate line.
Constraints
 1 ≤ T ≤ 4
 1 ≤ n ≤ 100000
 1 ≤ q ≤ 300000
 0 ≤ A_{i} < 2^{32}
 1 ≤ P_{i} < i
Example
Input: 1 10 10 2433124241 332550764 3458320162 869965676 3840323658 3515151768 3271951378 246136236 1976704004 1673162377 1 2 3 2 2 3 7 1 7 10 0 5 0 1 3 7 0 10 0 9 0 5 0 2 2 6 0 1 1 Output: 1673162377 3840323658 2025664556 3271951378 1673162377 1976704004 3840323658 2025664556 3515151768 2552768825
Explanation
Here's an image of the tree from the example case:
Author:  kostya_by 
Tester:  pavel1996 
Editorial  http://discuss.codechef.com/problems/BITTWIST 
Tags  cook69 kostya_by mediumhard sqrtdecomp 
Date Added:  26032016 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions