시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 257 76 42 24.419%

문제

눈꽃 나라엔 하루 종일 눈이 온다. 눈이 아주 많이 온다. 내린 눈은 계속해서 쌓이고 녹는다.

눈꽃 나라의 기상 캐스터 택희는 눈에 관해서만 일기예보를 한다. 지진이 나도, 태풍이 와도 택희는 항상 아래와 같은 예보만 한다.

현재 적설량이 Limm 이상 Rimm 이하인 지역은 A, B, C, ... , X 이상 K개의 지역입니다.

택희는 항상 위와 같은 방식으로 예보를 했지만, 눈꽃 나라가 행정구역 개편을 하며 나뉜 지역 수가 무려 N개가 되는 바람에 K개의 지역을 일일히 언급하는 것은 너무 힘들게 되었다.

그래서 택희는 그냥 적설량이 Limm 이상 Rimm 이하인 지역의 수 K만 세기로 마음먹었다.

하지만 이 방식으로는 각 지역에 대한 정보를 전혀 알 수 없었기 때문에,

현재 T번째로 눈이 많이 온 지역에 눈이 얼마나 쌓였는지도 언급하기로 하였다.

하지만 지역이 많이 늘어났다 보니 만만치 않은 작업이었다.

따라서 택희는 각 지역의 적설량을 체크하는 자동화 프로그램을 작성해보려 한다.

택희의 프로그램은 아래와 같은 네 가지 작업을 처리할 수 있어야 한다.

  1. 지역 i에 눈이 xmm쌓인다.
  2. 지역 i의 눈이 ymm녹는다.
  3. 현재 적설량이 Limm이상 Rimm이하인 구역의 수를 센다.
  4. 현재 적설량이 T번째로 많은 도시에 쌓인 눈이 몇 mm인지 센다.

4번 작업을 좀 더 정확히 말하면, 만일 같은 값이 있다면 중복해서 모두 센다.

예를 들어 다섯 지역에 쌓인 눈이 (3, 1, 2, 1, 2) 일 때, 4번 작업에서 T가 각각 1, 2, 3, 4, 5일 때의 답은 3, 2, 2, 1, 1이 된다.

기상예보는 신속 정확이 생명이므로, 위와 같은 연산을 아주 빨리 할 수 있는 프로그램이 필요하다.

택희는 열심히 노력했지만, 어떤 프로그램도 위와 같은 연산을 빠르게 처리하지 못했다.

택희를 위해 여러분이 더 빠른 프로그램을 하나 만들어주도록 하자.

입력

첫째 줄에 눈꽃 나라의 지역 수 N, 프로그램이 처리해야 할 명령의 수 M이 주어진다. (1 ≤ N, M ≤ 105)

둘째 줄에 N개의 정수로 현재 각 지역에 쌓인 눈의 양 Si가 주어진다. (0 ≤ Si ≤ 109)

셋째 줄부터 M개의 줄에 걸쳐 다음 네 가지 형태 중 하나의 명령이 주어진다.

1 i x의 명령은 i번 지역에 xmm의 눈이 쌓임을 의미한다. (1 ≤ i ≤ N, 1 ≤ x ≤ 109)

2 i y의 명령은 i번 지역의 눈이 ymm만큼 녹았음을 의미한다. (1 ≤ i ≤ N, 1 ≤ y ≤ 109)

3 Li Ri의 명령은 현재 시점에서 적설량이 Limm이상 Rimm이하인 지역의 수를 세는 명령이다. (0 ≤ Li ≤ Ri ≤ 1018)

4 T의 명령은 현재 시점에서 T번째로 눈이 많이 쌓인 지역에 몇 mm의 눈이 쌓였는지 확인하는 명령이다. (1 ≤ T ≤ N)

2번 명령으로 인해 어떤 지역의 적설량이 음수가 되는 경우는 없다.

출력

3, 4번 명령이 주어질 때마다 하나의 정수로 답을 출력한다.

예제 입력 1

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

예제 출력 1

2
2
1
1