题目描述

小 T 有一棵包含 $n$ 个点的树，第 $i$ 个点的权值为 $a_i$。

小 T 维护一个集合 $S$。每当他向 $S$ 中加入一个整数 $x$ 时，会依次执行以下操作：

1. 将 $S$ 中所有大于等于 $x$ 的数都加 $1$；
2. 将 $x$ 加入集合 $S$。

现在有 $m$ 次询问。每次询问给定两个点 $u,v$ 和一个参数 $k$。

每次询问开始时，集合 $S$ 为空。小 T 从点 $u$ 沿树上的简单路径走到点 $v$。每经过一个点 $p$（包括起点和终点），他都会按照上述规则将 $a_p$ 加入集合 $S$。

请你求出操作结束后，集合 $S$ 中有多少个数不超过 $k$。

更形式化地，设从 $u$ 到 $v$ 的简单路径依次经过

$$b_1,b_2,\ldots,b_l,$$

其中 $b_1=u$、$b_l=v$。集合 $S$ 初始为空，依次按照上述规则加入

$$a_{b_1},a_{b_2},\ldots,a_{b_l}.$$

询问采用强制在线方式，具体规则见输入格式。

输入格式

第一行输入三个整数 $n,m,T$，分别表示树的点数、询问次数和强制在线参数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各点的权值。

接下来 $n-1$ 行，每行输入两个整数 $x_i,y_i$，表示树中存在一条连接点 $x_i$ 和点 $y_i$ 的边。

接下来 $m$ 行，每行输入三个整数 $u',v',k'$。本次询问的真实参数由下式得到：

$$\begin{aligned} u &= u'\mathbin{\mathrm{xor}}(\mathrm{las}\times T),\\ v &= v'\mathbin{\mathrm{xor}}(\mathrm{las}\times T),\\ k &= k'\mathbin{\mathrm{xor}}(\mathrm{las}\times T), \end{aligned}$$

其中 $\mathrm{xor}$ 表示按位异或，$\mathrm{las}$ 表示上一次询问的答案。第一次询问前令 $\mathrm{las}=0$。

输出格式

输出 $m$ 行，每行一个整数，表示对应询问的答案。

样例

7 6 0
2 3 4 1 5 2 1
1 3
6 3
7 1
2 3
5 6
3 4
4 7 5
2 5 6
3 3 4
1 4 6
5 4 10
7 6 4

3
4
1
3
4
3

样例解释

第一次询问中，小 T 经过的路径为

$$4\to3\to1\to7,$$

经过的点权依次为 $1,4,2,1$，集合 $S$ 的变化过程为

$$\varnothing \to\{1\} \to\{1,4\} \to\{1,2,5\} \to\{1,2,3,6\}.$$

最终集合中有 $3$ 个不超过 $5$ 的数，因此答案为 $3$。

第二次询问结束后，集合 $S$ 为 $\{2,4,5,6\}$，因此答案为 $4$。

数据范围

• 对于 $15\%$ 的测试数据，$n,m,a_i,k\le500$；
• 对于 $30\%$ 的测试数据，$n,a_i,k\le500$；
• 对于另外 $15\%$ 的测试数据，$x_i=i$、$y_i=i+1$；
• 对于另外 $15\%$ 的测试数据，$a_i\le5$；
• 对于另外 $20\%$ 的测试数据，$T=0$；
• 对于全部测试数据：

$$1\le n\le2\times10^5, \qquad 1\le m\le10^5, \qquad T\in\{0,1\},$$$$1\le a_i,k\le2\times10^5, \qquad 1\le x_i,y_i,u,v\le n.$$

保证给出的边构成一棵树，且解码后的询问参数合法。