你有一个包含 $N$ 个整数的数组 $A$。初始时，所有 $A_i = 0$。同时给定一个质数 $M$。

你需要处理以下格式的更新和查询：

1. 给定 $X, Y$：对于所有 $1 \le i \le N$，将 $X + (i - 1) \cdot Y$ 加到 $A_i$ 上。
2. 给定 $L, R$：求所有 $L \le i \le R$ 中 $(A_i \bmod M)$ 的最大值。

输入格式

• 第一行包含 3 个整数：$N, M$ 和 $Q$。
• 接下来的 $Q$ 行，每行包含 3 个整数，格式为以下两种之一：
  • $T = 1, X, Y$：表示参数为 $X$ 和 $Y$ 的更新。
  • $T = 2, L, R$：表示参数为 $L$ 和 $R$ 的查询。

输出格式

对于每个测试用例，针对每个查询，在单独的一行中输出 $L \le i \le R$ 范围内 $(A_i \bmod M)$ 的最大值。

数据范围

• $1 \le N, Q \le 5 \cdot 10^5$
• $1 \le M \le 10^9$
• $M$ 是质数
• $1 \le T \le 2$
• $1 \le X, Y \le 10^9$
• $1 \le L \le R \le N$

样例

样例输入 1

5 37 6
1 2 7
1 9 13
2 2 4
1 29 3
2 1 3
2 3 5

样例输出 1

34
26
35

说明

测试用例 1：数组在前 3 步的变化如下：

• 更新 1：数组更新为 $[2, 9, 16, 23, 30]$。
• 更新 2：数组更新为 $[11, 31, 51, 71, 91]$。
• 查询 1：$A_2 \pmod{37} = 14$，$A_3 \pmod{37} = 34$，$A_4 \pmod{37} = 17$。因此，最大值为 34。