Your games are still a hit on the market, so sequels are just a matter of time. Unfortunately, your contract with a famous science-fiction writer has just ended, and you must negotiate a new one. Naturally, the author's lawyers are making exorbitant demands, and on top of that, they often change their minds.

The contract stipulates that for each of the $N$ games you intend to release, you will pay a certain $M$-bit amount written in binary, possibly with leading zeros. Of course, the lawyers have foreseen that—similar to previous installments—these will earn more and more, so they demanded that the successive amounts form a strictly increasing sequence. Each amount must be positive.

Complicated tax regulations mean that some bits of some numbers must be equal to 0—such bits are called fixed. The remaining bits are unfixed (which we will denote as '?') and you can freely determine their value. The state of a bit (fixed/unfixed) can change, and sometimes you must prepare a new contract, minimizing the total amount paid to the writer.

You will receive commands of two types (partially encrypted to force immediate finding of answers, i.e., an "online" solution):

• 1 $r'$ $c'$ ($0 \le r' \le N - 1, 0 \le c' \le M - 1$) – let $r = (r' + X) \pmod N$ and $c = (c' + X) \pmod M$, where $X$ is the last provided answer other than -1 (if there have been no such answers yet, then $X = 0$). In the $r$-th number, the state of the $c$-th bit changes, from fixed to unfixed or vice versa. Games are numbered from 0 to $N - 1$. Bits are numbered from 0 to $M - 1$, from left to right (i.e., from the most significant bits).
• 2 – find the smallest possible sum of $N$ amounts to be paid to the writer and output the result modulo $10^9 + 7$. If it is not possible to satisfy the given conditions, output -1.

Initially, all bits are fixed (i.e., equal to 0).

Are you able to solve this task? Remember, huge money is at stake!

Input

The first line contains three integers $N, M$ and $Q$ ($1 \le N \le 1000, 1 \le M \le 10^9, 1 \le Q \le 500\,000$) – the number of games, the number of bits in each remuneration, and the number of queries to handle. The following $Q$ lines contain queries in the format described in the problem statement.

In type 1 queries, $0 \le r' \le N - 1, 0 \le c' \le M - 1$.

There is at least one and at most 1000 queries of type 2.

Output

For each type 2 query, output a single number – the minimum total earnings of the writer for the given scenario modulo $10^9 + 7$, if it is possible to satisfy the given conditions. Otherwise, output -1.

Examples

Input 1

3 4 14
1 0 0
1 1 0
1 2 0
2
1 1 2
2
1 2 1
2
1 0 2
2
1 0 1
2
1 0 3
2

Output 1

-1
-1
30
-1
7
21

Note

Explanation of the example: The sample test with $r$ and $c$ in the input (instead of encrypted $r'$ and $c'$) would look as follows:

3 4 14
1 0 0
1 1 0
1 2 0
2
1 1 2
2
1 2 1
2
1 0 0
2
1 0 3
2
1 1 2
2

We have $N = 3$ games, and each amount must be a 4-bit number (possibly with leading zeros). The first few queries are trivial to decrypt because there has not yet been a type 2 query with an answer other than -1, so we have $X = 0$, meaning $r = r'$ and $c = c'$.

The result of the query is 30, because the optimal (and only possible in this case) amounts are $1000_2$, $1010_2$, and $1100_2$. These numbers are indeed positive and strictly increasing. The sum of the amounts is $8 + 10 + 12 = 30$.