G. Criterion in Burlandia

Source: Codeforces 2236G
Contest: Codeforces Round 1103 (Div. 3)
Time limit: 3 seconds
Memory limit: 512 megabytes

Statement

Regions in Burlandia form a graph with $n$ vertices and $n-1$ edges, and there is exactly one path between any two vertices. Formally, the regions form a tree.

Each region has a friendliness value $a_i$.

There are $q$ queries. In each query, a pair of friends located in different regions is given. They want to know how many subsegments of the path between these regions are hospitable.

It is known that in Burlandia there are two criteria for evaluating relationships — XOR and sum. A subsegment of the path, containing some vertices lying on the path from region $x$ to region $y$, is called hospitable if it is non-empty and the sum of friendliness values on this subsegment does not exceed their XOR.

More formally, for each query you are given two vertices $x$ and $y$ $(x \neq y)$. Consider the shortest path from vertex $x$ to vertex $y$ in the tree. Let the vertices $v_1, v_2, \ldots, v_k$ form this path, where $v_1 = x$, $v_k = y$. You need to find the number of subsegments of this path for which the following condition holds: $$ a_{v_{l}} \oplus a_{v_{l+1}} \oplus \ldots \oplus a_{v_{r}} \geq (a_{v_{l}} + a_{v_{l+1}} + \ldots + a_{v_{r}}), $$ where $1 \leq l \leq r \leq k$ — the boundaries of the subsegment of vertices on the path from $x$ to $y$.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains integers $n$ ($2 \leq n \leq 10^5$) — the number of vertices in the tree, and $q$ ($1 \leq q \leq 10^5$) — the number of queries.

The second line contains an array of $n$ non-negative integers — the friendliness values of the regions ($0 \leq a_i \lt 2^{20}$).

The next $n - 1$ lines describe the edges of the tree: each line contains integers $u, v$ ($1 \leq u, v \leq n$) — an edge.

Then $q$ lines follow describing the queries. Each query is given by integers $x, y$ ($1 \leq x, y \leq n$, $x \neq y$) — the vertices that define the path for which you need to count the number of hospitable subsegments.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases do not exceed $10^5$, and that the edges indeed form a tree.

Output

For each query output an answer on a separate line.

Note

For clarity, consider the third query from the third sample.

The path from vertex $2$ to vertex $3$ consists of vertices ${2, 4, 3}$.

The subsegment $[2; 3]$ does not satisfy the condition, since the XOR on it is $a_4 \oplus a_3 = 4 \oplus 4 = 0$, while the sum is $a_4 + a_3 = 4 + 4 = 8$.

The subsegment $[1; 3]$ does not satisfy the condition, since the XOR on it is $a_2 \oplus a_4 \oplus a_3 = 2 \oplus 4 \oplus 4 = 2$, while the sum is $a_2 + a_4 + a_3 = 2 + 4 + 4 = 10$.

It can be shown that all other 4 subsegments satisfy the condition.

For each query, output the answer in a separate line.

Examples

3
4 3
0 0 4 1
1 2
1 3
1 4
1 4
2 3
2 4
4 3
0 4 1 2
1 3
1 4
2 4
1 2
2 3
2 4
4 3
3 2 4 4
1 2
2 4
3 4
1 2
1 3
2 3

3
6
6
6
10
3
2
5
4