### Spiders Climbing Trees

Xiao F has planted a tree with $$n$$ nodes in his yard. The nodes are numbered 1 through $$n$$. There are $$n - 1$$ edges connecting these nodes, and the $$i^{th}$$ edge connects node $$u_i$$ to node $$v_i$$, and has length $$w_i$$.

Over the next few days, Xiao F makes $$m - 1$$ copies of this tree and arranges them in a row, so that he has $$m$$ identical trees. The $$x^{th}$$ node of the $$k^{th}$$ tree node is numbered $$(k - 1) * n + x$$. For convenience, each node numbered $$(k - 1) * n + x$$ will be denoted by the pair $$(k, x)$$ below.

Xiao F also has $$q$$ spiders in his yard. These spiders will connect nodes $$(k, x)$$ to $$(k + 1, x)$$ with a thread of spider silk, for any $$1 \leq k < m$$, $$1 \leq x \leq n$$.

Since each node has a different height and position, the lengths of thread between different nodes may differ. But since these trees are identical and the distances between neighboring trees are the same, for any $$1 \leq k_1, k_2 < m, 1 \leq x \leq n$$, the length of the spider silk connecting $$(k_1, x)$$ to $$(k_1 + 1, x)$$ is equal to the length of the spider silk connecting $$(k_2, x)$$ to $$(k_2 + 1, x)$$.

So we can describe these threads with a sequence $$a_1, a_2, \ldots, a_n$$, where $$a_x$$ denotes the lengths of the threads connecting $$(k, x)$$ and $$(k + 1, x)$$ for any $$1 \leq k < m$$.

To test the results, the spiders have a tree-climbing competition. The $$j^{th}$$ spider has to climb from node $$s_j$$ to node $$t_j$$ along the edges of the tree and on the spider silk threads.

Help the spiders to calculate each of their shortest path lengths.

### Limits

$$1 \leq n, q \leq 2 * 10^5$$, $$1 \leq m \leq 10^9$$, $$1 \leq a_x \leq 10^9$$, $$1 \leq w_i \leq 10^{12}$$, $$1 \leq u_i, v_i \leq n, 1 \leq s_j, t_j \leq n * m$$.

Subtask # Score Constraints
1 3 $$n \leq 100, m \leq 100, q \leq 1000$$
2 5 $$n, q \leq 5000$$
3 11 $$m \leq 20$$
4 12 The tree is a line graph.
5 9 The tree is a star graph.
6 22 $$s_j = 1$$
7 18 $$n, q \leq 5 * 10^4$$
8 20 No additional constraints

### Input format

The first line of input contains 3 integers $$n$$, $$m$$, and $$q$$, representing the number of nodes in each tree, the number of trees, and the number of spiders.

The second line of input contains $$n$$ integers $$a_1, a_2, \ldots, a_n$$, the lengths of the spider silk threads.

The next $$n - 1$$ lines of input contain 3 integers each $$u_i, v_i, w_i$$, describing an edge of the trees.

The next $$q$$ lines of input data contain 2 integers each $$s_j, t_j$$, representing the starting and ending points of the $$j^{th}$$ spider.

### Output format

Output $$q$$ lines each containing a single integer $$d_j$$ - the shortest path length of the $$j^{th}$$ spider.

### Samples

 Sample Input 1 Sample Output 1 4 3 2 4 3 3 5 1 2 2 2 4 1 3 2 4 12 3 7 9  119

### Compile Errors

Time Limit: 8 Seconds
Memory Limit: 1024MB
No. of ACs: 2
Your best score: 0
Source: LOJ #3661