E. Пустить реки вспять
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Существует $$$n$$$ стран, в каждой из которых ровно по $$$k$$$ регионов. Для $$$j$$$-го региона $$$i$$$-й страны они вычислили значение $$$a_{i,j}$$$, которое отражает количество воды в нём.

Мудрецы намереваются создать каналы между $$$j$$$-м регионом $$$i$$$-й страны и $$$j$$$-м регионом $$$(i + 1)$$$-й страны для всех $$$1 \leq i \leq (n - 1)$$$ и для всех $$$1 \leq j \leq k$$$.

В силу того, что все $$$n$$$ стран находятся на большом склоне, вода стекает в сторону страны с наибольшим номером. По прогнозу мудрецов, после создания системы каналов новое значение $$$j$$$-го региона $$$i$$$-й страны станет равно $$$b_{i,j} = a_{1,j} | a_{2,j} | ... | a_{i,j}$$$, где $$$|$$$ — операция побитового «ИЛИ».

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

Каждый запрос будет содержать $$$m$$$ требований.

Каждое требование содержит три параметра: номер региона $$$r$$$, знак $$$o$$$ («$$$<$$$» или «$$$>$$$») и значение $$$c$$$. Если $$$o$$$ = «$$$<$$$», то в $$$r$$$-м регионе выбранной вами страны новое значение должно быть строго меньше значения ограничения $$$c$$$, а если $$$o$$$ = «$$$>$$$» — строго больше.

Иными словами, выбранная вами страна $$$i$$$ должна удовлетворять всем $$$m$$$ требованиям. Если в очередном требовании $$$o$$$ = «$$$<$$$», то должно выполняться $$$b_{i,r} < c$$$, а если $$$o$$$ = «$$$>$$$» — то $$$b_{i,r} > c$$$.

В ответ на каждый запрос вам следует вывести одно целое число — номер подходящей страны. Если таких стран несколько, выведите наименьший из возможных. Если таких стран не существует, выведите $$$-1$$$.

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

Первая строка содержит три целых числа $$$n$$$, $$$k$$$, и $$$q$$$ ($$$1 \leq n, k, q \leq 10^5$$$) — количество стран, регионов и запросов соответственно.

Далее следует $$$n$$$ строк, $$$i$$$-я из которых содержит $$$k$$$ целых чисел $$$a_{i,1}, a_{i,2}, \dots, a_{i,k}$$$ ($$$1 \leq a_{i,j} \leq 10^9$$$), где $$$a_{i,j}$$$ — значение $$$j$$$-го региона $$$i$$$-й страны.

Далее описывается $$$q$$$ запросов.

Первая строка каждого запроса содержит одно целое число $$$m$$$ ($$$1 \leq m \leq 10^5$$$) — количество требований.

Затем идут $$$m$$$ строк, содержащих значения целое число $$$r$$$, символ $$$o$$$ и целое число $$$c$$$ ($$$1 \leq r \leq k$$$, $$$0 \leq c \leq 2 \cdot 10^9$$$), где $$$r$$$ и $$$c$$$ — номер региона и значение, а $$$o$$$ — символ «$$$<$$$» либо «$$$>$$$» — знак.

Гарантируется, что $$$n \cdot k$$$ не превышает $$$10^5$$$ и что сумма $$$m$$$ по всем запросам также не превышает $$$10^5$$$.

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

Для каждого запроса на новой строке выведите целое число — наименьший номер подходящей страны, либо $$$-1$$$, если такой страны не существует.

Пример
Входные данные
3 4 4
1 3 5 9
4 6 5 3
2 1 2 7
3
1 > 4
2 < 8
1 < 6
2
1 < 8
2 > 8
1
3 > 5
2
4 > 8
1 < 8
Выходные данные
2
-1
3
1
Примечание

В примере изначальные значения регионов имеют вид:

$$$1$$$$$$3$$$$$$5$$$$$$9$$$
$$$4$$$$$$6$$$$$$5$$$$$$3$$$
$$$2$$$$$$1$$$$$$2$$$$$$7$$$

После создания каналов новые значения будут выглядеть так:

$$$1$$$$$$3$$$$$$5$$$$$$9$$$
$$$1 | 4$$$$$$3 | 6$$$$$$5 | 5$$$$$$9 | 3$$$
$$$1 | 4 | 2$$$$$$3 | 6 | 1$$$$$$5 | 5 | 2$$$$$$9 | 3 | 7$$$
$$$\downarrow$$$
$$$1$$$$$$3$$$$$$5$$$$$$9$$$
$$$5$$$$$$7$$$$$$5$$$$$$11$$$
$$$7$$$$$$7$$$$$$7$$$$$$15$$$

В первом запросе необходимо вывести минимальный номер страны (т.е. строки), где после перераспределения воды в первом регионе (т.е. столбце) новое значение будет больше четырёх и меньше шести, а во втором — меньше восьми. Этим требованиям удовлетворяет только страна с номером $$$2$$$.

Во втором запросе нет ни одной страны, удовлетворяющей заданным требованиям.

В третьем запросе подходит только страна с номером $$$3$$$.

В четвёртом запросе все три страны удовлетворяют условиям, поэтому ответом является наименьший номер $$$1$$$.