Description

Ysuperman loves taking walks in their kindergarten. To make walking easier, they model the kindergarten as a directed graph with $n$ vertices and $m$ edges. After walking a lot, they assign each edge an unparalleled closeness value: $1,2,\cdots,m$. A larger value means a closer relationship. They also assign each vertex an unparalleled label: $1,2,\cdots,n$, where $1$ represents the kindergarten gate. However, vertices have no closeness value.

Over the next $k$ days, Ysuperman has one walking plan each day. Specifically, they want to start from vertex $x_i$, use only edges whose closeness values lie in the interval $[l_i,r_i]$, and reach the gate vertex $1$. Along the way, the closeness values of the edges used must be strictly decreasing; otherwise, due to their OCD, they cannot go home.

Ysuperman is completely confused by the draft they just drew. They realize they cannot plan so many valid routes, so they ask you for help. For each day’s plan, output 1 if it is feasible, otherwise output 0.

Of course, sometimes Ysuperman is in a hurry and needs you to reply immediately; sometimes they can wait and ask all questions first, then wait for your reply.

Input Format

The first line contains four integers $n,m,k,w$, representing the number of vertices, the number of edges, the number of Ysuperman’s plans, and Ysuperman’s level of urgency. Here $w$ will be used later in the input.

Then $m$ lines follow. The $i$-th of these lines contains two integers $u_i,v_i$, indicating that there is a directed edge from vertex $u_i$ to vertex $v_i$ in the kindergarten, and its closeness value is $i$.

Then $k$ lines follow. The $i$-th of these lines contains three integers $x_i,l_i,r_i$, representing Ysuperman’s $i$-th plan.

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

If $w=1$, then $x_i,l_i,r_i$ are encrypted and you need to decrypt them. The decryption is: let $L$ be the sum of the outputs of all previous queries (if there were no previous queries, then $L=0$). You need to XOR $x_i,l_i,r_i$ with $L$.

Output Format

Output $k$ lines. Each line is either 1 or 0. The number on the $i$-th line indicates whether the $i$-th plan is feasible.

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

0
1
1
0
0

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

0
0
1
0
0
0
0
1
0
1

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

0
0
1
0
0
0
0
1
0
1

Hint

Sample Explanation

Sample Explanation $1$

For the $2$-nd plan, Ysuperman is already at the gate, so the plan is feasible.

For the $3$-rd plan, Ysuperman can only take the path $5 \overset{6}{\rightarrow}3 \overset{5}{\rightarrow} 1$. (The number above each arrow is the closeness value of the edge.)

All other plans are infeasible.

Sample Explanation $3$

Sample 3 is Sample 2 after encryption.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n \le 10^5,1 \le m \le 2\cdot10^5,0 \le k \le 2\cdot10^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$.

Hint

There may be multiple edges and self-loops, and the graph is not guaranteed to be connected.

Translated by ChatGPT 5