Max Mod
有一个长度为 N 的整数数组 A,初始时所有 Ai 都是0。另外给定一个质数 M。
你需要依次处理以下两种操作:
- 给定 X,Y,对于所有 1≤i≤N,给 Ai 加上 X+(i−1)Y。
- 给定 L,R,求所有 L≤i≤R 中 AimodM 的最大值。
这里 AimodM 取 0 至 M−1 之间的非负余数。
输入格式
本题输入只有一组数据。
第一行包含三个整数 N,M,Q。
接下来 Q 行,每行包含三个整数,格式为以下一种:
1 X Y:进行第一种操作。
2 L R:进行第二种操作。
输出格式
对于每个第二种操作,输出一行,包含相应区间中 AimodM 的最大值。
数据范围
- 1≤N,Q≤5⋅105;
- 1≤M≤109,且 M 是质数;
- 操作类型为1或2;
- 对于第一种操作,1≤X,Y≤109;
- 对于第二种操作,1≤L≤R≤N。
样例
输入
5 37 6
1 2 7
1 9 13
2 2 4
1 29 3
2 1 3
2 3 5
输出
34
26
35
说明
前两个更新操作使数组依次变为:
- [2,9,16,23,30];
- [11,31,51,71,91]。
第一次查询中,A2mod37=14,A3mod37=34,A4mod37=17,所以最大值是34。