Du planerar att öppna en butik som säljer matrjosjkadockor. Du har beställt $N$ matrjosjkadockor från en fabrik, numrerade från $1$ till $N$. Den $i$-te ($1 \le i \le N$) matrjosjkadockan kan betraktas som en ihålig rät cirkulär cylinder med en basdiameter på $R_i$ cm och en höjd på $H_i$ cm.

Matrjosjkadockor kan förvaras genom att placera dem inuti varandra. Varje matrjosjkadocka kan innehålla högst en annan matrjosjkadocka, förutsatt att både basdiametern och höjden på dockan som ska placeras inuti är strikt mindre än motsvarande mått på den omgivande dockan. En docka som ligger inuti en annan docka kan i sin tur innehålla en annan docka.

En dag fick du ett meddelande från fabriken. Eftersom de inte kan färdigställa alla $N$ dockor på en gång kommer de att skicka dig alla dockor som har en basdiameter på minst $A$ cm och en höjd på högst $B$ cm.

Värdena på $A$ och $B$ kan ändras plötsligt. Därför har du för vart och ett av de $Q$ paren $(A_j, B_j)$ ($1 \le j \le Q$) bestämt dig för att i förväg beräkna det minsta antalet matrjosjkadockor som inte ligger inuti någon annan docka när de dockor som anländer placeras inuti varandra för förvaring.

Indata

Läs följande data från standardindata:

• Den första raden innehåller två heltal $N$ och $Q$, separerade med ett mellanslag. Detta anger att det finns $N$ beställda matrjosjkadockor och $Q$ par av $(A, B)$-värden.
• Den $i$-te raden av de följande $N$ raderna ($1 \le i \le N$) innehåller två heltal $R_i$ och $H_i$, separerade med ett mellanslag. Detta anger att den $i$-te dockan har en basdiameter på $R_i$ cm och en höjd på $H_i$ cm.
• Den $j$-te raden av de följande $Q$ raderna ($1 \le j \le Q$) innehåller två heltal $A_j$ och $B_j$, separerade med ett mellanslag.

Utdata

Utdata ska bestå av $Q$ rader. Den $j$-te raden ($1 \le j \le Q$) ska innehålla det minsta antalet matrjosjkadockor som inte ligger inuti någon annan docka för paret $(A_j, B_j)$ när de dockor som anländer placeras inuti varandra för förvaring.

Begränsningar

All indata uppfyller följande villkor:

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

Delproblem

Delproblem 1 [11 poäng]

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

Delproblem 2 [15 poäng]

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

Delproblem 3 [25 poäng]

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

Delproblem 4 [49 poäng]

• Inga ytterligare begränsningar.

Exempel

Indata 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

Förklaring

• När $(A, B) = (10, 5)$ finns det inga dockor med en basdiameter på minst $10$ cm och en höjd på högst $5$ cm, så skriv ut $0$.
• När $(A, B) = (3, 5)$ anländer dockorna med en basdiameter på minst $3$ cm och en höjd på högst $5$ cm, vilket är den 1:a och den 7:e dockan. Den 7:e dockan kan förvaras inuti den 1:a dockan. Det minsta antalet dockor som inte ligger inuti någon annan docka är $1$.
• När $(A, B) = (3, 9)$ anländer dockorna med en basdiameter på minst $3$ cm och en höjd på högst $9$ cm, vilket är den 1:a, 2:a, 3:e och 7:e dockan. I detta fall kan den 7:e dockan förvaras inuti den 1:a dockan, och den 1:a dockan kan förvaras inuti den 3:e dockan. Det minsta antalet dockor som inte ligger inuti någon annan docka är $2$.

Indata 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