{"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 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_).\n\nOshino 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.**\n\nSometimes 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.\n\nAnd you're here to tell Koyomi the feasibility of each of his attempts.\n\n## Input\n\nThe 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.\n\nThe 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_:\n\n*   If _t_ = 1: 2 ≤ _r_1 ≤ _r_2 ≤ _n_ - 1, 2 ≤ _c_1 ≤ _c_2 ≤ _m_ - 1;\n*   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.\n*   If _t_ = 3: no extra restrictions.\n\n## Output\n\nFor 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.\n\n[samples]\n\n## Note\n\nFor the first example, the situations of Koyomi's actions are illustrated below.\n\n<center>![image](https://espresso.codeforces.com/fb439c428436e7e2fa680b135339e7954dc8c350.png)</center>","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\\ r1\\ c1\\ r2\\ c2$ \" 表示 Oshino 在以 $(r1, c1)$ 和 $(r2, c2)$ 为对角顶点、边与网格边平行的矩形区域周围放置屏障。类似地，\" $2\\ r1\\ c1\\ r2\\ c2$ \" 表示 Oshino 移除该矩形区域周围的屏障。*Oshino 确保地面上的任何屏障之间没有公共点，且不会与 $n × m$ 区域的边界相交。*\n\n有时 Koyomi 会尝试在不跨越屏障的情况下从一个单元格走到另一个单元格，以避免损坏地面上的各种物品。\" $3\\ r1\\ c1\\ r2\\ c2$ \" 表示 Koyomi 尝试从 $(r1, c1)$ 走到 $(r2, c2)$ 而不穿越屏障。\n\n而你的任务就是告诉 Koyomi 每次尝试是否可行。\n\n输入的第一行包含三个用空格分隔的整数 $n$、$m$ 和 $q$（$1 ≤ n, m ≤ 2 500$，$1 ≤ q ≤ 100 000$）——网格的行数、列数，以及 Oshino 和 Koyomi 的总操作数。\n\n接下来的 $q$ 行每行描述一个操作，包含五个用空格分隔的整数 $t$、$r1$、$c1$、$r2$、$c2$（$1 ≤ t ≤ 3$，$1 ≤ r1, r2 ≤ n$，$1 ≤ c1, c2 ≤ m$）——操作类型和两个坐标。根据 $t$ 的值，还有以下附加条件：\n\n对于 Koyomi 的每次尝试（$t = 3$ 的操作），输出一行——如果可行则输出 \"_Yes_\"（不含引号），否则输出 \"_No_\"（不含引号）。\n\n对于第一个示例，Koyomi 的操作情景如下图所示。\n\n## Input\n\n输入的第一行包含三个用空格分隔的整数 $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$ 的值，还有以下附加条件：\n\n如果 $t = 1$：$2 ≤ r1 ≤ r2 ≤ n - 1$，$2 ≤ c1 ≤ c2 ≤ m - 1$；\n\n如果 $t = 2$：$2 ≤ r1 ≤ r2 ≤ n - 1$，$2 ≤ c1 ≤ c2 ≤ m - 1$，且指定的屏障组在移除前存在于地面上；\n\n如果 $t = 3$：无额外限制。\n\n## Output\n\n对于 Koyomi 的每次尝试（$t = 3$ 的操作），输出一行——如果可行则输出 \"_Yes_\"（不含引号），否则输出 \"_No_\"（不含引号）。\n\n[samples]\n\n## Note\n\n对于第一个示例，Koyomi 的操作情景如下图所示。","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 \\} $ be the set of grid cells.  \n\nLet $ B \\subseteq \\mathcal{P}(G) $ be the set of barrier segments, initially empty.  \nEach 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:  \n$$\n\\text{Rect}(r_1, c_1, r_2, c_2) = \\left\\{ (r, c) \\in G \\;\\middle|\\; \n\\begin{array}{c}\n(r = r_1 \\lor r = r_2) \\land (c_1 \\leq c \\leq c_2) \\\\\n\\lor\\ (c = c_1 \\lor c = c_2) \\land (r_1 \\leq r \\leq r_2)\n\\end{array}\n\\right\\}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 2500 $  \n2. $ 1 \\leq q \\leq 100000 $  \n3. For all barrier rectangles: no two barriers share any point; no barrier intersects the grid boundary.  \n\n**Operations**  \nFor each query $ i \\in \\{1, \\dots, q\\} $, given $ (t_i, r_{i1}, c_{i1}, r_{i2}, c_{i2}) $:  \n- If $ t_i = 1 $: $ B \\gets B \\cup \\text{Rect}(r_{i1}, c_{i1}, r_{i2}, c_{i2}) $  \n- If $ t_i = 2 $: $ B \\gets B \\setminus \\text{Rect}(r_{i1}, c_{i1}, r_{i2}, c_{i2}) $  \n- 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.  \n\n**Objective**  \nFor each query with $ t_i = 3 $, output:  \n$$\n\\begin{cases}\n\\text{\"Yes\"} & \\text{if } (r_{i1}, c_{i1}) \\text{ and } (r_{i2}, c_{i2}) \\text{ are connected in } G \\setminus B \\\\\n\\text{\"No\"} & \\text{otherwise}\n\\end{cases}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF869E","tags":["data structures","hashing"],"sample_group":[["5 6 5\n1 2 2 4 5\n1 3 3 3 3\n3 4 4 1 1\n2 2 2 4 5\n3 1 1 4 4","No\nYes"],["2500 2500 8\n1 549 1279 1263 2189\n1 303 795 1888 2432\n1 2227 622 2418 1161\n3 771 2492 1335 1433\n1 2017 2100 2408 2160\n3 48 60 798 729\n1 347 708 1868 792\n3 1940 2080 377 1546","No\nYes\nNo"]],"created_at":"2026-03-03 11:00:39"}}