There are $n$ inhabited planets in Little M's galaxy. Initially, the distances between these planets are so vast that a person cannot reach another planet within their lifetime; migration is often completed by relays across generations, and tourism or visiting relatives is out of the question.

Later, five-dimensional beings established space-warp tracks for the people. Those who travel through a track feel as if they have arrived at their destination instantly, but for the outside world, time has changed significantly—it might have been thousands of years, or it might have gone back thousands of years.

Formally, a track can be described by three numbers: $u, v, w$, representing that this track connects planet $u$ and planet $v$. If one travels from $u$ to $v$ through the track, time changes by $w$; if one travels from $v$ to $u$ through the track, time changes by $-w$. Note that $w$ can be positive or negative. A positive time change means that much time passes; a negative value means time flows backward by that amount; zero means time does not change.

With these tracks, people can make short-term trips to other planets, but this has also given rise to new needs: the desire to arrive at a certain planet at a specific time to see a specific person or witness a specific historical event. To achieve this, people can traverse any number of tracks and pass through multiple planets to reach their destination.

Formally, a requirement can be described by three numbers: $u, v, w$, representing the desire to start from planet $u$ and arrive at planet $v$, such that the total time change along the path compared to the departure time is $w$ (note that $w$ here can also be positive or negative).

The problem is to provide the process of establishing tracks and all the requirements during this process, and to determine whether each requirement can be satisfied.

Specifically, you will receive $m$ operations in sequence, each being either the establishment of a track or a requirement. If it is a requirement, you need to answer whether it is "possible" or "impossible" to fulfill this requirement using only the tracks established before it.

Input

You do not need to worry about the actual format of the input/output files; simply use the methods mentioned here for input and output.

First, paste the code from maze_io.cpp at the very beginning of your code.

Your program must first call maze_io::get_args(&n, &m, &k, &t); to obtain 4 parameters. Here, $n$ and $m$ are as described above, and $k$ and $t$ are parameters related to the data format. Note that all four variables must be defined as int.

Next, you need to call maze_io::get_line(&p, &u, &v, &w); $m$ times to obtain 4 parameters. Here, $p$ represents the type of operation, where $0$ indicates a new track and $1$ indicates a requirement. The other 3 variables have the meanings described above. Note that $p, u, v$ must be defined as int, and $w$ must be defined as long long.

For each requirement, you need to call maze_io::put_ans(ans); once to output the answer. Here, $ans$ is an int with a value of $0$ (indicating the requirement cannot be fulfilled) or $1$ (indicating it can be fulfilled).

If $k=3$, it means you must output the answer before you can receive the next operation; otherwise, there is no such restriction. If $k=0$, it means all requirement operations are guaranteed to appear after all track establishment operations.

Treat all tracks as undirected edges. If $t=0$, the final set of tracks forms a forest. If $t=1$, any connected component formed by the final tracks contains at most one cycle. If $t=2$, the final set of tracks forms a cactus forest, meaning each edge belongs to at most one simple cycle. If $t=3$, there are no special constraints.

Since the output is the passed parameter $ans$ itself, we can use maze_sample.cpp to output the actual operations of the sample (which will be read from maze.in and maze.ans, and output to maze.h.in). The output format is: the first line contains four integers $n, m, k, t$, followed by $m$ lines, each containing four integers $p, u, v, w$.

If you wish to construct your own test input data, the format is: the first line contains four integers $n, m, k, t$, followed by $m$ lines, each containing six integers $p, u, v, w, x, y$. Simply set $x=y=0$.

Examples

Input 1

5 20 3 3
0 5 2 8 737023109 467551616
0 1 3 -11 610666965 103793774
1 5 2 10 801050508 81540882
0 4 4 -9 432795277 577469097
0 4 1 17 167617173 189172213
0 1 4 -20 1005183139 269123299
1 4 3 -3 305267432 348822094
1 3 5 17 957086530 565704649
0 5 5 -13 580644467 252604773
0 3 5 9 262777226 184032246
1 2 1 14 438439996 597179973
0 1 4 7 489012768 974964269
1 5 1 2 660680201 894637208
1 2 2 2 682205686 450663892
1 3 5 8 181963596 230165952
0 5 2 16 673556059 931780532
0 5 4 -3 507063636 1066313785
1 5 2 -10 493798980 249901807
1 3 3 8 248671409 626524461
1 3 2 -8 159081180 345560641

Output 1

0
1
1
1
0
1
1
1
1
1

Note

For the 1st requirement, there is only one track from 5 to 2, with a time change of +8, which cannot satisfy the +10 requirement.

For the 2nd requirement, the route starts from 4, goes to 4 with -9, to 1 with +17, and to 3 with -11, for a total of -3.

For the 5th requirement, although there are many tracks in the area near 1, it is impossible to return to 1 with a time change of +2.

Constraints

For all data, all numbers obtained are integers, satisfying $1 \le u,v \le n$ and $p \in \{ 0,1 \} $.

Each test case satisfies the following constraints: