题目描述

译自 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

input

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

output

0
3

样例 2

input

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

output

3
2
1
0

样例 3

input

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

output

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$。