CC-BY-SA-3.0, Wikimedia Commons

一家货运公司希望优化其内部流程，这主要意味着节省开支。该公司服务的区域内，每经过一条街道都必须支付通行费。每条街道直接连接两个地点（城市、村庄等）。公司承接一系列订单；每个订单要求将货物从一个地点运送到另一个地点。在执行订单时，公司希望支付的通行费总额最小。由于该区域的街道网络可以建模为一个图，其中每条边都有特定的成本（即相应街道的通行费），因此公司实际上想要知道该图中两个节点之间最便宜路径的成本。

然而，该区域的街道网络图具有一个有趣的特性：它是单向的（即所有街道都是单行道），并且只有当 $\lfloor b/K \rfloor = 1 + \lfloor a/K \rfloor$（对于某个常数 $K$）时，才可能存在从 $a$ 到 $b$ 的边。

请编写一个程序，针对给定的订单列表，输出公司为完成相应订单所必须支付的最小通行费。

输入格式

第一行包含四个整数：$K$（具有上述含义）、$N$（地点数量）、$M$（街道数量）和 $O$（订单数量）。

接下来的 $M$ 行，每行包含三个整数 $a, b, t$ ($0 \le a, b < N$)。这意味着存在一条从 $a$ 到 $b$ 的（单向）街道，通行费为 $t$。保证满足 $\lfloor b/K \rfloor = 1 + \lfloor a/K \rfloor$，且任意两个地点之间最多只有一条街道相连。

最后 $O$ 行，每行包含两个整数 $a, b$：这意味着有一个从地点 $a$ 到地点 $b$ 的运货订单。

数据范围

我们始终有 $1 \le N \le 50\,000$，$1 \le O \le 10\,000$ 且 $K \le 5$。此外，对于所有订单 $a, b$，满足 $0 \le a < b < N$，且对于所有通行费 $t$，满足 $1 \le t \le 10\,000$。对于子任务，输入具有以下进一步限制：

• 子任务 1：7 分，$K = 1$
• 子任务 2：10 分，所有订单均满足 $a = 0$
• 子任务 3：8 分，$O \le 100$
• 子任务 4：31 分，$O \le 3\,000$
• 子任务 5：44 分，无其他限制

输出格式

输出应包含 $O$ 行，每行一个整数。第 $i$ 行应包含订单 $i$ 中两个地点之间最便宜路径的通行费。如果不存在这样的路径，则在该行输出 $-1$。

样例

输入格式 1

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

输出格式 1

15
9
7
8
-1