Person in Charge

• SleepingCup

Attention

The memory limit for this problem is 1024 MB.

Problem Description

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

The test network consists of $n$ hosts numbered from $1$ to $n$ in sequence. These $n$ hosts are connected by $n-1$ network cables, where the $i$-th cable connects host $a_i$ and host $b_i$. It is guaranteed that any two hosts can be connected directly or indirectly through a finite number of network cables. Restricted by the transmission power of information, a host $a$ can transmit information directly to a host $b$ if and only if the two hosts are connected by no more than $k$ network cables directly or indirectly.

In computer networks, data transmission often requires several forwarding steps. 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, \ldots, 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 host $c_{i+1}$.

Each host requires a certain amount of time to process information, and the $i$-th host takes $v_i$ units of time for processing. Data transmission in the network is extremely fast, so the transmission time is negligible. Thus, the time taken for the above transmission process is $\sum_{i = 1}^{m} v_{c_i}$.

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

Input Format

The first line of input contains three positive integers $n, Q, k$, representing the number of hosts in the network, the number of requests, and the transmission parameter respectively. The data guarantees $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, where the $i$-th integer denotes $v_i$, with the constraint $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 host $a_i$ and host $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 Format

Output $Q$ lines, each with a positive integer representing the minimum time required for the $i$-th transmission request.

Samples

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

Sample (1) Explanation

For the first request, since at least 4 network cables are required to connect host $4$ and host $7$, data cannot be transmitted directly between the two hosts and requires at least one forwarding step. We choose to forward the data at host $1$. It is easy to find that host $1$ is connected to both host $4$ and host $7$ with only two network cables, and the data 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 one network cable, direct transmission of data is the optimal solution, with a minimum transmission time of $1 + 2 = 3$.

Sample (2)

See transmit/transmit2.in and transmit/transmit2.ans in the contestant's directory.

This sample satisfies the constraints of Test Case 2.

Sample (3)

See transmit/transmit3.in and transmit/transmit3.ans in the contestant's directory.

This sample satisfies the constraints of Test Case 3.

Sample (4)

See transmit/transmit4.in and transmit/transmit4.ans in the contestant's directory.

This sample satisfies the constraints of Test Case 20.

Data Range

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

Special Property: It is guaranteed that $a_i = i + 1$, and $b_i$ is randomly selected from $1, 2, \ldots, i$ with equal probability.