Suunnittelet avaavasi kaupan, joka myy maatuskanukkeja. Olet tilannut tehtaalta $N$ maatuskanukkea, jotka on numeroitu $1$:stä $N$:ään. $i$-ttä ($1 \le i \le N$) maatuskanukkea voidaan pitää onttona suorana ympyrälieriönä, jonka pohjan halkaisija on $R_i$ cm ja korkeus $H_i$ cm.

Maatuskanukkeja voidaan säilyttää asettamalla niitä sisäkkäin. Jokainen maatuskanukke voi sisältää enintään yhden toisen maatuskanuken, edellyttäen että sisään asetettavan nuken pohjan halkaisija ja korkeus ovat molemmat aidosti pienempiä kuin ulomman nuken vastaavat mitat. Toisen nuken sisällä oleva nukke voi itse sisältää toisen nuken.

Eräänä päivänä sait viestin tehtaalta. Koska he eivät pysty valmistamaan kaikkia $N$ nukkea kerralla, he lähettävät sinulle kaikki nuket, joiden pohjan halkaisija on vähintään $A$ cm ja korkeus enintään $B$ cm.

Arvot $A$ ja $B$ voivat muuttua äkillisesti. Siksi olet päättänyt laskea etukäteen jokaiselle $Q$ parille $(A_j, B_j)$ ($1 \le j \le Q$) pienimmän mahdollisen määrän maatuskanukkeja, jotka eivät ole minkään muun nuken sisällä, kun saapuvat nuket asetetaan sisäkkäin säilytystä varten.

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ja $Q$. Tämä ilmaisee, että tilattuja maatuskanukkeja on $N$ ja $(A, B)$-arvopareja on $Q$.
• Seuraavien $N$ rivin $i$-s rivi ($1 \le i \le N$) sisältää kaksi välilyönnillä erotettua kokonaislukua $R_i$ ja $H_i$. Tämä ilmaisee, että $i$-nnen nuken pohjan halkaisija on $R_i$ cm ja korkeus $H_i$ cm.
• Seuraavien $Q$ rivin $j$-s rivi ($1 \le j \le Q$) sisältää kaksi välilyönnillä erotettua kokonaislukua $A_j$ ja $B_j$.

Tuloste

Tulosteen tulee koostua $Q$ rivistä. $j$-nnen rivin ($1 \le j \le Q$) tulee sisältää parille $(A_j, B_j)$ pienin mahdollinen määrä maatuskanukkeja, jotka eivät ole minkään muun nuken sisällä, kun saapuvat nuket asetetaan sisäkkäin säilytystä varten.

Rajoitukset

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

• $1 \le N \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $1 \le R_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le H_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le A_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).
• $1 \le B_j \le 1\,000\,000\,000$ ($1 \le j \le Q$).

Osatehtävät

Osatehtävä 1 [11 pistettä]

• $N \le 10$.
• $Q = 1$.

Osatehtävä 2 [15 pistettä]

• $N \le 100$.
• $Q = 1$.

Osatehtävä 3 [25 pistettä]

• $N \le 2\,000$.
• $Q \le 2\,000$.

Osatehtävä 4 [49 pistettä]

• Ei lisärajoituksia.

Esimerkit

Syöte 1

7 3
9 5
3 7
10 6
5 10
2 6
10 10
4 1
10 5
3 5
3 9

Tuloste 1

0
1
2

Huomautus

• Kun $(A, B) = (10, 5)$, ei ole yhtään nukkea, jonka pohjan halkaisija on vähintään $10$ cm ja korkeus enintään $5$ cm, joten tulostetaan $0$.
• Kun $(A, B) = (3, 5)$, saapuvat nuket, joiden pohjan halkaisija on vähintään $3$ cm ja korkeus enintään $5$ cm, eli 1. ja 7. nukke. 7. nukke voidaan säilyttää 1. nuken sisällä. Pienin määrä nukkeja, jotka eivät ole minkään muun nuken sisällä, on $1$.
• Kun $(A, B) = (3, 9)$, saapuvat nuket, joiden pohjan halkaisija on vähintään $3$ cm ja korkeus enintään $9$ cm, eli 1., 2., 3. ja 7. nukke. Tässä tapauksessa 7. nukke voidaan säilyttää 1. nuken sisällä ja 1. nukke voidaan säilyttää 3. nuken sisällä. Pienin määrä nukkeja, jotka eivät ole minkään muun nuken sisällä, on $2$.

Syöte 2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

Tuloste 2

3
1
3
5
0
2
1
3