题目描述

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

输出

0
3

样例 2 输入

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

输出

3
2
1
0

样例 3 输入

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

输出

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 \le A, B \le 10^6$。