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

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

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

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

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

输入的第一行包含三个正整数 n,Q,k，分别表示网络主机个数，请求个数，传输参数。数据保证 1≤n≤2×$10^5$，1≤Q≤2×$10^5$，1≤k≤3。
输入的第二行包含 n 个正整数，第 i 个正整数表示$v_i$ ，保证 1≤$v_i$≤$10^9$。
接下来 n−1 行，第 i 行包含两个正整数$a_i$，$b_i$，表示一条连接主机$a_i$，$b_i$的网线。保证 1≤$a_i$，$b_i$≤n。
接下来 Q 行，第 i 行包含两个正整数$s_i$，$t_i$,表示一次从主机$s_i$发送数据到主机$t_i$的请求。保证1≤$s_{i},t_{i}$≤n，$s_i$≠$t_i$。

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

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

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

对于所有的测试数据，满1≤n≤2*$10^5$，1≤Q≤2*$10^5$，1≤k≤3,1≤$a_{i},b_{i}$≤n,1≤$s_{i},t_{i}$≤n,$s_i$≠$t_i$。

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

CSP