D. Дело не идёт никуда
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эй, вы! Покажите мне этот большой слон... gut, gut... ja, ja... и дайте мне большой справка, что этот слон есть принадлежать мне!

У директора сети сувенирных лавок слонов есть $$$n$$$ магазинов с попарно различными координатами $$$(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$$$ и $$$m$$$ точек закупки с попарно различными координатами $$$(X_1, Y_1), (X_2, Y_2), \ldots, (X_m, Y_m)$$$.

Недавние слухи о краже редкого полосатого слона из Московского зоопарка спровоцировали $$$q$$$ запросов. На каждый запрос у директора появляется/пропадает магазин или появляется/пропадает точка закупки.

Директора интересует максимальное манхэттенское расстояние между открытым магазином и открытой точкой закупки. Другими словами, он хочет узнать максимальное значение $$$|x_i - X_j| + |y_i - Y_j|$$$ по всем парам $$$1 \le i \le n$$$, $$$1 \le j \le m$$$. В случае, если в данный момент времени нет ни одного открытого магазина или точки закупок, надо сообщить «KAPUT».

Помогите директору ответить на запросы в столь непростое время.

Входные данные

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следует описание наборов.

В первой строке даны целые числа $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^5$$$) — количество магазинов и количество точек закупки.

В следующих $$$n$$$ строках даны целые числа $$$x_i, y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — координаты открытых магазинов. Гарантируется, что никакие два магазина не находятся в одной точке.

В следующих $$$m$$$ строках даны целые числа $$$X_j, Y_j$$$ ($$$-10^9 \le X_j, Y_j \le 10^9$$$) — координаты открытых точек закупки. Гарантируется, что никакие две точки закупки не находятся в одной точке.

В следующей строке дано целое число $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$) — количество запросов.

Запросы бывают двух видов:

  • $$$1 \ x \ y$$$ — закрыть магазин с координатами $$$x, y$$$, если он был открыт, и открыть — в противном случае;
  • $$$2 \ X \ Y$$$ — закрыть точку закупки с координатами $$$X, Y$$$, если она была открыта, и открыть — в противном случае.

Гарантируется, что сумма $$$n$$$ по всем наборам данных не превосходит $$$5 \cdot 10^5$$$. То же самое гарантируется для $$$m$$$. То же самое гарантируется для $$$q$$$.

Выходные данные

После каждого обновления выведите максимальное расстояние между магазинами и точками закупки. Если после запроса у директора не открыт ни один магазин или не открыта ни одна точка закупки — выведите вместо максимального расстояния «KAPUT» (без кавычек).

Пример
Входные данные
3
3 3
0 0
0 1
0 2
1 1
1 2
1 3
3
2 1 3
2 1 2
1 0 12
3 3
0 0
0 1
0 2
1 1
1 2
1 3
3
2 1 1
2 1 2
2 1 3
3 3
0 0
0 1
0 2
1 1
1 2
1 3
4
1 0 0
1 0 1
1 0 2
1 0 0
Выходные данные
3
2
12
4
4
KAPUT
3
2
KAPUT
4
Примечание

Разберем первый набор входных данных:

Первым запросом точка закупки с координатой $$$(1,3)$$$ закрывается, и максимальное расстояние между действующими магазинами и точками закупки — между $$$(0,0)$$$ и $$$(1,2)$$$, то есть $$$3$$$.

Вторым обновлением точка закупки с координатой $$$(1,2)$$$ закрывается, и максимальное расстояние между действующими магазинами и точками закупки — между $$$(0,0)$$$ и $$$(1,1)$$$, то есть $$$2$$$.

Третьим обновлением открывается магазин $$$(0,12)$$$ и максимальное расстояние между действующими магазинами и точками закупки — между $$$(0,12)$$$ и $$$(1,1)$$$, то есть $$$12$$$.