Apakah Anda mengenal perusahaan Just Odd Inventions? Usaha perusahaan ini adalah membuat “penemuan yang sekadar aneh (just odd inventions)”. Di sini kita akan menyebutnya perusahaan JOI.

Untuk memperluas usahanya, perusahaan JOI memutuskan untuk merekrut karyawan baru.

Ada $N$ calon karyawan. Para calon diberi nomor dari $1$ hingga $N$, dan setiap calon memiliki sebuah bilangan bulat yang disebut nilai penilaian.

Dalam perekrutan ini, semua calon dengan nilai penilaian setidaknya suatu nilai tertentu akan diterima. Para karyawan yang baru diterima akan dibagi menjadi beberapa kelompok. Kelompok-kelompok tersebut dibentuk agar memenuhi kondisi berikut.

• Jika calon $a$ dan calon $b$ $(a < b)$ keduanya diterima, kedua karyawan tersebut berada dalam kelompok yang sama jika dan hanya jika semua calon $c$ $(a \le c \le b)$ diterima.

Sebagai penanggung jawab sumber daya manusia di perusahaan JOI, Anda akan memperkirakan jumlah kelompok yang terbentuk dalam perekrutan ini dengan memproses total $M$ kueri secara berurutan. Kueri ke-$j$ merupakan salah satu dari dua jenis berikut.

• Cari jumlah kelompok yang terbentuk jika semua calon dengan nilai penilaian setidaknya $B_j$ diterima. Kueri jenis ini disebut kueri jawaban.
• Perbarui nilai penilaian calon $C_j$ menjadi $D_j$. Kueri jenis ini disebut kueri pembaruan.

Tugas

Diberikan informasi mengenai $M$ kueri, buatlah program yang mencari jumlah kelompok untuk setiap kueri jawaban.

Masukan

Baca data berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $N, M$ yang dipisahkan spasi. Ini menyatakan bahwa ada $N$ calon karyawan dan Anda akan memproses $M$ kueri.
• Baris ke-$i$ $(1 \le i \le N)$ dari $N$ baris berikutnya berisi sebuah bilangan bulat $A_i$. Ini menyatakan bahwa sebelum kueri diproses, nilai penilaian calon $i$ adalah $A_i$.

• Baris ke-$j$ $(1 \le j \le M)$ dari $M$ baris berikutnya berisi dua atau tiga bilangan bulat yang dipisahkan spasi. Misalkan bilangan bulat pertama adalah $T_j$. Isi baris ini adalah salah satu dari berikut.

• Jika $T_j = 1$, baris tersebut berisi bilangan bulat $T_j, B_j$ yang dipisahkan spasi. Ini menyatakan bahwa kueri ke-$j$ adalah kueri jawaban yang mencari jumlah kelompok yang terbentuk jika semua calon dengan nilai penilaian setidaknya $B_j$ diterima.

• Jika $T_j = 2$, baris tersebut berisi bilangan bulat $T_j, C_j, D_j$ yang dipisahkan spasi. Ini menyatakan bahwa kueri ke-$j$ adalah kueri pembaruan yang memperbarui nilai penilaian calon $C_j$ menjadi $D_j$.

Keluaran

Cetak jumlah kelompok untuk setiap kueri jawaban secara berurutan ke keluaran standar, masing-masing pada satu baris.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $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)$.
• Ada setidaknya satu $j$ $(1 \le j \le M)$ yang memenuhi $T_j = 1$.

Subsoal

Subsoal 1 [10 poin]

Memenuhi kondisi berikut.

• $N \le 2\,000$.
• $M \le 2\,000$.

Subsoal 2 [30 poin]

• Memenuhi $T_j = 1$ $(1 \le j \le M)$.

Subsoal 3 [60 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

2
1
2

Penjelasan

1. Kueri pertama adalah kueri jawaban. Jika calon 1, calon 2, dan calon 4, yang memiliki nilai penilaian setidaknya 5, diterima, terbentuk dua kelompok: kelompok berisi calon 1 dan calon 2, serta kelompok berisi calon 4. Karena itu, cetak 2.
2. Kueri kedua adalah kueri pembaruan. Nilai penilaian calon 4 diperbarui menjadi 1.
3. Kueri ketiga adalah kueri jawaban. Jika calon 1 dan calon 2, yang memiliki nilai penilaian setidaknya 5, diterima, terbentuk satu kelompok berisi calon 1 dan calon 2. Karena itu, cetak 1.
4. Kueri keempat adalah kueri jawaban. Jika calon 1, calon 2, calon 3, dan calon 5, yang memiliki nilai penilaian setidaknya 3, diterima, terbentuk dua kelompok: kelompok berisi calon 1, calon 2, dan calon 3, serta kelompok berisi calon 5. Karena itu, cetak 2.

Masukan 2

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

Keluaran 2

0
1
3
3
2

Penjelasan

Contoh masukan 2 memenuhi batasan Subsoal 2.

Masukan 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

Keluaran 3

2
1
0