题目背景

原 bzoj2589。

题目描述

给定一个 $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$，描述一组询问。

输出格式

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

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

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}$。