题目描述

小 C 正在设计计算机网络中的路由系统。

测试用的网络总共有$n$台主机，依次编号为$1 \sim n$。这$n$台主机之间由$n- 1$根网线连接，第$i$条网线连接个主机$a_i$和$b_i$。保证任意两台主机可以通过有限根网线直接或者间接地相连。受制于信息发送的功率，主机$a$能够直接将信息传输给主机$b$当且仅当两个主机在可以通过不超过$k$根网线直接或者间接的相连。

在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机$a$传输到主机$b$（$a \neq b$），则其会选择出若干台用于传输的主机$c_1 = a, c_2, \ldots, c_{m - 1}, c_m = b$，并按照如下规则转发：对于所有的$1 \le i < m$，主机$c_i$将信息直接发送给$c_{i + 1}$。

每台主机处理信息都需要一定的时间，第$i$台主机处理信息需要$v_i$单位的时间。数据在网络中的传输非常迅速，因此传输的时间可以忽略不计。据此，上述传输过程花费的时间为$\sum_{i = 1}^{m} v_{c_i}$。

现在总共有$q$次数据发送请求，第$i$次请求会从主机$s_i$发送数据到主机$t_i$。小 C 想要知道，对于每一次请求至少需要花费多少单位时间才能完成传输。

输入格式

输入的第一行包含三个正整数$n, Q, k$，分别表示网络主机个数，请求个数，传输参数。数据保证$1 \le n \le 2 \times {10}^5$，$1 \le Q \le 2 \times {10}^5$，$1 \le k \le 3$。

输入的第二行包含$n$个正整数，第$i$个正整数表示$v_i$，保证$1 \le v_i \le {10}^9$。

接下来$n - 1$行，第$i$行包含两个正整数$a_i, b_i$，表示一条连接主机$a_i, b_i$的网线。保证$1 \le a_i, b_i \le n$。

接下来$Q$行，第$i$行包含两个正整数$s_i, t_i$，表示一次从主机$s_i$发送数据到主机$t_i$的请求。保证$1 \le s_i, t_i \le n，s_i \ne t_i$。

输出格式

$Q$行，每行一个正整数，表示第$i$次请求在传输的时候至少需要花费多少单位的时间。

输入输出样例

7 3 3
1 2 3 4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7
4 7
5 6
1 2

12
12
3

样例 1 解释

对于第一组请求，由于主机$4, 7$之间需要至少$4$根网线才能连接，因此数据无法在两台主机之间直接传输，其至少需要一次转发；我们让其在主机$1$进行一次转发，不难发现主机$1$和主机$4, 7$之间都只需要两根网线即可连接，且主机$1$的数据处理时间仅为$1$，为所有主机中最小，因此最少传输的时间为$4 + 1 + 7 = 12$。

对于第三组请求，由于主机$1, 2$之间只需要$1$根网线就能连接，因此数据直接传输就是最优解，最少传输的时间为$1 + 2 = 3$。

数据规模与约定

对于所有的测试数据，满足$1 \le n \le 2 \times {10}^5$，$1 \le Q \le 2 \times {10}^5$，$1 \le k \le 3$，$1 \le a_i$, $b_i \le n$，$1 \le s_i, t_i \le n,s_i \ne t_i$。

特殊性质：保证$a_i = i + 1$，而$b_i$则从$1, 2, \ldots, i$中等概率选取。