The system connecting the capital of Flatland to neighboring cities via commuter trains is severely outdated. To modernize it, it was decided to launch an express train from the capital to one of the stations.

There are $n$ stations in the railway network of Flatland, numbered with integers from $1$ to $n$, with the capital being station $1$. There are $m$ one-way segments between stations. For each segment, the express can travel from a station with a smaller number to a station with a larger number. The time it takes for the express to travel each segment is known.

A route is defined as a sequence of segments such that the first segment starts at the capital, and for any two consecutive segments, the start of the second coincides with the end of the first. The travel time of a route is equal to the total time taken to traverse all these segments; time spent at stations should be neglected.

The Ministry of Transport of Flatland plans to consider several options for the express route from the capital. Each option is characterized by the number of the station to which the express should be sent and an estimated travel time. However, the ministry understands that it may be impossible to exactly meet the travel time requirement. Therefore, they use a value $p$ to evaluate the admissibility of a route: a route with travel time $x$ is admissible for an estimated time $r$ if $r \leqslant x \leqslant \frac{p}{p-1} \cdot r$.

You are required to write a program that, given the description of the railway network of Flatland and the route options, determines for each option whether there exists an admissible express route.

Input

This problem requires processing multiple test cases in a single run.

The first line of input contains a single integer $t$ — the number of test cases ($1 \leqslant t \leqslant 1000$).

The following lines contain the descriptions of these test cases in the following format:

The first line contains four integers $n, m, q, p$ — the number of stations, the number of segments, the number of options to consider, and the parameter defining the admissible excess of the estimated route travel time ($2 \leqslant n \leqslant 500\,000$, $1 \leqslant m \leqslant 500\,000$, $1 \leqslant q \leqslant 500\,000$, $2 \leqslant p \leqslant 20$).

The next $m$ lines each contain three integers describing the $i$-th segment: $v_i, u_i, d_i$ — the departure station, the arrival station, and the time it takes for the express to travel this segment ($1 \leqslant v_i < u_i \leqslant n$, $1 \leqslant d_i \leqslant 10^{11}$). It is guaranteed that for any station, there exists at least one route from the capital ending at it.

The next $q$ lines each contain two integers $f_i$ and $r_i$ — the requirement to check for the existence of an admissible route to station $f_i$ with an estimated travel time $r_i$ ($2 \leqslant f_i \leqslant n$, $1 \leqslant r_i \leqslant 10^{17}$).

It is guaranteed that the sum of $n$, the sum of $m$, and the sum of $q$ over all test cases in a single input does not exceed $500\,000$.

Output

Output $t$ lines, one for each test case provided in the input.

As the answer for a test, output a string $s$ of length $q$ consisting of the characters '0' and '1'. The character $s_i$ should be '1' if there exists an admissible route for the $i$-th option, i.e., a route to station $f_i$ whose travel time lies in the interval $[r_i, \frac{p}{p-1} \cdot r_i]$, and '0' otherwise.

Scoring

Examples

Input 1

2
3 3 5 20
1 2 20
2 3 1
1 3 10
2 19
2 20
3 20
3 21
3 9
7 10 5 5
1 2 15
1 3 10
2 4 21
3 4 30
2 5 14
3 5 31
4 6 3
5 6 14
1 7 39
5 7 13
7 42
7 43
7 44
5 39
6 44

Output 1

11110
10111

Input 2

1
4 6 5 2
1 2 1
2 3 1
3 4 1
1 2 70
2 3 120
3 4 4
4 90
4 2
4 10
4 37
2 34

Output 2

11010

Note

In the second example: For the first query, a route with time $1 + 120 + 1 = 122$ is suitable. For the second query, a route with time $1 + 1 + 1 = 3$ is suitable. * For the fourth query, a route with time $70 + 1 + 1 = 72$ is suitable. For the third and fifth queries, there is no suitable route.