布尔兰迪亚准则

英文题名：G. Criterion in Burlandia
来源：Codeforces 2236G
比赛：Codeforces Round 1103 (Div. 3)
时间限制：3 seconds
空间限制：512 megabytes

题目描述

给定一棵树，每个点有友好值。每次询问一条路径，统计路径上有多少个非空连续子段满足该子段所有点权的异或值不小于点权和。

输入格式

第一行输入 $t$。每组输入 $n,q$、点权、$n-1$ 条边和 $q$ 个询问。所有 $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