#2958. 「COCI 2009.10」ALADIN

内存限制:64 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

译自 COCI 2009.10 T6. ALADIN

有一个长度为 N 的数组 a_1, a_2, \ldots, a_N ,开始时这 N 个数均为 0。
接下来对它有 Q 次操作,操作分为两类:

  • \texttt{1 L R A B} ,修改操作,a[L] = A%B; a[L+1] = (2*A)%B; a[L+2] = (3*A)%B; ... a[R] = ((R-L+1)*A)%B;
  • \texttt{2 L R} ,查询操作,请输出 a[L]+a[L+1]+...+a[R]

输入格式

第一行两个整数 N,Q
接下来 Q 行,每行一组操作。

输出格式

对于每组查询操作,输出一行结果。

样例

样例输入 1

6 3
2 1 6
1 1 5 1 2
2 1 6

样例输出 1

0
3

样例输入 2

4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4

样例输出 2

3
2
1
0

样例输入 3

4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4

样例输出 3

16
0

数据范围与提示

对于 30\% 的数据, N, Q\le 1000
对于 70\% 的数据, Q\le 1000
对于所有数据, 1\le N\le 10^9, 1\le Q\le 5\times 10^4, 1≤ A, B ≤ 10^6