Computer Network Routing

In this problem, we consider a computer network that consists of (n) hosts numbered from (1) to (n). The hosts are connected by (n-1) cables such that the network is a tree. The (i)-th cable connects host (a_i) and (b_i). Since the network is a tree, any two hosts are connected by a unique simple path.

A host (a) can directly transmit information to host (b) if and only if the two hosts are connected by a path using no more than (k) cables. When transmitting data from a source host (s) to a target host (t) (with (s \neq t)), a sequence of hosts (c_1=s, c_2, \ldots, c_m=t) is chosen such that for each consecutive pair ((c_i, c_{i+1})) the two hosts are within (k) hops (i.e. connected by at most (k) cables).

Each host (i) takes (v_i) units of time to process the information. The transmission time between hosts is negligible. Hence, the total time taken for the transmission is given by (\sum_{i=1}^{m} v_{c_i}).

You are given (q) queries. In the (i)-th query, data needs to be sent from host (s_i) to host (t_i). For each query, determine the minimum time required to complete the transmission.

inputFormat

The first line contains two integers (n) and (k) separated by a space.

The second line contains (n) integers (v_1, v_2, \ldots, v_n), where (v_i) is the processing time at host (i).

Each of the next (n-1) lines contains two integers (a_i) and (b_i), indicating that there is a cable connecting host (a_i) and host (b_i).

The next line contains an integer (q), representing the number of queries.

Each of the following (q) lines contains two integers (s_i) and (t_i), representing a data transmission query from host (s_i) to host (t_i).

outputFormat

For each query, print one line containing one integer — the minimum total processing time required to transmit the data from the source to the target host.

sample

5 1
1 2 3 4 5
1 2
2 3
3 4
4 5
2
1 5
2 4

15
9