시리우스 탐사

컴퓨터 게임 Expedition to Sirius를 $n$명의 플레이어가 한다. 플레이어는 1부터 $n$까지 번호가 매겨져 있다. 플레이어 $i$는 이전 임무에서 $c_i$만큼의 경험치를 쌓았다. 경험치가 같은 두 플레이어는 같은 레벨이다. 경험치가 더 많은 플레이어의 레벨이 더 높다.

게임은 여러 라운드로 진행된다. 각 라운드가 끝날 때마다 모든 플레이어는 다른 플레이어들이 가진 서로 다른 더 높은 레벨의 개수만큼 경험치를 얻는다. 예를 들어 경험치가 $[2, 5, 5, 1, 2, 10]$이면 첫 번째 플레이어는 2를 얻는다. 자신보다 높은 레벨이 5와 10, 두 개이기 때문이다. 이 예시의 마지막 플레이어는 아무것도 얻지 못한다. 경험치는 모든 플레이어가 동시에 바뀐다. 따라서 이 예시의 라운드가 끝나면 경험치는 $[4, 6, 6, 4, 4, 10]$이 된다.

여러 질문에 답해야 한다. 각 질문은 다음 세 가지 유형 중 하나이다.

1. $k$ 라운드 후 플레이어들의 서로 다른 레벨은 몇 개인가?
2. 처음 $k$ 라운드 동안 모든 플레이어에게 더해지는 경험치의 총합은 얼마인가?
3. $k$ 라운드가 끝나 경험치가 더해진 뒤, 플레이어 $i$의 경험치는 얼마인가?

첫 줄에는 두 정수 $n$과 $q$ ($1 \le n, q \le 300000$)가 주어진다. 각각 플레이어 수와 질문 수이다. 둘째 줄에는 게임 시작 시점의 각 플레이어 경험치인 $n$개의 정수 $c_i$ ($0 \le c_i \le 10^{12}$)가 주어진다. 이어지는 $q$개의 줄에는 질문이 하나씩 주어진다. 각 줄은 질문 유형 $t$ ($t \in \{1, 2, 3\}$)로 시작한다.

• $t = 1$이면 정수 $k$ ($0 \le k \le 10^{12}$) 하나가 이어서 주어진다. 라운드 수이다.
• $t = 2$이면 정수 $k$ ($0 \le k \le 10^{12}$) 하나가 이어서 주어진다. 라운드 수이다.
• $t = 3$이면 정수 $k$와 $i$ ($0 \le k \le 10^{12}$, $1 \le i \le n$) 두 개가 이어서 주어진다. 라운드 수와 플레이어 번호이다.

모든 질문에서 $k = 0$은 첫 라운드를 시작하기 전의 시점을 뜻한다.

각 질문에 대한 답을 새 줄에 출력한다.

첫 번째 테스트에서 경험치는 다음과 같이 변한다.

두 번째 테스트에서 경험치는 다음과 같이 변한다.