Mr. Rifat Vs Evil Rudra
Mr. Rifat standing in front of Amar Ekushey Hall of KUET. He wants to reach Babu Mama's Tea Stall for taking tea. But evil Rudra doesn't like this idea. He tries to block Mr. Rifat using his special power rectangle boundary. Now you have to determine if Mr. Rifat can reach the destination or not.
Initially, there will be a grid that represents a rectangle block and which is non-removable. You can imagine the whole place as a 2D grid.
In the following description, Type 1 and Type 2 are operations evil Rudra will perform. Type 3 is a query Mr. Rifat will ask himself.
Type 1: $r_1$ $c_1$ $r_2$ $c_2$ represents creating a rectangular boundary. $(r_1, c_1)$ and $(r_2, c_2)$ represents two opposite corners of the boundary and the sides are parallel to the coordinate axes.
Type 2: $r_1$ $c_1$ $r_2$ $c_2$ denotes removing the boundary. A rectangular boundary can be removed only if it was created earlier.
Type 3: $r_1$ $c_1$ $r_2$ $c_2$ means whether Mr. Rifat can walk from the hall to the tea stall without crossing any boundary where $(r_1, c_1)$ is the coordinate of the hall and $(r_2, c_2)$ is the coordinate of the tea stall.
Mr. Rifat can always reach the destination if the given points in the type 3 operation are enclosed by the same rectangular boundary. Also, no two boundaries will intersect with each other.
Input
In the first line contains three integers $n$ $(1\leq n \leq 2500)$, $m$ $(1\leq m \leq 2500)$ and $q$ $(1 \leq q \leq 2\cdot10^{5})$ where $n$ is the height, $m$ is the width of the grid and $q$ is the number of operations and queries to be performed.
Each of the following $q$ lines contains five space-separated integers $t, r_1, c_1, r_2, c_2$.
Where $t$ $(1 \leq t \leq 3)$ is the type of a operation or a query.
- If
$t = 1$:$2 \leq r_1\leq r_2 \leq n - 1, 2 \leq c_1 \leq c_2 \leq m - 1$ - If
$t = 2$:$2 \leq r_1\leq r_2 \leq n - 1, 2 \leq c_1 \leq c_2 \leq m - 1$ - If
$t = 3$:$1 \leq r_1, r_2 \leq n, 1 \leq c_1, c_2 \leq m$
Output
For each of the query of Type 3, output "Yes" if it's possible for Mr. Rifat to reach the tea stall from the hall and "No" otherwise.
Samples
| Input | Output |
|---|---|
10 10 10 1 5 7 8 8 3 8 2 6 7 1 5 4 9 4 3 4 2 3 3 1 2 3 3 4 3 5 7 2 9 1 3 6 9 9 2 2 3 3 4 3 1 2 2 2 3 4 9 2 7 | No Yes No Yes No |
| Input | Output |
|---|---|
1 1 1 3 1 1 1 1 | Yes |
