Þú ert að skipuleggja að opna verslun sem selur babuskudúkkur (Matryoshka). Þú hefur pantað $N$ babuskudúkkur frá verksmiðju, númeraðar frá $1$ til $N$. Líta má á $i$-tu ($1 \le i \le N$) babuskudúkkuna sem holan réttan hringstrokk með þvermál grunnflatar $R_i$ cm og hæð $H_i$ cm.

Hægt er að geyma babuskudúkkur með því að raða þeim hverri inn í aðra. Hver babuskudúkka getur innihaldið í mesta lagi eina aðra babuskudúkku, að því tilskildu að bæði þvermál grunnflatar og hæð dúkkunnar sem á að setja inn í séu strangt minni en á ytri dúkkunni. Dúkka sem er inni í annarri dúkku getur sjálf innihaldið aðra dúkku.

Dag einn fékkstu skilaboð frá verksmiðjunni. Þar sem þeir geta ekki útbúið allar $N$ dúkkurnar í einu munu þeir senda þér allar dúkkurnar sem hafa þvermál grunnflatar að minnsta kosti $A$ cm og hæð í mesta lagi $B$ cm.

Gildin á $A$ og $B$ geta breyst skyndilega. Því hefur þú ákveðið að reikna út fyrir fram, fyrir hvert af $Q$ pörunum $(A_j, B_j)$ ($1 \le j \le Q$), lágmarksfjölda babuskudúkka sem eru ekki inni í neinni annarri dúkku þegar dúkkunum sem berast er raðað hverri inn í aðra til geymslu.

Inntak

Lestu eftirfarandi gögn af staðalinntaki:

• Fyrsta línan inniheldur tvær heiltölur $N$ og $Q$, aðskildar með bili. Þetta gefur til kynna að það séu $N$ pantaðar babuskudúkkur og $Q$ pör af $(A, B)$ gildum.
• $i$-ta línan af næstu $N$ línum ($1 \le i \le N$) inniheldur tvær heiltölur $R_i$ og $H_i$, aðskildar með bili. Þetta gefur til kynna að $i$-ta dúkkan hafi þvermál grunnflatar $R_i$ cm og hæð $H_i$ cm.
• $j$-ta línan af næstu $Q$ línum ($1 \le j \le Q$) inniheldur tvær heiltölur $A_j$ og $B_j$, aðskildar með bili.

Úttak

Úttakið á að samanstanda af $Q$ línum. $j$-ta línan ($1 \le j \le Q$) á að innihalda lágmarksfjölda babuskudúkka sem eru ekki inni í neinni annarri dúkku fyrir parið $(A_j, B_j)$ þegar dúkkunum sem berast er raðað hverri inn í aðra til geymslu.

Takmarkanir

Öll inntaksgögn uppfylla eftirfarandi skilyrði:

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

Undirverkefni

Undirverkefni 1 [11 stig]

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

Undirverkefni 2 [15 stig]

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

Undirverkefni 3 [25 stig]

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

Undirverkefni 4 [49 stig]

• Engar frekari takmarkanir.

Dæmi

Inntak 1

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

Úttak 1

0
1
2

Athugasemd

• Þegar $(A, B) = (10, 5)$ eru engar dúkkur með þvermál grunnflatar að minnsta kosti $10$ cm og hæð í mesta lagi $5$ cm, svo skrifaðu út $0$.
• Þegar $(A, B) = (3, 5)$ berast dúkkurnar með þvermál grunnflatar að minnsta kosti $3$ cm og hæð í mesta lagi $5$ cm, sem eru 1. og 7. dúkkan. Hægt er að geyma 7. dúkkuna inni í 1. dúkkunni. Lágmarksfjöldi dúkka sem eru ekki inni í neinni annarri dúkku er $1$.
• Þegar $(A, B) = (3, 9)$ berast dúkkurnar með þvermál grunnflatar að minnsta kosti $3$ cm og hæð í mesta lagi $9$ cm, sem eru 1., 2., 3. og 7. dúkkan. Í þessu tilviki er hægt að geyma 7. dúkkuna inni í 1. dúkkunni, og 1. dúkkuna inni í 3. dúkkunni. Lágmarksfjöldi dúkka sem eru ekki inni í neinni annarri dúkku er $2$.

Inntak 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

Úttak 2

3
1
3
5
0
2
1
3