Baltic Olympiad in Informatics: 2017 Day 1, Problem 2

A trucking company wants to optimize its internal processes—which mainly means saving money. The company serves a region where a toll must be paid for every single street. Each street connects two places (cities, villages etc.) directly. The company serves a set of orders; each order tells them to carry goods from one place to another. When serving an order, the company wants to pay the minimum overall toll. As the region's street network can be modeled by a graph where each edge has a specific cost (the toll for the respective street), the company actually wants to know (the cost of) the cheapest path between two nodes in this graph.

However, the region's street network graph has an interesting property: it is directed (i.e. all streets are oneway), and there can only be an edge from ~a~ to ~b~ if ~\left\lfloor\frac b K\right\rfloor = 1 + \left\lfloor\frac a K\right\rfloor~ (for some constant ~K~).

Write a program that for each of a given list of orders outputs the minimum toll the company has to pay to serve the respective order.

Input Specification

The first line contains four integers: ~K~ (with the meaning described above), ~N~ (the number of places), ~M~ (the number of streets), and ~O~ (the number of orders).

Each of the next ~M~ lines contains three integers ~a~, ~b~, ~t~ (~0 \le a, b < N~). This means that there is a (oneway) street from ~a~ to ~b~ with toll ~t~. You are guaranteed that ~\left\lfloor\frac b K\right\rfloor = 1 + \left\lfloor\frac a K\right\rfloor~ is satisfied, and that no two locations are connected by more than one street.

Finally ~O~ lines follow, each containing two integers ~a~, ~b~: this means that there is an order to carry goods from place ~a~ to place ~b~.

Constraints

We always have ~1 \le N \le 50\,000~, ~1 \le O \le 10\,000~ and ~K \le 5~. Moreover, we have ~0 \le a < b < N~ for all orders ~a~, ~b~ and ~1 \le t \le 10\,000~ for all tolls ~t~. For subcases, the inputs have these further restrictions:

• Group 1: 7 points ~K = 1~
• Group 2: 10 points All orders have ~a = 0~
• Group 3: 8 points ~O \le 100~
• Group 4: 31 points ~O \le 3\,000~
• Group 5: 44 points No further restrictions

Output Specification

Your output should consist of ~O~ lines, each with one integer. The ~i~-th line should contain the toll on a cheapest path between the two places in order ~i~. If no such path exists, output -1 in this line.

Sample 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

Sample Output

15
9
7
8
-1