Description

Xiao C is designing a routing system for a computer network.

The test network has $n$ hosts, numbered $1 \sim n$. These $n$ hosts are connected by $n - 1$ network cables; the $i$-th cable connects hosts $a_i$ and $b_i$. It is guaranteed that any two hosts are connected directly or indirectly through a finite number of cables. Due to transmission power limits, host $a$ can directly send information to host $b$ if and only if the two hosts are connected directly or indirectly by a path that uses at most $k$ cables.

In a computer network, data transmission often requires several forwards. Suppose Xiao C needs to send data from host $a$ to host $b$ ($a \ne b$). He will choose several hosts for transmission $c_1 = a, c_2, \ldots, c_{m - 1}, c_m = b$, and forward as follows: for all $1 \le i < m$, host $c_i$ directly sends information to $c_{i + 1}$.

Each host needs some time to process information. The $i$-th host needs $v_i$ units of time. Data transmission in the network is very fast, so the transmission time can be ignored. Therefore, the total time cost of the above process is $\sum_{i = 1}^{m} v_{c_i}$.

There are $Q$ data sending requests in total. In the $i$-th request, data is sent from host $s_i$ to host $t_i$. Xiao C wants to know, for each request, the minimum number of time units needed to complete the transmission.

Input Format

The first line contains three positive integers $n, Q, k$, denoting the number of hosts, the number of requests, and the transmission parameter, respectively. It is guaranteed that $1 \le n \le 2 \times {10}^5$, $1 \le Q \le 2 \times {10}^5$, $1 \le k \le 3$.

The second line contains $n$ positive integers; the $i$-th integer is $v_i$, and it is guaranteed that $1 \le v_i \le {10}^9$.

The next $n - 1$ lines; the $i$-th line contains two positive integers $a_i, b_i$, indicating a network cable connecting hosts $a_i$ and $b_i$. It is guaranteed that $1 \le a_i, b_i \le n$.

The next $Q$ lines; the $i$-th line contains two positive integers $s_i, t_i$, indicating a request to send data from host $s_i$ to host $t_i$. It is guaranteed that $1 \le s_i, t_i \le n$ and $s_i \ne t_i$.

Output Format

Output $Q$ lines. Each line contains one positive integer, the minimum number of time units needed to complete the $i$-th request.

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

Hint

【Sample Explanation #1】

For the first request, since hosts $4$ and $7$ require at least $4$ cables to connect, data cannot be transmitted directly between the two hosts, so at least one forward is required. Let it be forwarded once at host $1$. It is easy to see that both host $4$ and host $7$ are within two cables from host $1$, and host $1$ has a processing time of only $1$, the minimum among all hosts. Therefore, the minimum transmission time is $4 + 1 + 7 = 12$.

For the third request, since hosts $1$ and $2$ are connected by only $1$ cable, direct transmission is optimal, and the minimum transmission time is $1 + 2 = 3$.

【Sample #2】

See the attachments transmit/transmit2.in and transmit/transmit2.ans.

This sample satisfies the limits of test point $2$.

【Sample #3】

See the attachments transmit/transmit3.in and transmit/transmit3.ans.

This sample satisfies the limits of test point $3$.

【Sample #4】

See the attachments transmit/transmit4.in and transmit/transmit4.ans.

This sample satisfies the limits of test point $20$.

Constraints

For all testdata, it is guaranteed that $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$, and $s_i \ne t_i$.

Special property: it is guaranteed that $a_i = i + 1$, and $b_i$ is chosen uniformly at random from $1, 2, \ldots, i$.

Translated by ChatGPT 5