你的游戏在市场上依然大受欢迎，因此推出续作只是时间问题。不幸的是，你与那位著名科幻作家的合同刚刚到期，你必须重新进行谈判。当然，作者的律师们提出了苛刻的要求，而且他们还经常改变主意。

合同规定，对于你计划发行的每一款游戏（共 $N$ 款），你都需要支付一笔 $M$ 位的二进制金额，可能包含前导零。当然，律师们已经预见到——就像之前的作品一样——这些金额会越来越高，因此他们要求后续的金额必须构成一个严格递增的序列。每一笔金额都必须是正数。

复杂的税收法规规定，某些数字的某些位必须为 $0$——这些位被称为“固定位”。其余的位是“非固定位”（我们用 '?' 表示），你可以自由决定它们的值。位的状态（固定/非固定）可能会发生变化，有时你必须准备一份新的合同，以最小化支付给作者的总金额。

你将收到两种类型的指令（部分加密，以强制要求在线求解）：

• $1 \ r' \ c'$ ($0 \le r' \le N - 1, 0 \le c' \le M - 1$) —— 令 $r = (r' + X) \pmod N$ 且 $c = (c' + X) \pmod M$，其中 $X$ 是上一次给出的不等于 $-1$ 的答案（如果之前没有此类答案，则 $X = 0$）。在第 $r$ 个数字中，改变第 $c$ 个位的状态，即从固定变为非固定，或反之。游戏编号从 $0$ 到 $N - 1$。位编号从 $0$ 到 $M - 1$，从左到右（即从最高有效位开始）。
• $2$ —— 找出支付给作者的 $N$ 笔金额之和的最小值，并输出结果对 $10^9 + 7$ 取模后的值。如果无法满足给定的条件，则输出 $-1$。

起初，所有位都是固定的（即等于 $0$）。

输入格式

第一行包含三个整数 $N, M$ 和 $Q$ ($1 \le N \le 1000, 1 \le M \le 10^9, 1 \le Q \le 500\,000$)，分别表示游戏数量、每笔报酬的位数以及需要处理的查询数量。接下来的 $Q$ 行包含查询，格式如题目描述中所述。

在类型 $1$ 的查询中，满足 $0 \le r' \le N - 1, 0 \le c' \le M - 1$。

类型 $2$ 的查询至少有 $1$ 个，至多有 $1000$ 个。

输出格式

对于每个类型 $2$ 的查询，输出一行一个整数——在给定场景下作者的最小总收入对 $10^9 + 7$ 取模的结果（如果满足条件）。否则，输出 $-1$。

样例

输入 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

输出 1

-1
-1
30
-1
7
21

说明 1

样例解释：假设输入中的 $r$ 和 $c$ 未经加密（即 $r = r', c = c'$），过程如下：

我们有 $N = 3$ 款游戏，每笔金额必须是 $4$ 位数（可能包含前导零）。前几个查询是平凡的，因为在此之前没有类型 $2$ 的查询返回过非 $-1$ 的结果，所以 $X = 0$。

查询结果为 $30$，因为在该情况下最优（且唯一可能）的金额为 $1000_2, 1010_2$ 和 $1100_2$。这些数字确实是正数且严格递增。金额之和为 $8 + 10 + 12 = 30$。