Background

"Battle of Red Cliffs" is an open-world adventure game. This means that from the very first moment you step into Teyvat, as long as you plan your stamina well, whether you climb over mountains or cross rivers, there is always a way to see new scenery.

Problem Description

There are $n$ ships, numbered from $1$ to $n$. Each ship has $m$ soldiers, numbered from $1$ to $m$.

At the beginning, some groups of ships are connected by iron chains. The specific relations are given as follows:

You are given $s$ relations, each in the form $l_1,r_1,l_2,r_2$, meaning that $\forall k \in [0,r_1-l_1]$, ship $l_1+k$ is connected to ship $l_2+k$. It is guaranteed that $r_1-l_1+1=r_2-l_2+1$ and $l_1 < l_2$.

It is guaranteed that $\forall p \in [1,n]$, there exists at most one relation such that $l_2 \le p \le r_2$.

Then there are $q$ operations, described as follows (operations are numbered $1 \sim q$ in chronological order):

Operation $1$: Fire a rocket at the soldiers on ship $p$ in the interval $[L,R]$. After this operation, all soldiers in this interval will be on fire. Due to the chain connections, all soldiers in the interval $[L,R]$ on every ship that is directly or indirectly connected to $p$ will also be on fire. Note that a soldier may catch fire multiple times.

Operation $2$: Revoke the operation numbered $p$, and it is guaranteed that this operation must be operation $1$. It is guaranteed that the same operation will not be revoked more than once, and all future queries will not consider the effects caused by revoked operations.

Operation $3$: Query whether all soldiers on ship $p$ in the interval $[L,R]$ are on fire. If all are on fire, output Yes, otherwise output No.

Input Format

The first line contains four integers $n,m,s,q$, with meanings as described above.

The next $s$ lines each contain four integers, describing a chain relation.

The next $q$ lines describe the operations.

The first integer of each line is $op$, indicating the type of operation.

• If $op=1$, you need to input three integers $p,L,R$, and perform operation $1$ as required.

• If $op=2$, you need to input one integer $p$, and perform operation $2$ as required.

• If $op=3$, you need to input three integers $p,L,R$, and perform operation $3$ as required.

Output Format

Output several lines, each being the answer to an operation $3$.

Friendly reminder: outputting all No or all Yes will get a high score of $0\text{ pts}$.

10 20 2 9
1 5 2 6
7 9 8 10
1 4 1 5
3 6 2 3
2 1
3 6 2 3
1 10 2 7
1 9 3 6
2 6
1 7 8 13
3 8 2 12

Yes
No
Yes

10 10 2 10
1 1 2 2
1 1 8 8
1 2 1 8
1 6 7 8
1 8 7 8
1 9 6 7
3 8 3 3
2 4
1 5 7 8
3 3 3 3
3 6 3 3
2 3

Yes
No
No

Hint

Sample Explanation #1

First, two relations are given. The first one means that ships $1$ and $2$, $2$ and $3$, $3$ and $4$, $4$ and $5$, $5$ and $6$ are connected. The second one means that ships $7$ and $8$, $8$ and $9$, $9$ and $10$ are connected.

In the first operation, a rocket is fired at soldiers $1$ to $5$ on ship $4$. Since ships $1$ to $6$ are connected, soldiers $1$ to $5$ on ships $1$ to $6$ all catch fire.

In the second operation, it queries whether soldiers $2$ to $3$ on the first ship are on fire. Obviously they are, so output Yes.

In the third operation, the first operation is revoked, so after that, no soldiers are on fire.

In the fourth operation, it queries whether soldiers $2$ to $3$ on the first ship are on fire. Obviously they are not, so output No.

In the fifth operation, soldiers $[2,7]$ on ship $10$ are set on fire. In the sixth operation, soldiers $[3,6]$ on ship $9$ are set on fire. Then in the seventh operation, the sixth operation is revoked. Note: at this moment, soldiers $[2,7]$ on ships $7$ to $10$ are on fire.

In the eighth operation, soldiers $[8,13]$ on ship $7$ are set on fire. In the ninth operation, it queries whether $[2,12]$ are all on fire. Obviously, at this time they are all on fire.

Constraints

For all data, it is guaranteed that: $1 \le n\leq 10^9$, $1 \le m\leq 5\times 10^5$, $0 \le q\leq 10^5$, $0 \le s\leq 200$.

Translated by ChatGPT 5