题目描述

小 F 在自家院子里种了一棵 $n$ 个节点的树。节点编号为 $1$ 到 $n$。有 $n-1$ 条边将这些节点连接起来，第 $i$ 条边连接节点 $u_i$ 与节点 $v_i$，长度为 $w_i$。

接下来的几天中，小 F 将这棵树复制了 $m-1$ 份并排成一排，于是他拥有了 $m$ 棵完全相同的树。第 $k$ 棵树节点 $x$ 的编号为 $(k-1)\times n+x$。为方便叙述，下面用二元组 $(k,x)$ 表示编号为 $(k-1)\times n+x$ 的节点。

小 F 的院子里有 $q$ 只蜘蛛。这些蜘蛛会对于任意 $1\le k < m,1\le x\le n$，用一条蛛丝将 $(k,x)$ 与 $(k+1,x)$ 连接起来。

由于每个节点的高度和脆弱程度不同，这些蛛丝之间可能会有长短。但是由于这些树完全相同，且相邻树之间的距离相同，所以对于任意 $1\le k_1,k_2 < m,1\le x\le n$，连接 $(k_1,x)$ 与 $(k_1+1,x)$ 的蛛丝长度等于连接 $(k_2,x)$ 与 $(k_2+1,x)$ 的蛛丝长度。

于是我们可以用一个序列 $a_1,a_2,\ldots,a_n$ 来描述这些蛛丝，其中 $a_x$ 表示对于任意 $1\le k < m$，连接 $(k,x)$ 与 $(k+1,x)$ 的蛛丝长度。

为了检验成果，蜘蛛们展开了一场爬树比赛。第 $j$ 只蜘蛛要从节点 $s_j$ 沿树边和蛛丝爬到节点 $t_j$。

你需要帮蜘蛛们算一算，每只蜘蛛的最短路径长度。

输入格式

第一行三个整数 $n,m,q$，分别表示每棵树的节点树、树的数量和蜘蛛数量。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$，描述蛛丝长度。

接下来 $n-1$ 行，第 $i$ 行三个整数 $u_i,v_i,w_i$，描述第 $i$ 条边。

接下来 $q$ 行，第 $j$ 行两个整数 $s_j,t_j$，表示第 $j$ 只蜘蛛的起点和终点。

输出格式

输出 $q$ 行，第 $j$ 行一个整数，表示第 $j$ 只蜘蛛的最短路径长度。

样例

输入

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

输出

11
9

$3$ 棵树与蛛丝形成的结构如下（黑线表示树边，蓝线表示蛛丝）：

（此处应有图示）

数据范围与提示

子任务 1（3 分）：$n\le 100,m\le 100,q\le 1000$
子任务 2（5 分）：$n,q\le 5000$
子任务 3（11 分）：$m\le 20$
子任务 4（12 分）：树是一条链
子任务 5（9 分）：树是一个菊花
子任务 6（22 分）：$s_j=1$
子任务 7（18 分）：$n,q\le 5\times 10^4$
子任务 8（20 分）：无附加限制

对于 $100\%$ 的数据：

• $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$