你有冇聽過 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$）。
• 至少存在一個 $j$（$1 \le j \le M$）令 $T_j=1$。

子任務

子任務 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