C. Сергей и школьная столовая
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сергей пришел в школьную столовую и с ужасом обнаружил, что там уже очередь из целых $$$m$$$ человек! Теперь он не уверен, стоит ли дожидаться конца этой очереди, поэтому хочет узнать, какое же блюдо ему достанется, если он это сделает. Так как Сергей устал после занятий, он попросил вас посчитать это за него.

Всего в столовой есть $$$n$$$ блюд со стоимостями $$$a_1, a_2, \ldots, a_n$$$. Также есть очередь из $$$m$$$ человек, у которых есть $$$b_1, \ldots, b_m$$$ тугриков (школьники пронумерованы в том же порядке, как они стоят в очереди, то есть $$$b_1$$$ означает, сколько тугриков у школьника, который стоит в очереди первым, а $$$b_m$$$ — сколько у школьника, стоящего последним).

Считается, что чем дороже блюдо, тем оно вкуснее, поэтому каждый школьник, когда подходит его очередь, просто покупает самое дорогое блюдо, на которое у него хватит денег (каждое блюдо в столовой есть только в одном экземпляре, поэтому после того, как один школьник купил блюдо, его уже никто не может купить), если же денег не хватает ни на одно из блюд, школьник так и уходит голодным (жестокий капитализм).

Но для Сергея деньги не проблема, поэтому, когда подойдет его очередь, он, если еще не уйдет, просто купит самое дорогое из оставшихся блюд.

Еще в школе Сергея сейчас нестабильная экономическая ситуация, поэтому, иногда могут изменяться стоимости некоторых блюд или количество денег у некоторых школьников. Поэтому вам нужно обработать $$$q$$$ запросов двух типов:

  • изменить $$$a_i$$$ на $$$x$$$. То есть стоимость $$$i$$$ блюда становится равна $$$x$$$.
  • изменить $$$b_i$$$ на $$$x$$$. То есть у $$$i$$$ школьника становится $$$x$$$ тугриков.

После каждого запроса нужно вывести стоимость блюда, которое получит Сергей, если дождется своей очереди, или $$$-1$$$, если к этому моменту уже ничего не останется.

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

В первой строке вводятся числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 300\ 000$$$) — количество блюд и количество школьников в очереди. Во второй строке вводятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{6}$$$) — элементы массива $$$a$$$. В третьей строке вводятся $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_{m}$$$ ($$$1 \leq b_i \leq 10^{6}$$$) — элементы массива $$$b$$$. В четвертой строке вводится целое число $$$q$$$ ($$$1 \leq q \leq 300\ 000$$$) — количество запросов.

В следующих $$$q$$$ строках вводятся запросы одного из двух типов, по одному в строке:

  • если запрос первого типа, то вводится $$$1$$$, затем вводятся целые числа $$$i$$$ и $$$x$$$ ($$$1 \leq i \leq n$$$, $$$1 \leq x \leq 10^{6}$$$), что значит, что $$$a_i$$$ становится равно $$$x$$$.
  • если запрос второго типа, то вводится $$$2$$$, затем вводятся целые числа $$$i$$$ и $$$x$$$ ($$$1 \leq i \leq m$$$, $$$1 \leq x \leq 10^{6}$$$), что значит, что $$$b_i$$$ становится равно $$$x$$$.
Выходные данные

Выведите $$$q$$$ строк, $$$i$$$-я из которых содержит ответ на вопрос Сергея после $$$i$$$ изменения (стоимость блюда, которое получит Сергей, если дождется своей очереди, или $$$-1$$$, если к этому моменту уже ничего не останется).

Примеры
Входные данные
1 1
1
1
1
1 1 100
Выходные данные
100
Входные данные
1 1
1
1
1
2 1 100
Выходные данные
-1
Входные данные
4 6
1 8 2 4
3 3 6 1 5 2
3
1 1 1
2 5 10
1 1 6
Выходные данные
8
-1
4
Примечание

В первом примере после первого запроса в столовой есть одно блюдо стоимостью $$$100$$$ тугриков и один школьник с одним тугриком, поэтому Сергей купит блюдо со стоимостью $$$100$$$.

Во втором примере после первого запроса есть одно блюдо со стоимостью один тугрик и один школьник, у которого есть $$$100$$$ тугриков, поэтому Сергей ничего не получит.

В третьем примере после первого запроса никто не сможет купить блюдо стоимостью $$$8$$$, так что его получит Сергей. После второго запроса все блюда уже будут куплены до того, как настанет очередь Сергея. После третьего запроса запросе третий и пятый школьники купят соответственно первое и второе блюдо, а четвертое уже не купит никто.