The Untended Antiquity
Contest: Codeforces Round 439 (Div. 2)
Difficulty rating: 2400
Tags: data structures, hashing

Adieu l'ami.

Koyomi is helping Oshino, an acquaintance of his, to take care of an open space around the abandoned Eikou Cram School building, Oshino's makeshift residence.

The space is represented by a rectangular grid of n × m cells, arranged into n rows and m columns. The c-th cell in the r-th row is denoted by (r, c).

Oshino places and removes barriers around rectangular areas of cells. Specifically, an action denoted by "1 r1 c1 r2 c2" means Oshino's placing barriers around a rectangle with two corners being (r1, c1) and (r2, c2) and sides parallel to squares sides. Similarly, "2 r1 c1 r2 c2" means Oshino's removing barriers around the rectangle. Oshino ensures that no barriers staying on the ground share any common points, nor do they intersect with boundaries of the n × m area.

Sometimes Koyomi tries to walk from one cell to another carefully without striding over barriers, in order to avoid damaging various items on the ground. "3 r1 c1 r2 c2" means that Koyomi tries to walk from (r1, c1) to (r2, c2) without crossing barriers.

And you're here to tell Koyomi the feasibility of each of his attempts.

Input format:
The first line of input contains three space-separated integers n, m and q (1 ≤ n, m ≤ 2 500, 1 ≤ q ≤ 100 000) — the number of rows and columns in the grid, and the total number of Oshino and Koyomi's actions, respectively.

The following q lines each describes an action, containing five space-separated integers t, r1, c1, r2, c2 (1 ≤ t ≤ 3, 1 ≤ r1, r2 ≤ n, 1 ≤ c1, c2 ≤ m) — the type and two coordinates of an action. Additionally, the following holds depending on the value of t:

- If t = 1: 2 ≤ r1 ≤ r2 ≤ n - 1, 2 ≤ c1 ≤ c2 ≤ m - 1;
- If t = 2: 2 ≤ r1 ≤ r2 ≤ n - 1, 2 ≤ c1 ≤ c2 ≤ m - 1, the specified group of barriers exist on the ground before the removal.
- If t = 3: no extra restrictions.

Output format:
For each of Koyomi's attempts (actions with t = 3), output one line — containing "Yes" (without quotes) if it's feasible, and "No" (without quotes) otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
For the first example, the situations of Koyomi's actions are illustrated below.

Example input:
5 6 5
1 2 2 4 5
1 3 3 3 3
3 4 4 1 1
2 2 2 4 5
3 1 1 4 4

Example output:
No
Yes

Example input:
2500 2500 8
1 549 1279 1263 2189
1 303 795 1888 2432
1 2227 622 2418 1161
3 771 2492 1335 1433
1 2017 2100 2408 2160
3 48 60 798 729
1 347 708 1868 792
3 1940 2080 377 1546

Example output:
No
Yes
No

Editorial:
The barriers share no common points. Therefore two cells are connected iff the set of barriers containing each of them are the same. The reason is that no barrier can divide a barrier of larger area into two separate regions that are not reachable from each other.
First approach: 2D segment tree or quadtree.
In a 2D segment tree or quadtree, each node u represents a rectangular area. On each node we use an array list (std::vector) to keep track of all barriers fully containing u's represented rectangle. Each newly-added barrier will cause $${\mathcal {O}}(\log ^{2}n)$$ insertions and each removal will result in $${\mathcal {O}}(\log ^{2}n)$$ deletions.
For queries, iterate over the list in all involved nodes (there are $${\mathcal {O}}(\log n)$$ of them).
It can be proved that a node of size w × h with a corner (r, c) can be contained in most min{r - 1, c - 1, n - (r + h), m - (c + w)} barriers. Hence it can be shown that in the worst cases, a single query involves at most $${ \frac { 1 } { 2 } } \cdot n \cdot ( \log _ { 2 } n - 1 )$$ elements in all lists. The total space complexity is $${ \mathcal { O } } ( n ^ { 2 } \cdot \log ^ { 2 } n )$$, and time complexity is $${ \mathcal { O } } ( q \cdot n \cdot \log n )$$, both with a small constant multiplier (less than 1 / 4 for space and much less than 1 / 2 for time), efficient enough to pass all tests. Tester's implementation works in under 800 ms in worst cases, so we decided to let such solutions pass. Also, a little randomization in partitioning may help avoid constructed worst cases and further reduce maximum running time on tests.
Second approach: Randomization.
We need to quickly check whether two sets are identical. Assign a random hash value to each barrier and use their sum or xor sum as the hash of the set.
In this way, the creation/deletion of a barrier is equivalent to adding/subtracting/xoring a value to all cells in a rectangular region, and a query is equivalent to finding the values of two cells. The cells are reachable from each other iff their values are the same. This can be done efficiently with a 2D segment tree or 2D Fenwick tree, in $${\mathcal {O}}(q\cdot \log ^{2}n)$$ time.
With randomized values being 64-bit unsigned integers, the probability of a collision is 2 - 64. The probability to give 105 correct answers is (1 - 2 - 64)100 000 ≈ 1 - 2 - 47. And the probability to give correct answers on all tests is approximately 1 - 2 - 40.
If you're still afraid of collisions, you can: either (1) use a pair of 64-bit integers as the hash value, or (2) use the problemsetter's birthday, 20001206, as the seed (kidding, lol).
We are aware that a few implementations with sub-optimal time complexities passed all the tests, though we spared no effort in the preparation process to come up with various cases. We really look forward to doing better to eliminate all such possibilities in the future. Cheers!