| Codeforces Round 439 (Div. 2) |
|---|
| Закончено |
Adieu l'ami.
Коёми помогает Ошино, его знакомому, привести в порядок территорию около здания заброшенной школы, в котором Ошино временно проживает.
Территорию можно представить как прямоугольную сетку из n × m единичных квадратов, расположенных в n рядах и m столбцах. Квадрат в столбце c и ряде r обозначается как (r, c).
Ошино строит и убирает барьеры вокруг некоторых прямоугольных обастей из ячеек. Более конкретно, действие, обозначенное как "1 r1 c1 r2 c2" означает, что Ошино строит барьеры на границе минимального по площади прямоугольника, содержащего квадраты (r1, c1) и (r2, c2) и сторонами, параллельными сторонам квадратов. Аналогично, "2 r1 c1 r2 c2" означает, что Ошино убирает барьеры вокруг некоторого прямоугольника. Ошино гарантирует, что ни у каких двух групп барьеров нет общих точек, а также ни у какой группы барьеров нет общих точек с гранцами сетки из n × m квадратов.
Иногда Коёми пытается осторожно пройти из одного квадрата в другой, не преодолевая никаких барьеров, чтобы не повредить разные предметы на земле. "3 r1 c1 r2 c2" означает, что Коёми пытается пройти из квадрата (r1, c1) в квадрат (r2, c2), не пересекая барьеры.
Ваша задача — для каждого вопроса Коёми сообщать, может ли он добраться из одной точки до другой, не пересекая барьеры.
В первой строке содержатся три целых числа n, m и q (1 ≤ n, m ≤ 2 500, 1 ≤ q ≤ 100 000) — число строк и столбцов в сетке и суммарное количество действий Коёми и Ошино, соответственно.
Каждая из следующих 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: нет дополнительных ограничений.
Для каждого действия Коёми (действия с t = 3), выведите одну строку — «Yes» (без кавычек), если Коёми сможет добраться из одной точки до другой, и «No» (без кавычек) в противном случае.
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
No
Yes
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
No
Yes
No
В первом тестовом примере действия Коёми изображены ниже.
