E. Reverse the Rivers
time limit per test2 seconds
memory limit per test256 megabytes
A conspiracy of ancient sages, who decided to redirect rivers for their own convenience, has put the world on the brink. But before implementing their grand plan, they decided to carefully think through their strategy — that's what sages do.

There are n
 countries, each with exactly k
 regions. For the j
-th region of the i
-th country, they calculated the value ai,j
, which reflects the amount of water in it.

The sages intend to create channels between the j
-th region of the i
-th country and the j
-th region of the (i+1)
-th country for all 1≤i≤(n−1)
 and for all 1≤j≤k
.

Since all n
 countries are on a large slope, water flows towards the country with the highest number. According to the sages' predictions, after the channel system is created, the new value of the j
-th region of the i
-th country will be bi,j=a1,j|a2,j|...|ai,j
, where |
 denotes the bitwise "OR" operation.

After the redistribution of water, the sages aim to choose the most suitable country for living, so they will send you q
 queries for consideration.

Each query will contain m
 requirements.

Each requirement contains three parameters: the region number r
, the sign o
 (either "<
" or ">
"), and the value c
. If o
 = "<
", then in the r
-th region of the country you choose, the new value must be strictly less than the limit c
, and if o
 = ">
", it must be strictly greater.

In other words, the chosen country i
 must satisfy all m
 requirements. If in the current requirement o
 = "<
", then it must hold that bi,r<c
, and if o
 = ">
", then bi,r>c
.

In response to each query, you should output a single integer — the number of the suitable country. If there are multiple such countries, output the smallest one. If no such country exists, output −1
.

Input
The first line contains three integers n
, k
, and q
 (1≤n,k,q≤105
) — the number of countries, regions, and queries, respectively.

Next, there are n
 lines, where the i
-th line contains k
 integers ai,1,ai,2,…,ai,k
 (1≤ai,j≤109
), where ai,j
 is the value of the j
-th region of the i
-th country.

Then, q
 queries are described.

The first line of each query contains a single integer m
 (1≤m≤105
) — the number of requirements.

Then follow m
 lines, each containing an integer r
, a character o
, and an integer c
 (1≤r≤k
, 0≤c≤2⋅109
), where r
 and c
 are the region number and the value, and o
 is either "<
" or ">
" — the sign.

It is guaranteed that n⋅k
 does not exceed 105
 and that the sum of m
 across all queries also does not exceed 105
.

Output
For each query, output a single integer on a new line — the smallest number of the suitable country, or −1
 if no such country exists.

Example
InputCopy
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
OutputCopy
2
-1
3
1
Note
In the example, the initial values of the regions are as follows:

1
3
5
9
4
6
5
3
2
1
2
7
After creating the channels, the new values will look like this:

1
3
5
9
1|4
3|6
5|5
9|3
1|4|2
3|6|1
5|5|2
9|3|7
↓
1
3
5
9
5
7
5
11
7
7
7
15
In the first query, it is necessary to output the minimum country number (i.e., row) where, after the redistribution of water in the first region (i.e., column), the new value will be greater than four and less than six, and in the second region it will be less than eight. Only the country with number 2
 meets these requirements.

In the second query, there are no countries that meet the specified requirements.

In the third query, only the country with number 3
 is suitable.

In the fourth query, all three countries meet the conditions, so the answer is the smallest number 1
.

in c++