"Just Odd Inventions"라는 회사를 알고 있는가? 이 회사의 사업은 "그저 기묘한 발명품(just odd inventions)"을 만드는 것이다. 줄여서 JOI 회사라고 부르자.

사업을 확장하기 위해 JOI 회사는 새로운 직원을 채용하기로 결정했다.

직원 후보자는 $N$명이 있다. 각 후보자에게는 $1$부터 $N$까지의 번호가 부여되어 있으며, 각 후보자에게는 평가치라고 불리는 정수가 하나씩 부여되어 있다.

이번 채용에서는 평가치가 어떤 일정한 값 이상인 모든 후보자를 채용한다. 새로 채용된 직원들은 몇 개의 그룹으로 나뉜다. 새로 채용된 직원들의 그룹은 다음 조건을 만족하도록 형성된다:

• 후보자 $a$와 후보자 $b$ ($a < b$)가 모두 채용되었을 때, 이 두 직원이 같은 그룹에 속할 필요충분조건은 모든 후보자 $c$ ($a \le c \le b$)도 함께 채용되는 것이다.

JOI 회사의 인사 담당자인 당신은 총 $M$개의 쿼리를 순서대로 처리하여 이번 채용에서 형성되는 그룹의 수를 추산하려고 한다. $j$번째 쿼리는 다음 두 종류 중 하나이다:

• 평가치가 $B_j$ 이상인 모든 후보자를 채용했을 때 형성되는 그룹의 수를 구한다. 이러한 종류의 쿼리를 답변 쿼리라고 부른다.
• 후보자 $C_j$의 평가치를 $D_j$로 갱신한다. 이러한 종류의 쿼리를 갱신 쿼리라고 부른다.

과제

$M$개의 쿼리에 대한 정보가 주어졌을 때, 각 답변 쿼리에 대해 그룹의 수를 계산하는 프로그램을 작성하라.

입력

표준 입력으로부터 다음 데이터를 읽어들인다:

• 첫째 줄에는 공백으로 구분된 두 정수 $N$과 $M$이 주어진다. 이는 후보자가 $N$명 있고 당신이 $M$개의 쿼리를 처리함을 나타낸다.
• 이어지는 $N$개의 줄 중 $i$번째 줄 ($1 \le i \le N$)에는 정수 $A_i$가 주어진다. 이는 어떤 쿼리도 처리하기 전에 후보자 $i$의 평가치가 $A_i$임을 나타낸다.
• 이어지는 $M$개의 줄 중 $j$번째 줄 ($1 \le j \le M$)에는 공백으로 구분된 두 개 또는 세 개의 정수가 주어진다. 첫 번째 정수를 $T_j$라고 하자. 이 줄의 내용은 다음 중 하나이다:
  1. $T_j = 1$이면, 이 줄에는 공백으로 구분된 정수 $T_j$와 $B_j$가 주어진다. 이는 $j$번째 쿼리가 평가치가 $B_j$ 이상인 모든 후보자를 채용했을 때 형성되는 그룹의 수를 구하는 답변 쿼리임을 나타낸다.
  2. $T_j = 2$이면, 이 줄에는 공백으로 구분된 정수 $T_j$, $C_j$, $D_j$가 주어진다. 이는 $j$번째 쿼리가 후보자 $C_j$의 평가치를 $D_j$로 갱신하는 갱신 쿼리임을 나타낸다.

출력

표준 출력으로 각 답변 쿼리에 대한 그룹의 수를 한 줄에 하나씩 출력하라.

제한

모든 입력 데이터는 다음 조건을 만족한다:

• $1 \le N \le 200\,000$.
• $1 \le M \le 200\,000$.
• $1 \le A_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le T_j \le 2$ ($1 \le j \le M$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $1 \le C_j \le N$ ($1 \le j \le M$).
• $1 \le D_j \le 1\,000\,000\,000$ ($1 \le j \le M$).
• $T_j = 1$을 만족하는 $j$ ($1 \le j \le M$)가 적어도 하나 존재한다.

서브태스크

서브태스크 1 [10점]

다음 조건을 만족한다: $N \le 2\,000$. $M \le 2\,000$.

서브태스크 2 [30점]

• $T_j = 1$ ($1 \le j \le M$)을 만족한다.

서브태스크 3 [60점]

추가 제한 조건이 없다.

예제

입력 1

5 4
8
6
3
5
4
1 5
2 4 1
1 5
1 3

출력 1

2
1
2

참고

1. 첫 번째 쿼리는 답변 쿼리이다. 평가치가 5 이상인 후보자 1, 2, 4가 채용되면, 후보자 1과 후보자 2로 이루어진 그룹과 후보자 4로 이루어진 그룹이 형성되므로 2를 출력한다.
2. 두 번째 쿼리는 갱신 쿼리이다. 후보자 4의 평가치를 1로 갱신한다.
3. 세 번째 쿼리는 답변 쿼리이다. 평가치가 5 이상인 후보자 1과 2가 채용되면, 후보자 1과 후보자 2로 이루어진 하나의 그룹이 형성되므로 1을 출력한다.
4. 네 번째 쿼리는 답변 쿼리이다. 평가치가 3 이상인 후보자 1, 2, 3, 5가 채용되면, 후보자 1, 2, 3으로 이루어진 그룹과 후보자 5로 이루어진 그룹이 형성되므로 2를 출력한다.

입력 2

7 5
13
19
1
15
13
1
19
1 20
1 1
1 6
1 11
1 17

출력 2

0
1
3
3
2

참고

입력 2는 서브태스크 2의 조건을 만족한다.

입력 3

10 5
8
10
15
2
2
8
5
12
11
4
1 5
2 8 4
1 12
2 5 11
1 16

출력 3

2
1
0