English · Original
Chinese · Translation
Formal · Original
_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 _r_1 _c_1 _r_2 _c_2" means Oshino's placing barriers around a rectangle with two corners being (_r_1, _c_1) and (_r_2, _c_2) and sides parallel to squares sides. Similarly, "2 _r_1 _c_1 _r_2 _c_2" 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 _r_1 _c_1 _r_2 _c_2" means that Koyomi tries to walk from (_r_1, _c_1) to (_r_2, _c_2) without crossing barriers.
And you're here to tell Koyomi the feasibility of each of his attempts.
## Input
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_, _r_1, _c_1, _r_2, _c_2 (1 ≤ _t_ ≤ 3, 1 ≤ _r_1, _r_2 ≤ _n_, 1 ≤ _c_1, _c_2 ≤ _m_) — the type and two coordinates of an action. Additionally, the following holds depending on the value of _t_:
* If _t_ = 1: 2 ≤ _r_1 ≤ _r_2 ≤ _n_ - 1, 2 ≤ _c_1 ≤ _c_2 ≤ _m_ - 1;
* If _t_ = 2: 2 ≤ _r_1 ≤ _r_2 ≤ _n_ - 1, 2 ≤ _c_1 ≤ _c_2 ≤ _m_ - 1, the specified group of barriers exist on the ground before the removal.
* If _t_ = 3: no extra restrictions.
## Output
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.
[samples]
## Note
For the first example, the situations of Koyomi's actions are illustrated below.
<center></center>
_Adieu l'ami._
Koyomi 正在帮助他的熟人 Oshino 照顾 Eikou 寄宿学校废弃建筑周围的一片空地，这片空地是 Oshino 的临时住所。
该空地由一个大小为 $n × m$ 的矩形网格表示，包含 $n$ 行和 $m$ 列。第 $r$ 行第 $c$ 列的单元格记为 $(r, c)$。
Oshino 在单元格组成的矩形区域周围放置或移除屏障。具体而言，操作 " $1\ r1\ c1\ r2\ c2$ " 表示 Oshino 在以 $(r1, c1)$ 和 $(r2, c2)$ 为对角顶点、边与网格边平行的矩形区域周围放置屏障。类似地，" $2\ r1\ c1\ r2\ c2$ " 表示 Oshino 移除该矩形区域周围的屏障。*Oshino 确保地面上的任何屏障之间没有公共点，且不会与 $n × m$ 区域的边界相交。*
有时 Koyomi 会尝试在不跨越屏障的情况下从一个单元格走到另一个单元格，以避免损坏地面上的各种物品。" $3\ r1\ c1\ r2\ c2$ " 表示 Koyomi 尝试从 $(r1, c1)$ 走到 $(r2, c2)$ 而不穿越屏障。
而你的任务就是告诉 Koyomi 每次尝试是否可行。
输入的第一行包含三个用空格分隔的整数 $n$、$m$ 和 $q$（$1 ≤ n, m ≤ 2 500$，$1 ≤ q ≤ 100 000$）——网格的行数、列数，以及 Oshino 和 Koyomi 的总操作数。
接下来的 $q$ 行每行描述一个操作，包含五个用空格分隔的整数 $t$、$r1$、$c1$、$r2$、$c2$（$1 ≤ t ≤ 3$，$1 ≤ r1, r2 ≤ n$，$1 ≤ c1, c2 ≤ m$）——操作类型和两个坐标。根据 $t$ 的值，还有以下附加条件：
对于 Koyomi 的每次尝试（$t = 3$ 的操作），输出一行——如果可行则输出 "_Yes_"（不含引号），否则输出 "_No_"（不含引号）。
对于第一个示例，Koyomi 的操作情景如下图所示。
## Input
输入的第一行包含三个用空格分隔的整数 $n$、$m$ 和 $q$（$1 ≤ n, m ≤ 2 500$，$1 ≤ q ≤ 100 000$）——网格的行数、列数，以及 Oshino 和 Koyomi 的总操作数。接下来的 $q$ 行每行描述一个操作，包含五个用空格分隔的整数 $t$、$r1$、$c1$、$r2$、$c2$（$1 ≤ t ≤ 3$，$1 ≤ r1, r2 ≤ n$，$1 ≤ c1, c2 ≤ m$）——操作类型和两个坐标。根据 $t$ 的值，还有以下附加条件：
如果 $t = 1$：$2 ≤ r1 ≤ r2 ≤ n - 1$，$2 ≤ c1 ≤ c2 ≤ m - 1$；
如果 $t = 2$：$2 ≤ r1 ≤ r2 ≤ n - 1$，$2 ≤ c1 ≤ c2 ≤ m - 1$，且指定的屏障组在移除前存在于地面上；
如果 $t = 3$：无额外限制。
## Output
对于 Koyomi 的每次尝试（$t = 3$ 的操作），输出一行——如果可行则输出 "_Yes_"（不含引号），否则输出 "_No_"（不含引号）。
[samples]
## Note
对于第一个示例，Koyomi 的操作情景如下图所示。
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ be the dimensions of the grid.
Let $ Q \in \mathbb{Z}^+ $ be the number of queries.
Let $ G = \{ (r, c) \mid 1 \leq r \leq n,\ 1 \leq c \leq m \} $ be the set of grid cells.
Let $ B \subseteq \mathcal{P}(G) $ be the set of barrier segments, initially empty.
Each barrier is defined as the boundary of an axis-aligned rectangle with corners $ (r_1, c_1) $ and $ (r_2, c_2) $, consisting of all edge cells on the perimeter:
$$
\text{Rect}(r_1, c_1, r_2, c_2) = \left\{ (r, c) \in G \;\middle|\;
\begin{array}{c}
(r = r_1 \lor r = r_2) \land (c_1 \leq c \leq c_2) \\
\lor\ (c = c_1 \lor c = c_2) \land (r_1 \leq r \leq r_2)
\end{array}
\right\}
$$
**Constraints**
1. $ 1 \leq n, m \leq 2500 $
2. $ 1 \leq q \leq 100000 $
3. For all barrier rectangles: no two barriers share any point; no barrier intersects the grid boundary.
**Operations**
For each query $ i \in \{1, \dots, q\} $, given $ (t_i, r_{i1}, c_{i1}, r_{i2}, c_{i2}) $:
- If $ t_i = 1 $: $ B \gets B \cup \text{Rect}(r_{i1}, c_{i1}, r_{i2}, c_{i2}) $
- If $ t_i = 2 $: $ B \gets B \setminus \text{Rect}(r_{i1}, c_{i1}, r_{i2}, c_{i2}) $
- If $ t_i = 3 $: Determine whether $ (r_{i1}, c_{i1}) $ and $ (r_{i2}, c_{i2}) $ lie in the same connected component of $ G \setminus B $, using 4-directional adjacency.
**Objective**
For each query with $ t_i = 3 $, output:
$$
\begin{cases}
\text{"Yes"} & \text{if } (r_{i1}, c_{i1}) \text{ and } (r_{i2}, c_{i2}) \text{ are connected in } G \setminus B \\
\text{"No"} & \text{otherwise}
\end{cases}
$$
API Response (JSON)
{
"problem": {
"name": "E. The Untended Antiquity",
"description": {
"content": "_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",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 524288
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF869E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_Adieu l'ami._\n\nKoyomi 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.\n\nThe space is represented...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_Adieu l'ami._\n\nKoyomi 正在帮助他的熟人 Oshino 照顾 Eikou 寄宿学校废弃建筑周围的一片空地，这片空地是 Oshino 的临时住所。\n\n该空地由一个大小为 $n × m$ 的矩形网格表示，包含 $n$ 行和 $m$ 列。第 $r$ 行第 $c$ 列的单元格记为 $(r, c)$。\n\nOshino 在单元格组成的矩形区域周围放置或移除屏障。具体而言，操作 \" $1\\...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ be the dimensions of the grid. \nLet $ Q \\in \\mathbb{Z}^+ $ be the number of queries. \nLet $ G = \\{ (r, c) \\mid 1 \\leq r \\leq n,\\ 1 \\leq c \\leq m \\} $ ...",
"is_translate": false,
"language": "Formal"
}
]
}