Subtree XOR Sum Query

You are given a rooted tree \(T\) with \(n\) nodes numbered from \(1\) to \(n\) and rooted at node \(1\). Each node \(i\) has a positive integer weight \(v_i\). The tree is given as \(n-1\) edges.

There are \(Q\) queries. For each query, you are given two integers \(x\) and \(k\). Consider the subtree of node \(x\) (including \(x\) itself). Among the nodes in this subtree, only those nodes \(c\) with a distance \(d(c, x)\) \(\le k\) are considered. The answer to the query is defined as:

[ \sum_{c \in S} \Big(v_{c} \oplus d(c, x)\Big) \quad\text{, where } S = { c \text{ in the subtree of } x \mid d(c,x) \le k }]

Here, \(d(c, x)\) denotes the number of edges on the unique simple path between nodes \(c\) and \(x\) (with \(d(x,x)=0\)), and \(\oplus\) represents the bitwise XOR operation.

Your task is to process all queries and output the answer for each query on a separate line.

inputFormat

The first line contains two integers \(n\) and \(Q\), the number of nodes and the number of queries.

The second line contains \(n\) positive integers: \(v_1, v_2, \dots, v_n\), where \(v_i\) denotes the weight of the \(i\)-th node.

The next \(n-1\) lines each contain two integers \(u\) and \(v\), representing an edge between nodes \(u\) and \(v\). It is guaranteed that these edges form a tree with node \(1\) as the root.

The following \(Q\) lines each contain two integers \(x\) and \(k\), indicating a query.

outputFormat

For each query, print a single integer on a separate line—the answer to the query, which is the sum of \(v_c \oplus d(c, x)\) for all nodes \(c\) in the subtree of \(x\) such that \(d(c, x) \le k\).

sample

5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
1 1
2 1
1 2

6
11
19