האם אתם מכירים את חברת 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$, תוכן השורה הוא אחד מהבאים:

  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. השאילתה השנייה היא שאילתת עדכון. נעדכן את ציון ההערכה של המועמד $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.

קלט 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