U500120 数据结构

请维护一个数组，初始全为 $0$，需要支持以下几个操作： 1. `1 l r x`：给区间 $[x, y]$ 加上 $x$； 2. `2 l r x`：给区间 $[x, y]$ 中的每个数对 $x$ 取模； 3. `3 l r`：求区间 $[x, y]$ 的和。

第一行，两个整数 $n$ 和 $m$，分别表示数组长度和操作次数。 接下来 $m$ 行，每行三到四个整数，具体看题目描述。

输出若干行，第 $i$ 行表示第 $i$ 次询问操作 $3$ 的答案。

对于 $10\%$ 的数据：$1\le n,m\le5\times10^3$； 对于 $100\%$ 的数据：$1\le n,m\le10^5$，$1\le x\le10^9$。 **保证数据随机生成**，**保证数列中的所有数每时每刻都不超过 $\texttt{long long}$ 类型**。