Tax Collection in the Kingdom of Ugly

In the Kingdom of Ugly, there are \( n \) cities with the capital being city \(1\). These \( n \) cities are connected by \( n-1 \) bidirectional roads of length 1, forming a tree with the capital as the root. Each city \(i\) is supposed to pay an income tax of \( a_i \) yuan. However, the tax collector Push_Y loves XOR, so the final tax collected from a city is the XOR of the tax values of all cities in its tax collection range.

The tax collection range for a city \( x \) is defined by starting at \( x \) and moving only away from the capital (i.e. only towards its children). All cities within a distance \( h \) (i.e. all cities in the subtree of \( x \) where \( \text{dep}(u)-\text{dep}(x) \le h \)) are included in the range. For each query, output the tax collected (in thousands of yuan) which is computed as \[ \frac{\bigoplus_{\substack{u \in subtree(x)\\\text{dep}(u)-\text{dep}(x)\le h}}a_u}{1000} \] where \( \bigoplus \) denotes the bitwise XOR operation.

inputFormat

The first line contains two integers \( n \) and \( m \), indicating the number of cities and the number of queries.

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \), where \( a_i \) is the tax amount (in yuan) of city \( i \).

Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) which denote a road connecting cities \( u \) and \( v \).

Each of the following \( m \) lines contains two integers \( x \) and \( h \) representing a query.

outputFormat

For each query, output a single integer on a separate line representing the tax collected from city \( x \) (in thousands of yuan) when the tax collection distance is \( h \).

sample

5 3
1000 2000 3000 4000 5000
1 2
1 3
2 4
2 5
1 1
2 1
3 2

3
7
3