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

Over the next few days, Little F replicates this tree $m-1$ times and arranges them in a row, resulting in $m$ identical trees. The node $x$ in the $k$-th tree is numbered $(k-1)\times n+x$. For convenience, we denote the node numbered $(k-1)\times n+x$ as the tuple $(k,x)$.

There are $q$ spiders in Little F's yard. For any $1\le k < m$ and $1\le x\le n$, these spiders connect node $(k,x)$ to $(k+1,x)$ with a strand of spider silk.

Due to the varying heights and fragility of each node, the lengths of these silk strands may differ. However, since the trees are identical and the distance between adjacent trees is uniform, for any $1\le k_1,k_2 < m$ and $1\le x\le n$, the length of the silk strand connecting $(k_1,x)$ to $(k_1+1,x)$ is equal to the length of the silk strand connecting $(k_2,x)$ to $(k_2+1,x)$.

Thus, we can describe these silk strands using a sequence $a_1, a_2, \ldots, a_n$, where $a_x$ represents the length of the silk strand connecting $(k,x)$ to $(k+1,x)$ for any $1\le k < m$.

To test their progress, the spiders hold a tree-climbing competition. The $j$-th spider needs to travel from node $s_j$ to node $t_j$ using the tree edges and the silk strands.

You need to help the spiders calculate the shortest path length for each spider.

Input

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, describing the lengths of the silk strands.

The next $n-1$ lines each contain three integers $u_i, v_i, w_i$, describing the $i$-th edge.

The next $q$ lines each contain two integers $s_j, t_j$, representing the starting and ending nodes of the $j$-th spider.

Output

Output $q$ lines, each containing an integer representing the shortest path length for the $j$-th spider.

Examples

Input 1

4 3 2
4 3 3 5
1 2 2
2 4 1
3 2 4
12 3
7 9

Output 1

11
9

Note 1

The structure formed by the $3$ trees and the silk strands is as follows (black lines represent tree edges, blue lines represent silk strands):

One shortest path for the $1$st spider is shown by the red arrowed path:

One shortest path for the $2$nd spider is shown by the red arrowed path:

Constraints

• Subtask $1\ (3\text{ pt})$: $n\le 100, m\le 100, q\le 1000$
• Subtask $2\ (5\text{ pt})$: $n, q\le 5000$
• Subtask $3\ (11\text{ pt})$: $m\le 20$
• Subtask $4\ (12\text{ pt})$: The tree is a chain
• Subtask $5\ (9\text{ pt})$: The tree is a star graph
• Subtask $6\ (22\text{ pt})$: $s_j=1$
• Subtask $7\ (18\text{ pt})$: $n, q\le 5\times 10^4$
• Subtask $8\ (20\text{ pt})$: No additional constraints

For $100\%$ of the data, $1\le n, q\le 2\times 10^5, 1\le m\le 10^9, 1\le a_x\le 10^9, 1\le w_i\le 10^{12}, 1\le u_i, v_i\le n, 1\le s_j, t_j\le n\times m$.