Problem Background

"The Battle of Red Cliffs" is an open-world adventure game. This means that from the moment you step into Teyvat, as long as you plan your stamina wisely, whether it's scaling mountains, crossing rivers, or traversing valleys, you will always find new vistas.

Problem Description

There are \( n \) ships, numbered from 1 to \( n \). Each ship has \( m \) soldiers, numbered from 1 to \( m \).

Initially, several groups of ships are connected by iron chains. The specific relationships are given as follows:

Given \( s \) groups of relationships, each in the form \( l_1, r_1, l_2, r_2 \), indicating that for all \( k \in [0, r_1 - l_1] \), the \( l_1 + k \)-th ship is connected to the \( l_2 + k \)-th ship. It is guaranteed that \( r_1 - l_1 + 1 = r_2 - l_2 + 1 \) and \( l_1 < l_2 \).

It is guaranteed that for all \( p \in [1, n] \), there is at most one group of relationships such that \( l_2 \le p \le r_2 \).

Next, there are \( q \) operations. The operations are as follows (operations are numbered sequentially from 1 to \( q \)):

Operation 1: Launch a rocket at the soldiers in the interval \([L, R]\) on the ship numbered \( p \). After this operation, all soldiers in this interval will catch fire. Due to the interconnected iron chains, all ships directly or indirectly connected to \( p \) will also have their soldiers in the interval \([L, R]\) catch fire. Note that soldiers may catch fire multiple times.

Operation 2: Withdraw the operation numbered \( p \), ensuring this operation is always an Operation 1. It is guaranteed that no operation will be withdrawn more than once, and subsequent queries will not consider the effects of already withdrawn operations.

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

Input Format

The first line contains four integers \( n, m, s, q \), representing the number of ships, the number of soldiers per ship, the number of relationships, and the number of operations, respectively.

The next \( s \) lines each contain four integers, representing a relationship of interconnected ships.

The next \( q \) lines represent the operations.

Each line starts with an integer \( op \) indicating the type of operation.

• If \( op = 1 \), you need to input three integers \( p, L, R \), and perform Operation 1 as described.

• If \( op = 2 \), you need to input one integer \( p \), and perform Operation 2 as described.

• If \( op = 3 \), you need to input three integers \( p, L, R \), and perform Operation 3 as described.

Output Format

Several lines, each representing the answer for each Operation 3.

Reminder: Outputting all No or all Yes will result in a score of \( 0 \text{ pts} \).

Sample Input and Output

Input Sample #1

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

Output Sample #1

Yes
No
Yes

Input Sample #2

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

Output Sample #2

Yes
No
No

Notes

Sample Explanation #1

Initially, two relationships are given: the first connects ships 1 through 6, and the second connects ships 7 through 10.

The first operation fires a rocket at soldiers 1 through 5 on ship 4, causing soldiers 1 through 5 on ships 1 through 6 to catch fire.

The second operation queries whether soldiers 2 through 3 on ship 1 are on fire. Since they are, Yes is output.

The third operation withdraws the first operation, so no soldiers are on fire anymore.

The fourth operation queries whether soldiers 2 through 3 on ship 1 are on fire. Since they are not, No is output.

The fifth operation fires a rocket at soldiers 2 through 7 on ship 10, and the sixth operation fires a rocket at soldiers 3 through 6 on ship 9. The seventh operation withdraws the sixth operation. Note: Currently, soldiers 2 through 7 on ships 7 through 10 are on fire.

The eighth operation fires a rocket at soldiers 8 through 13 on ship 7, and the ninth operation queries whether soldiers 2 through 12 on ship 8 are all on fire. Since they are, Yes is output.

Data Range

For all data, it is guaranteed that \( 1 \le n \le 10^9 \), \( 1 \le m \le 5 \times 10^5 \), \( 0 \le q \le 10^5 \), and \( 0 \le s \le 200 \).

见题面 Input 部分

见题面 Output 部分