Minimum Cost Shipping

We are given a directed graph with (n) nodes and (m) edges. Each edge has three values: (a, b, t) which denotes a directed edge from node (a) to node (b) with cost (t). There are (o) shipping orders. For each order, you are given two nodes (a) and (b) and you need to find the minimum cost required to ship goods from (a) to (b). If it is impossible, output (-1).

Special Property: For every edge, the endpoints satisfy the following relationship: [ \left\lfloor \frac{b}{k} \right\rfloor = 1 + \left\lfloor \frac{a}{k} \right\rfloor ] where (k) is a given constant.

inputFormat

The first line contains four integers (n), (m), (o), and (k).

Then follow (m) lines, each containing three integers (a), (b) and (t), representing a directed edge from (a) to (b) with cost (t).

Then follow (o) lines, each containing two integers (a) and (b) representing a shipping order from (a) to (b).

outputFormat

For each shipping order, output the minimum cost required to ship goods from (a) to (b). If there is no valid route, output (-1). Each answer should be printed on a new line.

sample

6 4 2 3
0 3 5
0 4 10
3 5 2
4 5 1
0 5
0 2

7
-1