题目描述

题目译自 BalticOI 2017 Day1「Toll」

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

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

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

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

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

输入格式

第一行四个整数 $k,n,m,o$ 代表一个常数，地点的个数，边的个数，订单的个数。
点的编号为从 $0$ 到 $n - 1$。
接下来 $m$ 行每行三个整数 $a,b,t$ 代表从 $a$ 连向 $b$ 要花费 $t$，保证满足 $\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$，并且两点之间连接的边数不超过 $1$ 条边。
接下来 $o$ 行每行两个整数 $a,b$ 代表要从 $a$ 运货到 $b$。

输出格式

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

样例

input

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

output

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