每个体面的比赛都必须有一道教科书般的图论题。没有复杂的流程，没有奇怪的观察；只有纯粹、硬核的算法。幸运的是，你刚刚找到了它！

上图展示了样例测试数据。

给你一个拥有 $n$ 个顶点和 $m$ 条边的无向带权图，以及 $q$ 个形如 $(a_i, b_i)$ 的询问。对于每个询问，求顶点 $a_i$ 和 $b_i$ 之间的最短路径长度。

输入格式

输入包含 $m + q + 1$ 行。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n \le 100\,000$，$1 \le m \le 200\,000$，$1 \le q \le 25\,000$）。

接下来的 $m$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $w_i$，表示顶点 $u_i$ 和 $v_i$ 之间有一条长度为 $w_i$ 的无向边（$1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$）。

最后 $q$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$）。

任意两个顶点之间最多只有一条边，且不存在连接顶点自身的自环。

此外，保证所有 $m$ 条边 $u_i, v_i$ 都满足 $|u_i - v_i| \le 10$。

输出格式

输出 $q$ 行。第 $i$ 行应包含一个正整数，表示连接第 $i$ 个询问中两个顶点的最短路径长度。如果不存在这样的路径，则针对该询问输出 $-1$。

样例

输入样例 1

6 5 3
1 3 7
3 4 5
1 4 1
2 5 10
2 6 12
6 5
1 3
1 5

输出样例 1

22
6
-1