19984번 - Черепахи в пруду 다국어

Пруд черепахи Тортиллы сильно изменился с момента последнего посещения Буратино. Теперь он представляет собой прямоугольное поле из $w$ столбцов и $h$ строк, в некоторых клетках которого расположены кувшинки. На этих кувшинках в солнечные дни греются многочисленные дети, внуки и правнуки Тортиллы.

На пруду находится набор из $n$ связных кувшинок. Набор кувшинок называется связным, если от любой кувшинки можно дойти до любой другой, переходя по кувшинкам, смежным по стороне.

Черепахи очень любят ходить друг к другу в гости. Когда одна черепаха решает нанести визит другой, она строит некоторый маршрут, проходящий через смежные по стороне кувшинки и соединяющий ее кувшинку с кувшинкой своей знакомой. Однако неподвижный образ жизни черепах накладывает серьезные ограничения на возможные маршруты --- перед началом движения черепаха выбирает некоторые два из четырех возможных направлений перемещения (вверх, вниз, влево, вправо) и затем может переходить с кувшинки на кувшинку только в одном из этих двух направлений. Например, на приведенном ниже рисунке черепахе с кувшинки A, желающей нанести визит черепахе с кувшинки B, нужно выбрать направления вверх и влево, чтобы иметь возможность проложить маршрут. С другой стороны, черепаха с кувшинки C не имеет возможности добраться до кувшинки A, так как на любом пути, соединяющем их кувшинки, потребуется перемещаться по меньшей мере в трех направлениях.

Черепахи считают, что кувшинки в пруду расположены удобно для черепах, если черепаха может с любой кувшинки добраться до любой другой, используя для перемещения только два направления. Например, кувшинки в пруду на рисунке выше расположены неудобно, так как с кувшинки, отмеченной буквой C, нельзя добраться до кувшинки, отмеченной буквой A. Если же добавить к имеющимся кувшинкам кувшинку на клетку, отмеченную звездочкой, то кувшинки в пруду будут расположены удобно для черепах.

По итогам семейного совещания Тортилла приняла решение последовательно добавить к $n$ имеющимся кувшинкам $q$ новых.

Ваша задача --- до начала добавлений и после каждого добавления определить, является ли набор кувшинок удобным для черепах. Тортилла гарантирует вам, что после каждого очередного добавления набор кувшинок остается связным.

В первой строке находятся два целых числа $h$, $w$ --- количество строк и столбцов в клетчатом поле, которым является пруд ($1 \leq h, w \leq 100\,000$).

В следующей строке находится целое число $n$ --- количество кувшинок в пруду в начальный момент ($1 \leq n \leq 100\,000$). 

В последующих $n$ строках находится по два целых числа $r_i, c_i$ --- для каждой кувшинки заданы номера строки и столбца, на пересечении которых она находится ($1 \leq r_i \leq h$, $1 \leq c_i \leq w$). 

В следующей строке находится целое число $q$ --- количество кувшинок, которые собирается добавить Тортилла ($0 \leq q \leq 100\,000$).

В последующих $q$ строках в аналогичном формате заданы пары целых чисел $nr_i, nc_i$, обозначающие соответственно номер строки и номер столбца клетки с очередной добавленной кувшинкой ($1 \leq nr_i \leq h$, $1 \leq nc_i \leq w$).

Гарантируется, что никакие две кувшинки во входных данных не совпадают. Гарантируется, что исходно и после каждого добавления набор кувшинок является связным.

Выведите $q + 1$ строку, каждая из которых представляет собой либо слово <<YES>>, либо слово <<NO>>, в зависимости от того, является ли на очередной момент времени система кувшинок удобной для черепах или нет. Первая строка должна содержать ответ для начального расположения кувшинок, каждая из последующих должна содержать ответ после очередного добавления кувшинки.