UOJ Logo Universal Online Judge

UOJ

#218. 【UNR #1】火车管理

统计

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$ 个测试点相同。

限制与约定

测试点编号$n,m$$\mathrm{ty}$
1$\leq 10^3$$=1$
2
3
4$\leq 10^5$$=0$
5$\leq 2 \times 10^5$
6$\leq 5 \times 10^5$
7$\leq 10^5$$=1$
8$\leq 2 \times 10^5$
9$\leq 3 \times 10^5$
10$\leq 5 \times 10^5$

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

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

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

下载

样例数据下载