小 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, \cdots, 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\) 次请求在传输的时候至少需要花费多少单位的时间。

样例1解释

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

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

样例2

见附件中的 transmit/transmit2.in 与 transmit/transmit2.ans。

该样例满足测试点 \(2\) 的限制。

样例3

见附件中的 transmit/transmit3.in 与 transmit/transmit3.ans。

该样例满足测试点 \(3\) 的限制。

样例4

见附件中的 transmit/transmit4.in 与 transmit/transmit4.ans。

该样例满足测试点 \(20\) 的限制。

数据范围

对于所有的测试数据，满足 \(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, \cdots, i\) 中等概率选取。