일본 침몰 2

문제

일본 열도는 동서로 가늘고 긴 열도이다. 일본 열도는 남북 방향의 경계선에 의해 $N$ 개의 구획으로 나누어져 있다. 구획에는 서쪽부터 순서대로 $1$ 부터 $N$ 까지의 번호가 붙어 있다. 현재 구획 $i$ ($1 \le i \le N$) 의 표고는 $A_{i} m$ 이다.

일본 열도에서는 종종 폭풍이 일어난다. 폭풍이 일어나면 파도에 의한 침식으로 각 구획의 표고가 다음과 같이 감소한다.

• 세기 $x$ 의 서풍 폭풍에서는, 서쪽에서 세어 $x$ 개 이내의 구획 중 "그보다 서쪽에 자신보다 표고가 높은 구획이 존재하지 않는" 모든 구획의 표고가 $1 m$ 감소한다. 즉, 폭풍 이전의 구획 $i$ 의 표고를 $a_{i}$ 로 나타내면, $i \le x$ 이고 $1 \le k < i$ 를 만족하는 모든 $k$ 에 대해 $a_{k} \le a_{i}$ 인 경우에 구획 $i$ 의 표고가 $1 m$ 줄어들고, 그 외의 경우에는 변하지 않는다.
• 세기 $x$ 의 동풍 폭풍에서는, 동쪽에서 세어 $x$ 개 이내의 구획 중 "그보다 동쪽에 자신보다 표고가 높은 구획이 존재하지 않는" 모든 구획의 표고가 $1 m$ 감소한다. 즉, 폭풍 이전의 구획 $i$ 의 표고를 $a_{i}$ 로 나타내면, $i \ge N - x + 1$ 이고 $i < k \le N$ 을 만족하는 모든 $k$ 에 대해 $a_{k} \le a_{i}$ 인 경우에 구획 $i$ 의 표고가 $1 m$ 줄어들고, 그 외의 경우에는 변하지 않는다.

당신은 앞으로 $Q$ 일간의 사건을 시뮬레이션해야 한다. $j$ 일째 ($1 \le j \le Q$) 에는 다음과 같은 사건이 일어난다.

• $T_{j} = 1$ 일 때, 세기 $X_{j}$ 의 서풍 폭풍이 일어난다.
• $T_{j} = 2$ 일 때, 세기 $X_{j}$ 의 동풍 폭풍이 일어난다.
• $T_{j} = 3$ 일 때, 그 시점에서의 구획 $X_{j}$ 의 표고를 보고한다.

또한, 제약에 의해 어느 구획의 표고도 음수가 되지 않음이 보장된다.

현재의 각 구획의 표고 및 앞으로 $Q$ 일간의 사건이 주어질 때, $T_{j} = 3$ 인 날에 대해 지정된 구획의 표고를 구하는 프로그램을 작성하시오.

제한

• $1 \le N \le 300\,000$.
• $1 \le Q \le 300\,000$.
• $Q \le A_{i} \le 10^{9}$ ($1 \le i \le N$).
• $1 \le T_{j} \le 3$ ($1 \le j \le Q$).
• $1 \le X_{j} \le N$ ($1 \le j \le Q$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($5$ 점) $N \le 2\,000$, $Q \le 2\,000$.
2. ($27$ 점) $T_{j} \neq 3$ 이면 $X_{j} = N$ ($1 \le j \le Q$).
3. ($28$ 점) $A_{1} = A_{2} = \dots = A_{N} = Q$.
4. ($20$ 점) $T_{j} \neq 2$ ($1 \le j \le Q$).
5. ($20$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$N$ $Q$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$T_{1}$ $X_{1}$
$T_{2}$ $X_{2}$
$:$
$T_{Q}$ $X_{Q}$

출력

$T_{j} = 3$ 인 $j$ ($1 \le j \le Q$) 각각에 대해, $j$ 일째 시점에서의 구획 $X_{j}$ 의 표고 ($m$) 를 나타내는 정수를 $1$ 줄씩 순서대로 출력한다.

예제 입력 1

5 7
7 7 7 7 7
1 3
1 1
3 1
2 1
2 5
3 2
3 4

예제 출력 1

5
6
6

구획 $1, 2, 3, 4, 5$ 의 표고 $(m)$ 사건 시작 시 $7, 7, 7, 7, 7$ $1$ 일째 세기 $3$ 의 서풍 폭풍이 일어난다. 서쪽에서 $3$ 개 이내의 구획 중 "그보다 서쪽에 자신보다 표고가 높은 구획이 존재하지 않는" 것은 구획 $1, 2, 3$ 이다. $6, 6, 6, 7, 7$ $2$ 일째 세기 $1$ 의 서풍 폭풍이 일어난다. 서쪽에서 $1$ 개 이내의 구획 중 "그보다 서쪽에 자신보다 표고가 높은 구획이 존재하지 않는" 것은 구획 $1$ 뿐이다. $5, 6, 6, 7, 7$ $3$ 일째 구획 $1$ 의 표고는 현재 $5 m$ 이므로, $5$ 를 출력한다. $5, 6, 6, 7, 7$ $4$ 일째 세기 $1$ 의 동풍 폭풍이 일어난다. 동쪽에서 $1$ 개 이내의 구획 중 "그보다 동쪽에 자신보다 표고가 높은 구획이 존재하지 않는" 것은 구획 $5$ 뿐이다. $5, 6, 6, 7, 6$ $5$ 일째 세기 $5$ 의 동풍 폭풍이 일어난다. 동쪽에서 $5$ 개 이내의 구획 중 "그보다 동쪽에 자신보다 표고가 높은 구획이 존재하지 않는" 것은 구획 $4, 5$ 뿐이다. $5, 6, 6, 6, 5$ $6$ 일째 구획 $2$ 의 표고는 현재 $6 m$ 이므로, $6$ 을 출력한다. $5, 6, 6, 6, 5$ $7$ 일째 구획 $4$ 의 표고는 현재 $6 m$ 이므로, $6$ 을 출력한다.

이 예제는 서브태스크 $1, 3, 5$ 의 제약을 만족한다.

예제 입력 2

5 7
10 13 14 7 12
1 5
2 5
3 3
3 4
2 5
3 1
3 2

예제 출력 2

12
7
9
11

이 예제는 서브태스크 $1, 2, 5$ 의 제약을 만족한다.

예제 입력 3

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

예제 출력 3

7
9
6
6

이 예제는 서브태스크 $1, 4, 5$ 의 제약을 만족한다.

예제 입력 4

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

예제 출력 4

5
7
6

이 예제는 서브태스크 $1, 5$ 의 제약을 만족한다.