あなたは Just Odd Inventions 社を知っているだろうか？この会社の業務は「ただ奇妙な発明（just odd inventions)」をすることである．ここでは略して JOI 社と呼ぶ．

JOI 社は事業を拡大するため，新たに社員を雇用することになった．

社員の候補者が $N$ 人いる．候補者にはそれぞれ $1$ から $N$ までの番号が付けられており，それぞれの候補者には評価値と呼ばれる一つの整数が定められている．

今回の雇用では，評価値がある値以上の候補者を全員採用する．新たに採用された社員をいくつかのグループに分ける．新たに採用された社員のグループを，次の条件をみたすように作る．

• 候補者 $a$ と候補者 $b$ ($a<b$) が両方とも採用されたとき，これらの社員が同じグループに入るのは，候補者 $c$ ($a \le c \le b$) が全員採用された場合であり，かつそのときに限る．

JOI 社の人事担当であるあなたは，クエリを合計 $M$ 個順に処理することで，今回の雇用において作られるグループの個数を見積もることになった．$j$ 番目のクエリは，以下の 2 種類のうちのいずれかである．

• 評価値が $B_j$ 以上の候補者を全員採用する場合に作られるグループの個数を求める．この種類のクエリを解答クエリと呼ぶ．
• 候補者 $C_j$ の評価値を $D_j$ に更新する．この種類のクエリを更新クエリと呼ぶ．

課題

$M$ 個のクエリについての情報が与えられたとき，それぞれの解答クエリに対するグループの個数を求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

• 1 行目には，整数 $N,M$ が空白を区切りとして書かれている．これは，社員の候補者が $N$ 人いて，あなたが $M$ 個のクエリを処理することを表す．
• 続く $N$ 行のうちの $i$ 行目 ($1 \le i \le N$) には，整数 $A_i$ が書かれている．これは，クエリを処理する以前は，候補者 $i$ の評価値が $A_i$ であることを表す．

• 続く $M$ 行のうちの $j$ 行目 ($1 \le j \le M$) には，2 個または 3 個の整数が空白を区切りとして書かれている．1 個目の整数を $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 行ずつ出力せよ，

制約

すべての入力データは以下の条件を満たす．

• $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. 1 番目のクエリは解答クエリである．評価値が $5$ 以上である候補者 $1$，候補者 $2$，候補者 $4$ を採用した場合，候補者 $1$ と候補者 $2$ からなるグループと，候補者 $4$ からなるグループの 2 個のグループが作られるので，2 を出力する．
2. 2 番目のクエリは更新クエリである．候補者 $4$ の評価値を $1$ に更新する．
3. 3 番目のクエリは解答クエリである．評価値が $5$ 以上である候補者 $1$ と候補者 $2$ を採用した場合，候補者 $1$ と候補者 $2$ からなる 1 個のグループが作られるので，1 を出力する．
4. 4 番目のクエリは解答クエリである．評価値が $3$ 以上である候補者 $1$，候補者 $2$，候補者 $3$，候補者 $5$ を採用した場合，候補者 $1$，候補者 $2$，候補者 $3$ からなるグループと，候補者 $5$ からなるグループの 2 個のグループが作られるので，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