题目描述

布兰迪亚的区域构成了一幅图，包含 $n$ 个顶点和 $n-1$ 条边，且任意两个顶点之间有且仅有一条路径。形式化地说，这些区域构成了一棵树。

每个区域有一个友好值 $a_i$。

现有 $q$ 次查询。每次查询给出两个位于不同区域的朋友。他们想知道这两个区域之间的路径上有多少个子段是友好的。

已知在布兰迪亚，评估关系有两个标准——XOR 与和。路径的一段子段，包含从区域 $x$ 到区域 $y$ 路径上的若干顶点，如果 它非空，并且该子段上友好值的和不超过其 XOR，则称该子段是友好的。

更形式化地说，对于每次查询，给定两个顶点 $x$ 和 $y$ $(x \neq y)$。考虑树中从顶点 $x$ 到顶点 $y$ 的最短路径。设顶点 $v_1, v_2, \ldots, v_k$ 构成这条路径，其中 $v_1 = x$, $v_k = y$。你需要找出该路径上满足以下条件的子段数量：

$$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}}),$$

其中 $1 \leq l \leq r \leq k$ 为路径上从 $x$ 到 $y$ 的顶点子段的边界。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。随后是每个测试用例的描述。

每个测试用例的第一行包含整数 $n$（$2 \leq n \leq 10^5$）——树中顶点的数量，以及 $q$（$1 \leq q \leq 10^5$）——查询的数量。

第二行包含一个由 $n$ 个非负整数组成的数组——区域的友好度值（$0 \leq a_i \lt 2^{20}$）。

接下来的 $n-1$ 行描述树的边：每行包含整数 $u, v$（$1 \leq u, v \leq n$）——一条边。

随后是 $q$ 行描述查询。每个查询由整数 $x, y$ 给出（$1 \leq x, y \leq n$, $x \neq y$）——定义路径的顶点，你需要计算该路径上友好子段的数量。

保证所有测试用例中 $n$ 的总和以及 $q$ 的总和不超过 $10^5$，并且这些边确实构成一棵树。

输出格式

对于每个查询，在单独的一行输出一个答案。

样例

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