هل تعرف شركة 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$ التالية على عددين صحيحين أو ثلاثة أعداد صحيحة، تفصل بينها فراغات. إذا سمينا العدد الأول $T_j$، فإن محتوى هذا السطر يكون أحد الشكلين التاليين.

• عندما يكون $T_j=1$، يحتوي السطر على العددين الصحيحين $T_j,B_j$ مفصولين بفراغ. يدل ذلك على أن الاستعلام رقم $j$ هو استعلام إجابة لحساب عدد المجموعات الناتجة عند قبول جميع المرشحين الذين لا تقل قيمة تقييمهم عن $B_j$.

• عندما يكون $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. الاستعلام الثاني هو استعلام تحديث. نحدِّث قيمة تقييم المرشح $4$ لتصبح $1$.
3. الاستعلام الثالث هو استعلام إجابة. عند قبول المرشحين $1,2$ اللذين تبلغ قيمة تقييمهما $5$ أو أكثر، تتكون مجموعة واحدة تضم المرشحين $1,2$. لذلك نطبع 1.
4. الاستعلام الرابع هو استعلام إجابة. عند قبول المرشحين $1,2,3,5$ الذين تبلغ قيمة تقييمهم $3$ أو أكثر، تتكون مجموعتان: مجموعة تضم المرشحين $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