Aladin 在小路上散步时发现了一件非常奇怪的事情。在机器旁边有 $N$ 个空箱子。在摸索了一会儿后，他让机器开始工作了。这台机器现在可以接受 4 个整数 $L, R, A$ 和 $B$。按下标有 “NE DIRAJ” 的红色发光大按钮后，机器会开始疯狂运转并执行以下步骤：

• 将编号为 $L$ 的箱子中的石头数量设置为 $A \bmod B$。
• 接着它会飞到编号为 $L+1$ 的箱子，并将那里的石头数量设置为 $(2 \cdot A) \bmod B$。
• 接着它会飞到编号为 $L+2$ 的箱子，并将那里的石头数量设置为 $(3 \cdot A) \bmod B$。
• 一般地，它会访问编号在 $L$ 到 $R$ 之间的每个箱子，并将编号为 $X$ 的箱子中的石头数量设置为 $((X - L + 1) \cdot A) \bmod B$。
• 在访问完编号为 $R$ 的箱子后，它会停下来等待进一步的指令。

在游戏过程中，Aladin 想知道某个区间内的箱子中总共有多少颗石头。

请编写一个程序来模拟该设备并回答 Aladin 的问题。

输入格式

第一行包含两个整数 $N$ 和 $Q$（$1 \le N \le 1\,000\,000\,000$，$1 \le Q \le 50\,000$），分别表示箱子的数量和询问的数量。

接下来的 $Q$ 行包含有关模拟的信息。

• 如果该行以 1 开头，则格式为 1 L R A B（$1 \le L \le R \le N$，$1 \le A, B \le 1\,000\,000$），表示 Aladin 在设备中输入了数字 $L, R, A$ 和 $B$，并让设备执行其工作。
• 如果该行以 2 开头，则格式为 2 L R（$1 \le L \le R \le N$），表示 Aladin 想知道编号在 $L$ 到 $R$（含）之间的箱子中总共有多少颗石头。

输出格式

对于每个以 2 开头的询问，输出该特定询问的答案。

询问应按照输入中给出的顺序进行处理。

子任务

• 价值 30% 满分的测试点满足 $N, Q \le 1000$。
• 价值 70% 满分的测试点满足 $Q \le 1000$。

样例

输入样例 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

说明

第一个样例解释：

箱子初始时包含 $\{0, 0, 0, 0, 0, 0\}$，总共有 0 颗石头。

之后，设备将石头数量设置为 $\{1 \bmod 2, 2 \bmod 2, 3 \bmod 2, 4 \bmod 2, 5 \bmod 2, 0\} = \{1, 0, 1, 0, 1, 0\}$，总共有 3 颗石头。