Сіз «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$ сұранысты өңдейтініңізді білдіреді.
• Келесі $N$ жолдың $i$-ші жолында ($1 \le i \le N$) бір бүтін сан $A_i$ берілген. Бұл кез келген сұранысты өңдеуден бұрын $i$ үміткерінің бағалау мәні $A_i$ екенін білдіреді.
• Келесі $M$ жолдың $j$-ші жолында ($1 \le j \le 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$).
• $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, 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