Background

Translated from ROI 2019 D1T3。

The capital of Flatland needs to establish railway connections with nearby cities, and the existing railway system is already outdated. To optimize the railway system, a high-speed tram from the capital to another city needs to be launched. The Flatland railway network has a total of $n$ stations, numbered from $1$ to $n$, and the capital is station $1$. There are $m$ directed tracks between stations, and the travel time of each track is known.

Problem Description

The planning department wants to consider several different high-speed tram route plans. Each plan is defined by a destination station and an expected travel time. However, the department knows that the actual travel time may not fully match the expectation. Therefore, they use a parameter $p$ to evaluate whether a plan is feasible: for a given expected time $r$, if $r \le x \le \frac{p}{p-1} \times r$, where $x$ is the total travel time, then the route is considered feasible.

Write a program that, given the description of the Flatland railway network and all route plans, determines whether there exists a feasible high-speed tram route for each plan.

Input Format

The first line contains an integer $t$, the number of test cases.

The following lines describe each test case.

The first line of each test case contains four integers $n, m, q, p$, representing the number of stations, the number of tracks, the number of route plans to consider, and the allowed time deviation parameter.

The next $m$ lines describe each track. Each line contains three integers $v_i, u_i, d_i$, representing the starting station, the ending station, and the travel time.

The next $q$ lines describe each route plan. Each line contains two integers $f_i$ and $r_i$, representing the destination station and the expected travel time.

Output Format

For each test case, output a string $s$ of length $q$ on one line. The $i$-th character $s_i$ equals $1$ if there exists a feasible high-speed tram route whose total travel time is within the interval $[r_i, \frac{p}{p-1} \times r_i]$; otherwise, $s_i$ equals $0$.

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

11110
10111

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

11010

Hint

Explanation of Sample $1$：

Explanation of Sample $2$：

For the first query, the route time is $1 + 120 + 1 = 122$, which meets the expectation.

For the second query, the route time is $1 + 1 + 1 = 3$, which meets the expectation.

For the fourth query, the route time is $70 + 1 + 1 = 72$, which meets the expectation.

For the third and fifth queries, there is no feasible route that meets the expectation.

Constraints：

For $100\%$ of the data, $1 \le t \le 1000$, $1 \le v_i < u_i \le n \le 500000$, $1 \le m \le 500000$, $1 \le q \le 500000$, $2 \le p \le 20$, $1 \le d_i \le 10^{11}$, $2 \le f_i \le n$, $1 \le r_i \le 10^{17}$.

Subtask scores and special properties:

Translated by ChatGPT 5