2958 「COCI 2009.10」ALADIN

译自 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$ 行，每行一组操作。

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

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