Background

An easy check-in problem.

Because holding the Ugly Contest cost too much money, ac decided to send Push_Y to collect taxes.

Problem Description

The Ugly Country consists of $n$ cities, and city $1$ is the capital. These $n$ cities are connected by $n-1$ bidirectional roads of length $1$. Starting from city $x$, moving away from the capital (that is, moving to child nodes), all cities within distance at most $h$ are the tax-collection range of city $x$.

City $i$ needs to pay $a_i$ yuan in income tax. However, since the tax officer Push_Y likes XOR very much, the final tax paid will be the XOR sum of the tax amounts that should be paid by every city in its tax-collection range.

Push_Y will ask you $m$ queries. In each query, he asks how many thousand yuan of income tax city $x$ will collect when the tax-collection distance is $h$.

Simplified statement:

Given a tree with $n$ nodes, rooted at node $1$. The weight of node $i$ is $a_i$. Let $dep_u$ be the depth of node $u$, and the root has depth $1$. There are $q$ queries. Each query gives two integers $x,h$, asking for the value of $\bigoplus_{u\in son(x)\land dep_u-dep_x\le h}a_i$ after dividing by $1000$.

Here, $\bigoplus_{i=1}^ni$ means $1\operatorname{xor} 2\operatorname{xor}\cdots\operatorname{xor} n$.

Here, $\land$ means “and”, and $\operatorname{xor}$ means XOR.

Input Format

The first line contains two positive integers $n,m$, representing the number of cities and the number of queries.

The second line contains $n$ positive integers $a_i$, representing the income tax amount that each city should pay.

The third line contains $n-1$ positive integers. The $i$-th number $f_i$ means that city $i+1$ is connected by a road to city $f_i$.

Starting from line $4$, there are $m$ lines. Each line contains two positive integers $x,h$, representing one query.

Output Format

For each query, output one line with one real number, representing the amount of tax collected by that city.

Keep three digits after the decimal point.

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

Hint

For $30\%$ of the testdata, $1\le n,m\le 10^3$.

For $70\%$ of the testdata, $1\le n,m\le5 \times 10^4$. Among them, $20\%$ of the testdata are chains.

For $100\%$ of the testdata, $1\le n,m\le 10^6$, $1 \le a_i \le 10^9$, $1\le x \le n$, $0 \le h \le n$.

Translated by ChatGPT 5