题目描述

给定一个 \(n\) 个节点的树，每个节点上有一个整数，\(i\) 号点的整数为 \(val_i\)。

有 \(m\) 次询问，每次给出 \(u',v\)，您需要将其解密得到 \(u,v\)，并查询 \(u\) 到 \(v\) 的路径上有多少个不同的整数。

解密方式：\(u=u' \operatorname{xor} lastans\)。

\(lastans\) 为上一次询问的答案，若无询问则为 \(0\)。

输入格式

第一行有两个整数 \(n\) 和 \(m\)。

第二行有 \(n\) 个整数。第 \(i\) 个整数表示 \(val_i\)。

在接下来的 \(n-1\) 行中，每行包含两个整数 \(u,v\)，描述一条边。

在接下来的 \(m\) 行中，每行包含两个整数 \(u',v\)，描述一组询问。

输出格式

对于每个询问，一行一个整数表示答案。

样例1

样例输入1

8 2
105 2 9 3 8 5 7 7 
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
3 8

样例输出1

4
4

限制

对于 \(100\%\) 的数据，\(1\le u,v\le n\le 4\times 10^4\)，\(1\le m\le 10^5\)，\(0\le u',val_i<2^{31}\)。