题目描述

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

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

在计算机网络中，数据的传输往往需要通过若干次转发。假定小 C 需要将数据从主机 $a$ 传输到主机 $b$（$a \neq b$），则其会选择出若干台用于传输的主机 $c_1 = a, c_2, \ldots, c_{m-1}, c_m = b$，并按照如下规则转发：对于所有的 $1 \leq 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 \neq 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 ≤ n ≤ 2×10⁵，1 ≤ Q ≤ 2×10⁵，1 ≤ k ≤ 3，1 ≤ aᵢ, bᵢ ≤ n，1 ≤ aᵢ, tᵢ ≤ n，aᵢ ≠ tᵢ。