题目描述

题目译自 BalticOI 2017 Day1「Toll」

作为一个合格的货运公司，在送达货物的同时也要让花的钱最少。
这座城市有 $n$ 个地点，这 $n$ 个地点之间有 $m$ 条边。
货运公司接到了 $o$ 个订单，他们要想方设法的让路途中花的钱最少。
对于每条路，都有三个信息：

• $a$, $b$ 代表从 $a$ 到达 $b$，并且是单向的；
• $t$ 代表这条路需要多少钱。

并且对于每个订单，都给出 $a$ 和 $b$ 代表要把物品从 $a$ 运到 $b$，求每个订单需要花的最少的钱；如果无法送达就输出 $-1$。

特别的，对于从 $a$ 到 $b$ 的路，一定满足：

$$\left\lfloor \frac{b}{k} \right\rfloor = 1 + \left\lfloor \frac{a}{k} \right\rfloor $$

其中 $k$ 是一个给定的常数。

---

输入格式

第一行四个整数 $k, n, m, o$ 代表一个常数，地点的个数，边的个数，订单的个数。
点的编号为从 $0$ 到 $n - 1$。
接下来 $m$ 行每行三个整数 $a, b, t$ 代表从 $a$ 连向 $b$ 要花费 $t$，保证满足

$$\left\lfloor \frac{b}{k} \right\rfloor = 1 + \left\lfloor \frac{a}{k} \right\rfloor $$

并且两点之间连接的边数不超过 $1$ 条边。
接下来 $o$ 行每行两个整数 $a, b$ 代表要从 $a$ 运货到 $b$。

---

输出格式

对于每个订单，输出一行一个整数表示答案。

---

样例

输入

5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13

输出

15
9
7
8
-1

---

数据范围与提示

对于 $100\%$ 的数据，
$1 \le n \le 50000$，
$1 \le o \le 10000$，
$1 \le k \le 5$，
$0 \le a < b < n$，
$1 \le t \le 10000$。

详细子任务与附加限制如下：

• Subtask 1（$7$ 分）：$k=1$。
• Subtask 2（$10$ 分）：每个订单中的 $a=0$。
• Subtask 3（$8$ 分）：$o \le 100$。
• Subtask 4（$31$ 分）：$o \le 3000$。
• Subtask 5（$44$ 分）：无特殊限制。