Экспедиция на Сириус

В компьютерную игру <<Экспедиция на Сириус>> играют $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. Сколько единиц опыта будет у игрока номер $i$ после начисления опыта в конце $k$-го раунда?

В первой строке даны два целых числа $n$ и $q$ ($1 \le n, q \le 300\\,000)$ --- количество игроков и количество вопросов, на которые вам нужно ответить.

Во второй строке даны $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$ означает момент начала игры до проведения первого раунда.

Для каждого вопроса выведите ответ на него в новой строке.

В первом тесте опыт игроков изменяется следующим образом:

Во втором тесте опыт игроков изменяется следующим образом: