Du planlegger å åpne en butikk som selger matrjosjkadukker. Du har bestilt $N$ matrjosjkadukker fra en fabrikk, nummerert fra $1$ til $N$. Den $i$-te ($1 \le i \le N$) matrjosjkadukken kan betraktes som en hul rett sirkulær sylinder med en bunndiameter på $R_i$ cm og en høyde på $H_i$ cm.

Matrjosjkadukker kan oppbevares ved å sette dem inni hverandre. Hver matrjosjkadukke kan inneholde høyst én annen matrjosjkadukke, forutsatt at både bunndiameteren og høyden til dukken som skal plasseres inni er strengt mindre enn tilsvarende mål på dukken utenpå. En dukke som er plassert inni en annen dukke kan selv inneholde en annen dukke.

En dag fikk du en melding fra fabrikken. Siden de ikke kan gjøre klare alle de $N$ dukkene på én gang, vil de sende deg alle dukkene som har en bunndiameter på minst $A$ cm og en høyde på høyst $B$ cm.

Verdiene til $A$ og $B$ kan endre seg brått. Derfor har du for hvert av de $Q$ parene $(A_j, B_j)$ ($1 \le j \le Q$) bestemt deg for å forhåndsberegne det minste antallet matrjosjkadukker som ikke er plassert inni noen annen dukke når dukkene som ankommer settes inni hverandre for oppbevaring.

Inndata

Les følgende data fra standard inndata:

• Den første linjen inneholder to heltall $N$ og $Q$, atskilt med et mellomrom. Dette indikerer at det er $N$ bestilte matrjosjkadukker og $Q$ par med $(A, B)$-verdier.
• Den $i$-te linjen av de påfølgende $N$ linjene ($1 \le i \le N$) inneholder to heltall $R_i$ og $H_i$, atskilt med et mellomrom. Dette indikerer at den $i$-te dukken har en bunndiameter på $R_i$ cm og en høyde på $H_i$ cm.
• Den $j$-te linjen av de påfølgende $Q$ linjene ($1 \le j \le Q$) inneholder to heltall $A_j$ og $B_j$, atskilt med et mellomrom.

Utdata

Utdataene skal bestå av $Q$ linjer. Den $j$-te linjen ($1 \le j \le Q$) skal inneholde det minste antallet matrjosjkadukker som ikke er plassert inni noen annen dukke for paret $(A_j, B_j)$ når dukkene som ankommer settes inni hverandre for oppbevaring.

Begrensninger

Alle inndata oppfyller følgende betingelser:

• $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$).

Deloppgaver

Deloppgave 1 [11 poeng]

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

Deloppgave 2 [15 poeng]

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

Deloppgave 3 [25 poeng]

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

Deloppgave 4 [49 poeng]

• Ingen ytterligere begrensninger.

Eksempler

Inndata 1

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

Utdata 1

0
1
2

Merk

• Når $(A, B) = (10, 5)$, er det ingen dukker med en bunndiameter på minst $10$ cm og en høyde på høyst $5$ cm, så skriv ut $0$.
• Når $(A, B) = (3, 5)$, ankommer dukkene med en bunndiameter på minst $3$ cm og en høyde på høyst $5$ cm, som er den 1. og den 7. dukken. Den 7. dukken kan oppbevares inni den 1. dukken. Det minste antallet dukker som ikke er plassert inni noen annen dukke er $1$.
• Når $(A, B) = (3, 9)$, ankommer dukkene med en bunndiameter på minst $3$ cm og en høyde på høyst $9$ cm, som er den 1., 2., 3. og 7. dukken. I dette tilfellet kan den 7. dukken oppbevares inni den 1. dukken, og den 1. dukken kan oppbevares inni den 3. dukken. Det minste antallet dukker som ikke er plassert inni noen annen dukke er $2$.

Inndata 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

Utdata 2

3
1
3
5
0
2
1
3