题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。另有一序列 $b_1,\cdots,b_n$，初始时 $b_i=\max\limits_{1\le j\le i}a_j$。

接下来进行 $m$ 次操作，每个操作为以下两种之一：

• 1 l r x：对每个 $l\le i\le r$，令 $a_i\gets a_i+x$；再对每个 $1\le i\le n$，令 $b_i\gets\min\left(b_i,\max\limits_{1\le j\le i}a_j\right)$。

• 2 k：询问 $b_k$。

由于某种原因，本题要求强制在线。

输入格式

第一行：三个整数 $n,m,o$。

第二行：$n$ 个整数 $a_1,a_2,\cdots,a_n$。

接下来 $m$ 行：每行一个操作，格式为以下两种之一：

• $1$ $l^\prime$ $r^\prime$ $x$：表示操作 1 l r x，其中 $l=1+(l^\prime-1+o\times lastans)\bmod n$，$r=1+(r^\prime-1+o\times lastans)\bmod n$。

• $2$ $k^\prime$：表示操作 2 k，其中 $k=1+(k^\prime-1+o\times lastans)\bmod n$。

$lastans$ 为上一次询问的答案（不存在则为 $0$）。

输出格式

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

样例输入1

15 20 0
0 1 3 3 4 5 6 8 15 17 14 20 5 2 4
1 10 14 -3
2 10
2 11
2 10
2 10
1 2 2 -4
2 2
1 2 15 -4
2 8
2 6
1 2 2 1
1 14 15 -2
2 15
2 14
1 14 15 2
1 10 14 1
1 2 15 1
1 9 15 -3
2 14
1 9 15 1

样例输出1

15
15
15
15
0
4
1
13
13
12

样例输入2

15 15 1
20 6 6 13 17 5 12 14 12 11 4 18 3 7 16
2 8
2 11
1 1 9 -13
1 14 14 -7
2 6
2 9
1 11 15 -2
2 11
1 4 7 -12
1 13 15 -13
2 6
2 10
1 1 8 -4
2 10
1 5 8 -6

样例输出2

20
20
20
20
18
15
15
11

数据范围

对于所有数据，满足 $1\le n,m\le 5\times 10^5$，$o\in\{0,1\}$，$1\le l\le r\le n$，$1\le k\le n$，$|x|\le 10^8$，保证任意时刻 $|a_i|\le 10^8$。