[AdditionalFile5532.zip](file://AdditionalFile5532.zip?type=additional_file)

#5532. 「PA 2018 Final」Nowy kontrakt 2

标签: 传统 | 时间限制: 8000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2018 Final Nowy kontrakt 2

你的游戏仍然在市场上大获成功，因此推出续集只是时间问题。不幸的是，你与著名科幻作家的合同刚刚到期，你必须协商一份新合同。当然，作者的律师提出了过高的要求，而且他们经常改变主意。

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

复杂的税务规定导致某些数字的某些位必须为 $0$，这些位称为固定位。其他位是不固定的（我们用 ? 表示），你可以自由设定它们的值。位的状态（固定/不固定）可能会变化，有时你必须准备新合同，以最小化支付给作者的总金额。

你将收到两种类型的指令（部分加密，以强制立即找到答案，即所谓的强制在线）：

• $\texttt{1 r' c'}$ $(0 \leq r^{\prime} \leq N-1, 0 \leq c^{\prime} \leq M-1)$，令 $r = (r^{\prime} + X) \bmod N$ 和 $c = (c^{\prime} + X) \bmod M$，其中 $X$ 是上次给出的非 $-1$ 的答案（如果还未有此类答案，则 $X=0$）。在第 $r$ 个数字中，第 $c$ 个位的状态会改变，从固定变为不固定，或从不固定变为固定。游戏编号从 $0$ 到 $N-1$。位编号从 $0$ 到 $M-1$，从左到右（即从最高有效位到最低有效位）。
• $\texttt{2}$ ，找到支付给作者的 $N$ 个金额的最小可能总和，并输出结果对 $10^{9}+7$ 取模的值。如果无法满足给定条件，输出 $-1$。

初始时，所有位都是固定的（即值为 $0$）。

你能解决这个问题吗？请记住，这涉及到巨大的金钱！

输入格式

输入的第一行包含三个整数 $N, M, Q$ $(1 \leq N \leq 1000, 1 \leq M \leq 10^{9}, 1 \leq Q \leq 500000)$，分别表示游戏数量、每个报酬的位数以及要处理的查询数量。

接下来的 $Q$ 行包含查询，格式如任务描述中所述。

对于类型 1 的查询，满足 $0 \leq r^{\prime} \leq N-1$，$0 \leq c^{\prime} \leq M-1$。

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

输出格式

对于每个类型 2 的查询，输出一个数字，表示给定场景下支付给作者的最小总报酬对 $10^{9}+7$ 取模的结果，如果可以满足给定条件的话。否则输出 $-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
30
-1
7
21

样例中使用了输入的数字 $r$ 和 $c$（而非加密的 $r^{\prime}$ 和 $c^{\prime}$），其形式如下：

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

我们有 $N=3$ 款游戏，每笔报酬是 $4$ 位二进制数（可能包含前导零）。前几个查询易于解密，因为尚未有类型 2 查询的非 $-1$ 答案，所以 $X=0$，即 $r=r^{\prime}$ 和 $c=c^{\prime}$。

$\begin{array}{ccccccccccccccccc} \texttt{0000} & & \texttt{?000} & & \texttt{?000} & & \texttt{?000} & & & & \texttt{?000} & & & & \texttt{?000} & & \\ \texttt{0000} & \rightarrow & \texttt{0000} & \rightarrow & \texttt{?000} & \rightarrow & \texttt{?000} & \rightarrow & \texttt{(-1)} & \rightarrow & \texttt{?0?0} & \rightarrow & \texttt{(-1)} & \rightarrow & \texttt{?0?0} & \rightarrow & \texttt{(30)} \\ \texttt{0000} & & \texttt{0000} & & \texttt{0000} & & \texttt{?000} & & & & \texttt{?000} & & & & \texttt{??00} & & \\ \end{array}$

查询结果为 $30$，因为最优（也是唯一可能的）金额为 $1000_{2}$、$1010_{2}$ 和 $1100_{2}$。这些数字确实是正数且严格递增。总和为 $8 + 10 + 12 = 30$。