spiderclimb

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	11 9