DRIVEME

Suppose we are given a map consisting of ~N~ locations and ~M~ one-way roads connecting these locations. For each road from location ~u~ to location ~v~, its length ~d_{u,v}~ is known. We want to create a navigation support system that provides directions to drivers on how to get from one location to another. Specifically, we are interested in finding the length of the shortest path from one location to another.

Under normal conditions, cars move as indicated by the direction of the roads. However, sometimes drivers violate traffic rules and drive in the opposite direction on roads! This is, of course, illegal and should be avoided! Drivers who choose to do this try to minimize the number of violations they make on a route, meaning the number of roads that will be traveled in the reverse direction. We want the navigation system to "allow" drivers to make at most ~K~ violations.

Given the map and ~K~, we want to be able to answer questions of the form: "what is the length of the shortest path from location ~u~ to location ~v~, if the driver is willing to make at most ~p~ violations?" (where ~0 \le p \le K~).

Input Data

The first line of the input will contain four natural numbers ~N~, ~M~, ~K~, and ~Q~, separated in pairs by a single space. The last number ~Q~ is the number of questions to be asked.

The next ~M~ lines correspond to the roads. Each one will contain three natural numbers ~u~, ~v~, and ~d_{u,v}~, separated in pairs by a single space. They will satisfy ~1 \le u~, ~v \le N~, and ~1 \le d_{u,v} \le 10^6~.

The next ~Q~ lines correspond to the questions. Each one will contain three integers ~u~, ~v~, and ~p~, separated by a single space. They will satisfy ~1 \le u~, ~v \le N~, and ~0 \le p \le K~.

Output Data

The output should consist of ~Q~ lines, each containing exactly one natural number. The ~k~-th line of the output should contain the answer to the ~k~-th question. If there is no path from location ~u~ to location ~v~ with at most ~p~ violations for any question, the corresponding line of the output should contain the word "IMPOSSIBLE".

Constraints

• ~2 \le N \le 100~
• ~1 \le M \le 1.000~
• ~0 \le K \le 10~
• ~1 \le Q \le 10.000~
• Time limit: 1 sec.
• Maximum available memory: 64 MB.

Example of Input - Output

STDIN (driveme.in)

6 9 2 10
2 1 2
3 2 7
4 5 6
1 3 8
1 4 4
5 2 8
5 6 10
1 5 5
4 2 5
1 6 1
3 5 0
1 2 0
3 5 1
1 2 1
4 3 1
6 4 0
2 6 2
6 4 1
6 4 2

STDOUT (driveme.out)

15
14
9
13
2
12
IMPOSSIBLE
17
24
16