Problem Description

Ysuperman loves to stroll in TA's kindergarten. To make strolling more convenient, TA has abstracted the kindergarten into a directed graph with $n$ nodes and $m$ edges. Each edge has a unique intimacy level: $1, 2, \cdots, m$, where a higher number indicates greater intimacy. Each node also has a unique identifier: $1, 2, \cdots, n$, with node $1$ representing the kindergarten gate. However, nodes do not have intimacy levels.

For the next $k$ days, Ysuperman has a daily strolling plan. Specifically, TA wants to start from node $x_i$, traverse only edges with intimacy levels within the interval $[l_i, r_i]$, and reach the kindergarten gate (node $1$). The intimacy levels of the traversed edges must be strictly decreasing, as TA has obsessive-compulsive disorder and cannot return home otherwise.

Ysuperman is confused by the draft TA just sketched and finds it challenging to plan these routes. TA now asks you for help. Specifically, for each day's plan, if it is feasible, output 1; otherwise, output 0.

Sometimes Ysuperman is in a hurry and needs an immediate response, while other times TA can wait for all questions to be asked before receiving responses.

Input Format

The first line contains four integers $n, m, k, w$, representing the number of nodes, the number of edges, the number of Ysuperman's plans, and Ysuperman's urgency level, respectively. The value of $w$ is used in subsequent inputs.

The next $m$ lines contain two integers each, $u_i, v_i$, indicating a directed edge from node $u_i$ to node $v_i$ with an intimacy level of $i$.

The next $k$ lines contain three integers each, $x_i, l_i, r_i$, representing Ysuperman's $i$-th plan.

If $w = 0$, then $x_i, l_i, r_i$ are in plain text and can be used directly.

If $w = 1$, then $x_i, l_i, r_i$ are encrypted. You need to decrypt them by XORing each with $L$, where $L$ is the sum of all previous query outputs (or $0$ if there are no previous queries).

Output Format

Output $k$ lines, each containing either 1 or 0, where the $i$-th line indicates whether the $i$-th plan is feasible.

Sample Input and Output

Sample Input #1

5 7 5 0
3 2
1 2
4 3
5 4
3 1
5 3
5 1
3 1 4
1 2 2
5 5 6
4 5 7
2 1 7

Sample Output #1

0
1
1
0
0

Sample Input #2

5 12 10 0
4 2
4 2
5 3
3 3
1 5
1 4
4 4
2 4
5 3
1 5
2 2
4 1
4 3 5
4 2 3
1 4 5
3 1 8
3 1 4
3 5 5
2 1 12
4 10 12
2 5 5
1 1 3

Sample Output #2

0
0
1
0
0
0
0
1
0
1

Sample Input #3

5 12 10 1
4 2
4 2
5 3
3 3
1 5
1 4
4 4
2 4
5 3
1 5
2 2
4 1
4 3 5
4 2 3
1 4 5
2 0 9
2 0 5
2 4 4
3 0 13
5 11 13
0 7 7
3 3 1

Sample Output #3

0
0
1
0
0
0
0
1
0
1

Notes/Hints

Sample Explanation

Sample Explanation #1

For the second plan, Ysuperman is already at the gate, so the plan is feasible.

For the third plan, Ysuperman can only take the path $5 \overset{6}{\rightarrow} 3 \overset{5}{\rightarrow} 1$. (The numbers above the arrows represent the intimacy levels of the edges).

Other plans are not feasible.

Sample Explanation #3

Sample three is the encrypted version of sample two.

Data Range

This problem uses batched testing.

For $100\%$ of the data, $1 \le n \le 10^5, 1 \le m \le 2 \cdot 10^5, 0 \le k \le 2 \cdot 10^5$.

$w \in \{0, 1\}, 1 \le u_i, v_i \le n$.

After decryption, $x_i, l_i, r_i$ are guaranteed to satisfy $1 \le x \le n, 1 \le l_i, r_i \le m$.

Hints

The graph may contain multiple edges and self-loops, and it is not guaranteed to be connected.

见题面 Input 部分

见题面 Output 部分