#P18319. Max Mod

Max Mod

Max Mod

有一个长度为 NN 的整数数组 AA,初始时所有 AiA_i 都是0。另外给定一个质数 MM。

你需要依次处理以下两种操作:

  1. 给定 X,YX,Y,对于所有 1≤i≤N1\le i\le N,给 AiA_i 加上 X+(i−1)YX+(i-1)Y。
  2. 给定 L,RL,R,求所有 L≤i≤RL\le i\le R 中 Ai mod MA_i\bmod M 的最大值。

这里 Ai mod MA_i\bmod M 取 00 至 M−1M-1 之间的非负余数。

输入格式

本题输入只有一组数据。

第一行包含三个整数 N,M,QN,M,Q。

接下来 QQ 行,每行包含三个整数,格式为以下一种:

  • 1 X Y:进行第一种操作。
  • 2 L R:进行第二种操作。

输出格式

对于每个第二种操作,输出一行,包含相应区间中 Ai mod MA_i\bmod M 的最大值。

数据范围

  • 1≤N,Q≤5⋅1051\le N,Q\le5\cdot10^5;
  • 1≤M≤1091\le M\le10^9,且 MM 是质数;
  • 操作类型为1或2;
  • 对于第一种操作,1≤X,Y≤1091\le X,Y\le10^9;
  • 对于第二种操作,1≤L≤R≤N1\le L\le R\le 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][2,9,16,23,30];
  • [11,31,51,71,91][11,31,51,71,91]。

第一次查询中,A2 mod 37=14A_2\bmod37=14,A3 mod 37=34A_3\bmod37=34,A4 mod 37=17A_4\bmod37=17,所以最大值是34。