uoj 旗下有一个火车站，用来管理属于 uoj 的小火车。

火车站一共有 $n$ 条编号为 $1, \dots, n$ 的，只有一端的用来存放小火车的铁路，由于小火车特殊的构造，每条铁路可以停放无数辆小火车。每条铁路是相互独立的。

铁路是一个栈结构，后停放的小火车可以先出来。

每辆小火车有一个吨位 $t$。

由于 NOI2016 即将到来，想要跟小火车正面作战的人多了起来，火车站管理员九条可怜每天需要处理很多事件。

事件可以概括成一下三种：

• 1 l r 有人想跟铁路编号在 $[l,r]$ 的每条铁路的第一辆可以开出来的小火车正面战斗，你需要统计这些小火车的吨位之和，没有火车的铁路不计入答案。
• 2 l 编号为 $l$ 的铁路开走一辆火车，如果这条铁路没有小火车则不开出。
• 3 l r x 铁路编号在 $[l,r]$ 的每条铁路都新停放一辆吨位为 $x$ 的火车。

现在管理员九条可怜要去南海前线了，你需要替他管理火车站。

由于火车站很忙，所以你需要实时反馈信息，我们会用一些手段要求你强制在线，具体请看输入格式。

输入格式

输入第一行三个非负整数 $n,m,\mathrm{ty}$ 表示铁路的数量和操作次数还有是否强制在线。

接下来 $m$ 行，每行四个数或者三个数或者两个数表示一次操作。

为了实时反馈信息，你需要解密 $l,r$，设读入的是 $l_1,r_1$，则实际的值如下：

\begin{eqnarray} l_2 & = & (l_1+\mathrm{lastans} \cdot \mathrm{ty}) \bmod n + 1 \\ r_2 & = & (r_1+\mathrm{lastans} \cdot \mathrm{ty}) \bmod n + 1 \\ l & = & \min(l_2,r_2) \\ r & = & \max(l_2,r_2) \end{eqnarray}

$\mathrm{lastans}$ 表示上一次询问的答案，如果之前没有询问则为 $0$。

当你进行的是第二类操作时，只需要令 $l=(l_1+\mathrm{lastans} \cdot \mathrm{ty}) \bmod n+1$ 即可。

输入数据保证 $1\leq l_1,r_1\leq n$。

注意，我们并没有加密吨位和操作类型

输出格式

对于每个询问输出一行，一个非负整数表示答案。

样例一

input

10 10 0
3 1 5 3
1 1 6
3 1 7 1
1 1 9
1 1 6
3 1 5 2
1 3 6
1 3 9
3 1 7 6
2 1

output

15
7
6
7
8

样例二

input

10 10 1
1 1 8
2 1
1 1 6
3 3 7 5
2 9
1 5 9
1 2 7
2 9
3 1 6 2
2 9

output

0
0
15
25

样例三

见样例数据下载，限制与约定跟第 $6$ 个测试点相同。

样例四

见样例数据下载，限制与约定跟第 $10$ 个测试点相同。

限制与约定

对于所有数据，$1 \leq t \leq 10^3$。

时间限制：$4\texttt{s}$

空间限制：$1024\texttt{MB}$

下载

样例数据下载