Дима и массив

문제

Диме не дарили массив $aa$, состоящий из $nn$ целых чисел на день рождения, он не покупал его, не находил на улице, а он у него просто есть и всегда был, и Диме не очень-то и интересно откуда.

Дима не играет с массивом, не дарит его Пете, не режет на кусочки и не стремится его уничтожить. Дима просто выполняет операции двух видов со своим массивом:

• ? l r --- узнать MEX мультимножества $\{a_l,a_{l+1},\dots ,a_r\}\backslash \{a\_l,\; a\_\{l+1\},\; \backslash ldots,\; a\_r\backslash \}$
• ! i x --- присвоить $a_{i}a\_i$ значение $xx$ $(0\le x\le n)(0\; \backslash leq\; x\; \backslash leq\; n)$

MEX мультимножества чисел $\{a_1,a_2,\dots ,a_k\}\backslash \{a\_1,\; a\_2,\; \backslash ldots,\; a\_k\backslash \}$ --- это минимальное целое $t\ge 0t\; \backslash ge\; 0$ такое, что $t\mathrm{\ne }{a}_{i}t\; \backslash ne\; a\_i$ для всех $1\le i\le k1\; \backslash leq\; i\; \backslash leq\; k$.

На самом деле, Диме не очень нравится выполнять операции двух видов со своим массивом. Диму волнуют лишь результаты операций первого типа. Помогите Диме и напишите программу, которая выполнит операции за него.

입력

Первая строка содержит два целых числа $nn$ и $qq$ ($1\le n\le 500000,1\le q\le 2500001\; \backslash leq\; n\; \backslash leq\; 500\backslash ,000,\; 1\; \backslash leq\; q\; \backslash leq\; 250\backslash ,000$) --- размер массива, который есть у Димы и количество операций, соответственно.

Вторая строка содержит $nn$ целых чисел $a_{i}a\_i$ ($0\le a_i\le n0\; \backslash leq\; a\_i\; \backslash leq\; n$) --- массив Димы до начала операций.

Каждая из следующих $qq$ строк содержит описание одной операции в формате, описанном выше.

Гарантируется, что суммарно Дима сделал не более $5000050\backslash ,000$ операций изменения массива.

Элементы массива пронумерованы, начиная с $11$.

출력

Для каждой операцияя первого типа выведите одно целое число --- MEX соответствующего мультимножества. Ответы на запросы выводите в порядке, в котором они заданы во входных данных.

힌트

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

• Изначально массив равен $[4,1,0,2,2,3][4,\; 1,\; 0,\; 2,\; 2,\; 3]$
• В первом запросе считается MEX от $\{4,1,0,2,2,3\}\backslash \{4,\; 1,\; 0,\; 2,\; 2,\; 3\backslash \}$ и он равен $55$.
• Во втором запросе считается MEX от $\{2,2,3\}\backslash \{2,\; 2,\; 3\backslash \}$ и он равен $00$.
• В третьем запросе считается MEX от $\{1,0,2,2\}\backslash \{1,\; 0,\; 2,\; 2\backslash \}$ и он равен $33$.
• В четвёртом запросе считается MEX от $\{1,0,2,2,3\}\backslash \{1,\; 0,\; 2,\; 2,\; 3\backslash \}$ и он равен $44$.
• Пятый запрос меняет массив. Теперь он равен $[4,1,3,2,2,3][4,\; 1,\; 3,\; 2,\; 2,\; 3]$.
• В шестом запросе считается MEX от всего массива и он равен $00$.
• Седьмой запрос меняет массив. Теперь он равен $[4,1,3,0,2,3][4,\; 1,\; 3,\; 0,\; 2,\; 3]$.
• В восьмом запросе снова считается MEX от всего массива и теперь он равен $55$.