P1165

序列游戏

序列游戏

有一个长度为 nn 的整数序列 AA，初始时所有元素均为 00。按照给定顺序执行 mm 次操作，操作分为以下两种：

  • 1 l r a b1\ l\ r\ a\ b：对于每个 i∈[l,r]i\in[l,r]，将 AiA_i 覆盖为 Ai=(a×(i−l+1)) mod b。A_i=(a\times(i-l+1))\bmod b。
  • 2 l r2\ l\ r：求出并输出 ∑i=lrAi。\sum_{i=l}^{r}A_i。

输入格式

第一行包含两个整数 n,mn,m。

接下来 mm 行，每行描述一次操作，格式为 1 l r a b1\ l\ r\ a\ b 或 2 l r2\ l\ r。

输出格式

对于每次类型为 22 的操作，输出一行一个整数，表示对应区间内所有元素之和。

样例输入

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

样例输出

0
3

数据范围

  • 1≤n≤1091\le n\le 10^9；
  • 1≤m≤5×1041\le m\le 5\times 10^4；
  • 1≤l≤r≤n1\le l\le r\le n；
  • 0≤a≤1060\le a\le 10^6；
  • 1≤b≤1061\le b\le 10^6。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

0
3