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

The network consists of $n$ hosts, numbered $1$ to $n$. These $n$ hosts are connected by $n-1$ network cables, where 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 power limitations, host $a$ can transmit information directly to host $b$ if and only if the two hosts are connected by a path of at most $k$ cables.

In a computer network, data transmission often requires several relays. Suppose Little C needs to transmit data from host $a$ to host $b$ ($a \neq b$). He will select a sequence of hosts for transmission $c_1 = a, c_2, \dots, c_{m-1}, c_m = b$, and forward the data according to the following rule: for all $1 \le i < m$, host $c_i$ sends the information directly to $c_{i+1}$.

Each host requires a certain amount of time to process information; the $i$-th host requires $v_i$ units of time. Data transmission in the network is very fast, so the transmission time itself is negligible. Based on this, the time taken for the above transmission process is $\sum_{i=1}^m v_{c_i}$.

There are $q$ data transmission requests in total. The $i$-th request is to send data from host $s_i$ to host $t_i$. Little C wants to know the minimum time required to complete the transmission for each request.

Input

Read data from the file transmit.in.

The first line contains three positive integers $n, Q, k$, representing 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$, and $1 \le k \le 3$.

The second line contains $n$ positive integers, where the $i$-th integer represents $v_i$. It is guaranteed that $1 \le v_i \le 10^9$.

The next $n-1$ lines each contain two positive integers $a_i, b_i$, representing 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 each contain two positive integers $s_i, t_i$, representing 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 \neq t_i$.

Output

Output to the file transmit.out.

The output should contain $Q$ lines, each containing a single positive integer representing the minimum time required for the $i$-th request.

Examples

Input 1

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

Output 1

12
12
3

Note

For the first request, since at least 4 cables are needed to connect host 4 and host 7, data cannot be transmitted directly between the two hosts; it requires at least one relay. If we let host 1 perform a relay, it is easy to see that host 1 only needs two cables to connect to host 4 and host 7 respectively, and the processing time of host 1 is only 1, which is the minimum among all hosts. Therefore, the minimum transmission time is $4 + 1 + 7 = 12$.

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

Examples 2-4

See the files transmit/transmit2.in and transmit/transmit2.ans, transmit/transmit3.in and transmit/transmit3.ans, and transmit/transmit4.in and transmit/transmit4.ans in the contestant's directory. These examples satisfy the constraints of test cases 2, 3, and 20, respectively.

Constraints

For all test data, $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 \neq t_i$.

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