Background

As a qualified freight company, you need to deliver goods while spending as little money as possible.

Problem Description

This city has $n$ locations, and there are $m$ edges between these $n$ locations.
The freight company has received $o$ orders, and they need to minimize the money spent along the route.

For each road, there are three pieces of information:

• $a, b$ mean the road connects from $a$ to $b$;
• $t$ means how much money this road costs.

For each order, $a$ and $b$ are given, meaning you need to transport goods from $a$ to $b$. For each order, find the minimum money needed; if it cannot be delivered, output $-1$.

In particular, for a road with endpoints numbered $a, b$, it is guaranteed that:

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

($k$ is a given constant).

Input Format

The first line contains four integers $k, n, m, o$, representing a constant, the number of locations, the number of edges, and the number of orders.
The locations are numbered from $0$ to $n - 1$.

The next $m$ lines each contain three integers $a, b, t$, meaning that it costs $t$ to go from $a$ to $b$. It is guaranteed that $\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$, and between any two locations there is at most $1$ edge.

The next $o$ lines each contain two integers $a, b$, meaning you need to transport goods from $a$ to $b$.

Output Format

For each order, output one integer per line representing the answer.

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

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (7 pts): $k = 1$.
• Subtask 2 (10 pts): For every order, $a = 0$.
• Subtask 3 (8 pts): $o \le 100$.
• Subtask 4 (31 pts): $o \le 3000$.
• Subtask 5 (44 pts): No special constraints.

For $100\%$ of the testdata, $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$.

Notes

Translated from BOI 2017 D1 T3 Toll.
Translator: @一只书虫仔。
This problem enforces $O2$ optimization.

Translated by ChatGPT 5