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 $$$a_{i,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 \leq i \leq (n - 1)$$$ and for all $$$1 \leq j \leq 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 $$$b_{i,j} = a_{1,j} | a_{2,j} | ... | a_{i,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 "$$$ \lt $$$" or "$$$ \gt $$$"), and the value $$$c$$$. If $$$o$$$ = "$$$ \lt $$$", 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$$$ = "$$$ \gt $$$", it must be strictly greater.

In other words, the chosen country $$$i$$$ must satisfy all $$$m$$$ requirements. If in the current requirement $$$o$$$ = "$$$ \lt $$$", then it must hold that $$$b_{i,r} \lt c$$$, and if $$$o$$$ = "$$$ \gt $$$", then $$$b_{i,r} \gt 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 \leq n, k, q \leq 10^5$$$) — the number of countries, regions, and queries, respectively.

Next, there are $$$n$$$ lines, where the $$$i$$$-th line contains $$$k$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,k}$$$ ($$$1 \leq a_{i,j} \leq 10^9$$$), where $$$a_{i,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 \leq m \leq 10^5$$$) — the number of requirements.

Then follow $$$m$$$ lines, each containing an integer $$$r$$$, a character $$$o$$$, and an integer $$$c$$$ ($$$1 \leq r \leq k$$$, $$$0 \leq c \leq 2 \cdot 10^9$$$), where $$$r$$$ and $$$c$$$ are the region number and the value, and $$$o$$$ is either "$$$ \lt $$$" or "$$$ \gt $$$" — the sign.

It is guaranteed that $$$n \cdot k$$$ does not exceed $$$10^5$$$ and that the sum of $$$m$$$ across all queries also does not exceed $$$10^5$$$.

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.

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$$$

$$$\downarrow$$$

$$$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$$$.

Idx	Name	Rating
A	Quintomania	800
B	Startup	800
C	Anya and 1100	1100
D	I Love 1543	1300
E	Reverse the Rivers	1600
F	XORificator 3000	1900
G	Library of Magic	2200

Codeforces Round 984 (Div. 3)