Þekkir þú fyrirtækið „Just Odd Inventions“? Starfsemi þessa fyrirtækis snýst um að búa til „bara furðulegar uppfinningar“. Við munum kalla það JOI-fyrirtækið til styttingar.

Til að stækka við sig hefur JOI-fyrirtækið ákveðið að ráða nýja starfsmenn.

Það eru $N$ umsækjendur um störfin. Hverjum umsækjanda er úthlutað númeri frá $1$ til $N$, og hverjum umsækjanda er úthlutað heiltölu sem kallast matsgildi.

Í þessu ráðningarferli verða allir umsækjendur sem hafa matsgildi sem er að minnsta kosti ákveðið gildi ráðnir. Nýráðnu starfsmönnunum er skipt í nokkra hópa. Hópar nýráðinna starfsmanna eru myndaðir þannig að þeir uppfylli eftirfarandi skilyrði:

• Þegar bæði umsækjandi $a$ og umsækjandi $b$ ($a < b$) eru ráðnir, eru þessir starfsmenn í sama hópi þá og því aðeins að allir umsækjendur $c$ ($a \le c \le b$) séu einnig ráðnir.

Sem starfsmannastjóri hjá JOI-fyrirtækinu átt þú að áætla fjölda hópa sem myndast í þessu ráðningarferli með því að vinna úr alls $M$ fyrirspurnum í röð. $j$-ta fyrirspurnin er af annarri af eftirfarandi tveimur tegundum:

• Finndu fjölda hópa sem myndast þegar allir umsækjendur með matsgildi að minnsta kosti $B_j$ eru ráðnir. Þessi tegund fyrirspurnar kallast svarfyrirspurn.
• Uppfærðu matsgildi umsækjanda $C_j$ í $D_j$. Þessi tegund fyrirspurnar kallast uppfærslufyrirspurn.

Verkefni

Þegar upplýsingar um $M$ fyrirspurnir eru gefnar, skrifaðu forrit sem reiknar fjölda hópa fyrir hverja svarfyrirspurn.

Inntak

Lestu eftirfarandi gögn af staðalinntaki:

• Fyrsta línan inniheldur tvær heiltölur $N$ og $M$ aðskildar með bili. Þetta gefur til kynna að það séu $N$ umsækjendur og að þú munir vinna úr $M$ fyrirspurnum.
• $i$-ta línan af næstu $N$ línum ($1 \le i \le N$) inniheldur heiltölu $A_i$. Þetta gefur til kynna að áður en nokkrar fyrirspurnir eru unnar sé matsgildi umsækjanda $i$ jafnt og $A_i$.
• $j$-ta línan af næstu $M$ línum ($1 \le j \le M$) inniheldur tvær eða þrjár heiltölur aðskildar með bili. Látum fyrstu heiltöluna vera $T_j$. Innihald þessarar línu er annað af eftirfarandi:
  1. Ef $T_j = 1$ inniheldur þessi lína heiltölurnar $T_j$ og $B_j$ aðskildar með bili. Þetta gefur til kynna að $j$-ta fyrirspurnin sé svarfyrirspurn til að finna fjölda hópa sem myndast þegar allir umsækjendur með matsgildi að minnsta kosti $B_j$ eru ráðnir.
  2. Ef $T_j = 2$ inniheldur þessi lína heiltölurnar $T_j$, $C_j$ og $D_j$ aðskildar með bili. Þetta gefur til kynna að $j$-ta fyrirspurnin sé uppfærslufyrirspurn til að uppfæra matsgildi umsækjanda $C_j$ í $D_j$.

Úttak

Skrifaðu út fjölda hópa fyrir hverja svarfyrirspurn á staðalúttak, eina tölu í hverri línu.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

• $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$).
• Það er að minnsta kosti eitt $j$ ($1 \le j \le M$) þannig að $T_j = 1$.

Undirverkefni

Undirverkefni 1 [10 stig]

Eftirfarandi skilyrði eru uppfyllt: $N \le 2\,000$. $M \le 2\,000$.

Undirverkefni 2 [30 stig]

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

Undirverkefni 3 [60 stig]

Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

2
1
2

Athugasemd

1. Fyrsta fyrirspurnin er svarfyrirspurn. Ef umsækjendur 1, 2 og 4 (sem hafa matsgildi að minnsta kosti 5) eru ráðnir myndast hópur sem samanstendur af umsækjanda 1 og umsækjanda 2, og hópur sem samanstendur af umsækjanda 4, svo skrifaðu út 2.
2. Önnur fyrirspurnin er uppfærslufyrirspurn. Uppfærðu matsgildi umsækjanda 4 í 1.
3. Þriðja fyrirspurnin er svarfyrirspurn. Ef umsækjendur 1 og 2 (sem hafa matsgildi að minnsta kosti 5) eru ráðnir myndast einn hópur sem samanstendur af umsækjanda 1 og umsækjanda 2, svo skrifaðu út 1.
4. Fjórða fyrirspurnin er svarfyrirspurn. Ef umsækjendur 1, 2, 3 og 5 (sem hafa matsgildi að minnsta kosti 3) eru ráðnir myndast hópur sem samanstendur af umsækjendum 1, 2 og 3, og hópur sem samanstendur af umsækjanda 5, svo skrifaðu út 2.

Inntak 2

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

Úttak 2

0
1
3
3
2

Athugasemd

Inntak 2 uppfyllir skilyrði undirverkefnis 2.

Inntak 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

Úttak 3

2
1
0