Background

Translated from ROI 2022 D2T2.

In the game “Sirius Expedition Team”, there are $n$ players, numbered from $1$ to $n$. Each player has accumulated $c_i$ experience points from previous missions. If two players have the same experience value, we say they are at the same level. A player with higher experience has a higher level.

The game consists of multiple rounds. At the end of each round, every player gains experience equal to the number of distinct higher levels among the other players. For example, if the players’ experience values are $[2, 5, 5, 1, 2, 10]$, then the first player’s experience increases by $2$: there are two higher levels—players with experience $5$ and $10$. In this example, the last player’s experience does not increase. All players’ experience changes simultaneously; for this example, at the end of the round the experience becomes $[4, 6, 6, 4, 4, 10]$.

Problem Description

You need to answer several queries. Each query is one of the following three types:

1. After $k$ rounds, how many distinct levels will the players have?
2. During the first $k$ rounds, how much total experience is added across all players?
3. At the end of the $k$-th round, how much experience will player $i$ have?

Input Format

The first line contains two integers $n$ and $q$ ($1\le n,q\le300,000$), representing the number of players and the number of queries.

The second line contains $n$ integers $c_i$ ($0\le c_i\le10^{12}$), representing each player’s experience at the start of the game.

The next $q$ lines contain the queries. Each line starts with an integer $t$ ($t\in\{1，2，3\}$), representing the query type.

• If $t=1$, it is followed by an integer $k$ ($0\le k\le10^{12}$), the number of rounds.
• If $t=2$, it is followed by an integer $k$ ($0\le k\le10^{12}$), the number of rounds.
• If $t=3$, it is followed by two integers $k$ and $i$ ($0\le k\le10^{12}，1\le i\le n$), the number of rounds and the player index.

In all queries, $k=0$ refers to the time at the start of the game, before the first round.

Output Format

For each query, output one number per line as the answer.

6 6
5 4 4 2 2 2
1 0
1 1
1 2
2 1
2 2
3 1 5

3
2
1
8
11
4

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

5
2
10
4

Hint

The figure below shows how the players’ experience values change during the game in the two samples.

All Constraints are given in the Input Format.

Translated by ChatGPT 5