디마와 배열

디마는 정수 $n$개로 이루어진 배열 $a$를 가지고 있다. 생일 선물로 받은 것도, 직접 산 것도, 길에서 주운 것도 아니다. 원래부터 있었고 항상 있었다. 디마는 이 배열이 어디서 왔는지 별로 궁금해하지 않는다.

디마는 배열을 가지고 놀지 않고, Petya에게 주지 않으며, 잘게 자르지도 않고, 없애려고 하지도 않는다. 디마는 배열에 두 종류의 연산만 수행한다.

• ? l r: 다중집합 $\{a_l, a_{l+1}, \ldots, a_r\}$의 MEX를 구한다.
• ! i x: $a_i$의 값을 $x$로 바꾼다 $(0 \leq x \leq n)$.

다중집합 $\{a_1, a_2, \ldots, a_k\}$의 MEX는 모든 $1 \leq i \leq k$에 대해 $t \ne a_i$를 만족하는 가장 작은 정수 $t \ge 0$이다.

첫 줄에는 두 정수 $n$과 $q$ ($1 \leq n \leq 500\,000$, $1 \leq q \leq 250\,000$)가 주어진다. 각각 배열의 크기와 연산의 개수다.

둘째 줄에는 연산을 시작하기 전 배열의 원소 $a_i$ ($0 \leq a_i \leq n$) $n$개가 주어진다.

다음 $q$개 줄에는 위에서 설명한 형식의 연산이 한 줄에 하나씩 주어진다. 배열을 바꾸는 연산은 모두 합해 최대 $50\,000$개라고 보장된다.

원소의 번호는 1부터 시작한다.

첫 번째 종류의 연산마다 해당 다중집합의 MEX를 한 줄에 하나씩 출력한다. 답은 입력에 주어진 질의 순서대로 출력한다.

샘플에서 질의는 다음과 같다.

• 처음 배열은 $[4, 1, 0, 2, 2, 3]$이다.
• 첫 번째 질의는 $\{4, 1, 0, 2, 2, 3\}$의 MEX를 구하며, 값은 $5$이다.
• 두 번째 질의는 $\{2, 2, 3\}$의 MEX를 구하며, 값은 $0$이다.
• 세 번째 질의는 $\{1, 0, 2, 2\}$의 MEX를 구하며, 값은 $3$이다.
• 네 번째 질의는 $\{1, 0, 2, 2, 3\}$의 MEX를 구하며, 값은 $4$이다.
• 다섯 번째 연산은 배열을 바꾼다. 이제 배열은 $[4, 1, 3, 2, 2, 3]$이다.
• 여섯 번째 질의는 전체 배열의 MEX를 구하며, 값은 $0$이다.
• 일곱 번째 연산은 배열을 바꾼다. 이제 배열은 $[4, 1, 3, 0, 2, 3]$이다.
• 여덟 번째 질의는 다시 전체 배열의 MEX를 구하며, 값은 $5$이다.