คุณรู้จักบริษัท 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$ คำสั่ง
• บรรทัดที่ $i$ ($1 \le i \le N$) ของ $N$ บรรทัดถัดมาประกอบด้วยจำนวนเต็ม $A_i$ หมายความว่าก่อนประมวลผลคำสั่ง ผู้สมัคร $i$ มีค่าประเมินเท่ากับ $A_i$

• บรรทัดที่ $j$ ($1 \le j \le M$) ของ $M$ บรรทัดถัดมาประกอบด้วยจำนวนเต็ม 2 หรือ 3 จำนวน คั่นด้วยช่องว่าง ให้จำนวนเต็มตัวแรกเป็น $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. คำสั่งแรกเป็นคำสั่งหาคำตอบ เมื่อรับผู้สมัคร $1$ ผู้สมัคร $2$ และผู้สมัคร $4$ ซึ่งมีค่าประเมินไม่น้อยกว่า $5$ จะเกิดกลุ่มที่ประกอบด้วยผู้สมัคร $1$ และผู้สมัคร $2$ และกลุ่มที่ประกอบด้วยผู้สมัคร $4$ รวมเป็น 2 กลุ่ม จึงส่งออก $2$
2. คำสั่งที่สองเป็นคำสั่งปรับปรุง เปลี่ยนค่าประเมินของผู้สมัคร $4$ เป็น $1$
3. คำสั่งที่สามเป็นคำสั่งหาคำตอบ เมื่อรับผู้สมัคร $1$ และผู้สมัคร $2$ ซึ่งมีค่าประเมินไม่น้อยกว่า $5$ จะเกิดหนึ่งกลุ่มที่ประกอบด้วยผู้สมัคร $1$ และผู้สมัคร $2$ จึงส่งออก $1$
4. คำสั่งที่สี่เป็นคำสั่งหาคำตอบ เมื่อรับผู้สมัคร $1$ ผู้สมัคร $2$ ผู้สมัคร $3$ และผู้สมัคร $5$ ซึ่งมีค่าประเมินไม่น้อยกว่า $3$ จะเกิดกลุ่มที่ประกอบด้วยผู้สมัคร $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