Сговор древних мудрецов, решивших повернуть реки для собственного удобства, поставил мир на грань. Но перед реализацией своего грандиозного плана они решили тщательно продумать стратегию — на то они и мудрецы.
Существует \(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\).
Выходные данные
Для каждого запроса на новой строке выведите целое число — наименьший номер подходящей страны, либо \(-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\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|