Tunnetko yrityksen "Just Odd Inventions"? Tämän yrityksen liiketoimintana on luoda "vain outoja keksintöjä". Kutsumme sitä lyhyesti JOI-yritykseksi.

Laajentaakseen liiketoimintaansa JOI-yritys on päättänyt palkata uusia työntekijöitä.

Työntekijäehdokkaita on $N$. Jokaiselle ehdokkaalle on annettu numero väliltä $1$ ja $N$, ja jokaiselle ehdokkaalle on annettu arviointiarvoksi kutsuttu kokonaisluku.

Tässä työhönottoprosessissa palkataan kaikki ehdokkaat, joiden arviointiarvo on vähintään tietyn suuruinen. Uudet palkatut työntekijät jaetaan useisiin ryhmiin. Uusien palkattujen työntekijöiden ryhmät muodostetaan siten, että seuraava ehto täyttyy:

• Kun sekä ehdokas $a$ että ehdokas $b$ ($a < b$) palkataan, nämä työntekijät kuuluvat samaan ryhmään jos ja vain jos myös kaikki ehdokkaat $c$ ($a \le c \le b$) palkataan.

JOI-yrityksen henkilöstövastaavana tehtäväsi on arvioida tässä työhönottoprosessissa muodostuvien ryhmien lukumäärää käsittelemällä yhteensä $M$ kyselyä järjestyksessä. $j$-s kysely on joko toista seuraavista kahdesta tyypistä:

• Selvitä muodostuvien ryhmien lukumäärä, kun kaikki ehdokkaat, joiden arviointiarvo on vähintään $B_j$, palkataan. Tämän tyyppistä kyselyä kutsutaan vastauskyselyksi.
• Päivitä ehdokkaan $C_j$ arviointiarvoksi $D_j$. Tämän tyyppistä kyselyä kutsutaan päivityskyselyksi.

Tehtävä

Kun $M$ kyselyn tiedot on annettu, kirjoita ohjelma, joka laskee ryhmien lukumäärän jokaiselle vastauskyselylle.

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $M$. Tämä ilmaisee, että ehdokkaita on $N$ ja käsiteltäviä kyselyitä on $M$.
• Seuraavien $N$ rivin $i$-s rivi ($1 \le i \le N$) sisältää kokonaisluvun $A_i$. Tämä ilmaisee, että ennen yhdenkään kyselyn käsittelyä ehdokkaan $i$ arviointiarvo on $A_i$.
• Seuraavien $M$ rivin $j$-s rivi ($1 \le j \le M$) sisältää kaksi tai kolme välilyönnillä erotettua kokonaislukua. Olkoon ensimmäinen kokonaisluku $T_j$. Tämän rivin sisältö on jompikumpi seuraavista:
  1. Jos $T_j = 1$, tämä rivi sisältää kokonaisluvut $T_j$ ja $B_j$ välilyönnillä erotettuina. Tämä ilmaisee, että $j$-s kysely on vastauskysely, jossa tulee selvittää muodostuvien ryhmien lukumäärä, kun kaikki ehdokkaat, joiden arviointiarvo on vähintään $B_j$, palkataan.
  2. Jos $T_j = 2$, tämä rivi sisältää kokonaisluvut $T_j$, $C_j$ ja $D_j$ välilyönnillä erotettuina. Tämä ilmaisee, että $j$-s kysely on päivityskysely, jossa ehdokkaan $C_j$ arviointiarvoksi päivitetään $D_j$.

Tuloste

Tulosta vakiotulosteeseen ryhmien lukumäärä jokaiselle vastauskyselylle, yksi per rivi.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

• $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$).
• On olemassa vähintään yksi $j$ ($1 \le j \le M$), jolle $T_j = 1$.

Osatehtävät

Osatehtävä 1 [10 pistettä]

Seuraavat ehdot täyttyvät: $N \le 2\,000$. $M \le 2\,000$.

Osatehtävä 2 [30 pistettä]

• Ehto $T_j = 1$ ($1 \le j \le M$) täyttyy.

Osatehtävä 3 [60 pistettä]

Ei lisärajoituksia.

Esimerkit

Syöte 1

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

Tuloste 1

2
1
2

Huomautus

1. Ensimmäinen kysely on vastauskysely. Jos ehdokkaat 1, 2 ja 4 (joiden arviointiarvo on vähintään 5) palkataan, muodostuu ehdokkaista 1 ja 2 koostuva ryhmä sekä ehdokkaasta 4 koostuva ryhmä, joten tulostetaan 2.
2. Toinen kysely on päivityskysely. Päivitetään ehdokkaan 4 arviointiarvoksi 1.
3. Kolmas kysely on vastauskysely. Jos ehdokkaat 1 ja 2 (joiden arviointiarvo on vähintään 5) palkataan, muodostuu yksi ehdokkaista 1 ja 2 koostuva ryhmä, joten tulostetaan 1.
4. Neljäs kysely on vastauskysely. Jos ehdokkaat 1, 2, 3 ja 5 (joiden arviointiarvo on vähintään 3) palkataan, muodostuu ehdokkaista 1, 2 ja 3 koostuva ryhmä sekä ehdokkaasta 5 koostuva ryhmä, joten tulostetaan 2.

Syöte 2

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

Tuloste 2

0
1
3
3
2

Huomautus

Syöte 2 täyttää osatehtävän 2 rajoitukset.

Syöte 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

Tuloste 3

2
1
0