Du möchtest ein Geschäft eröffnen, das Matroschka-Puppen verkauft. Dazu hast du $N$ Matroschka-Puppen bei einer Fabrik bestellt. Sie sind von $1$ bis $N$ nummeriert. Die $i$-te Matroschka-Puppe ($1\le i\le N$) kann als hohler gerader Kreiszylinder mit einem Grundflächendurchmesser von $R_i$ cm und einer Höhe von $H_i$ cm betrachtet werden.

Matroschka-Puppen können ineinandergeschachtelt aufbewahrt werden. Jede Matroschka-Puppe kann genau eine andere Matroschka-Puppe aufnehmen, deren Grundflächendurchmesser und Höhe beide kleiner sind. Die aufgenommene Matroschka-Puppe darf ihrerseits eine andere Matroschka-Puppe enthalten.

Eines Tages erhältst du eine Nachricht von der Fabrik, bei der du die Matroschka-Puppen bestellt hast. Da nicht alle $N$ bestellten Matroschka-Puppen auf einmal bereitgestellt werden können, werden vorab alle Puppen unter den $N$ bestellten geliefert, deren Grundflächendurchmesser mindestens $A$ cm und deren Höhe höchstens $B$ cm beträgt.

Die Werte von $A$ und $B$ könnten kurzfristig geändert werden. Daher beschließt du, für jedes von $Q$ Paaren $(A_j,B_j)$ ($1\le j\le Q$) im Voraus die kleinstmögliche Anzahl von Matroschka-Puppen zu bestimmen, die in keiner anderen Matroschka-Puppe enthalten sind, wenn die vorab gelieferten Matroschka-Puppen ineinandergeschachtelt aufbewahrt werden.

Aufgabe

Gegeben sind der Grundflächendurchmesser und die Höhe jeder Matroschka-Puppe sowie $Q$ Paare $(A_j,B_j)$ ($1\le j\le Q$). Schreibe ein Programm, das für jedes Paar die kleinstmögliche Anzahl von Matroschka-Puppen bestimmt, die in keiner anderen Matroschka-Puppe enthalten sind, wenn die vorab gelieferten Matroschka-Puppen ineinandergeschachtelt aufbewahrt werden.

Eingabe

Lies die folgenden Daten von der Standardeingabe ein.

• Die erste Zeile enthält die durch ein Leerzeichen getrennten ganzen Zahlen $N,Q$. Dies bedeutet, dass $N$ Matroschka-Puppen bestellt wurden und $Q$ Wertepaare für $A,B$ gegeben sind.
• Die $i$-te Zeile ($1\le i\le N$) der folgenden $N$ Zeilen enthält die durch ein Leerzeichen getrennten ganzen Zahlen $R_i,H_i$. Dies bedeutet, dass die $i$-te Matroschka-Puppe einen Grundflächendurchmesser von $R_i$ cm und eine Höhe von $H_i$ cm hat.
• Die $j$-te Zeile ($1\le j\le Q$) der folgenden $Q$ Zeilen enthält die durch ein Leerzeichen getrennten ganzen Zahlen $A_j,B_j$.

Ausgabe

Die Ausgabe besteht aus $Q$ Zeilen. Gib in der $j$-ten Zeile ($1\le j\le Q$) für das Paar $(A_j,B_j)$ die kleinstmögliche Anzahl von Matroschka-Puppen aus, die in keiner anderen Matroschka-Puppe enthalten sind, wenn die vorab gelieferten Matroschka-Puppen ineinandergeschachtelt aufbewahrt werden.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

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

Teilaufgaben

Teilaufgabe 1 [11 Punkte]

Die folgenden Bedingungen gelten.

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

Teilaufgabe 2 [15 Punkte]

Die folgenden Bedingungen gelten.

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

Teilaufgabe 3 [25 Punkte]

Die folgenden Bedingungen gelten.

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

Teilaufgabe 4 [49 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Ausgabe 1

0
1
2

Hinweis

• Für $(A,B)=(10,5)$ gibt es keine Matroschka-Puppe, deren Grundflächendurchmesser mindestens $10$ cm und deren Höhe höchstens $5$ cm beträgt. Daher wird 0 ausgegeben.
• Für $(A,B)=(3,5)$ werden die Matroschka-Puppen mit einem Grundflächendurchmesser von mindestens $3$ cm und einer Höhe von höchstens $5$ cm geliefert, also die Puppen Nummer $1$ und $7$. Die Matroschka-Puppe Nummer $7$ kann in der Matroschka-Puppe Nummer $1$ aufbewahrt werden. Die kleinstmögliche Anzahl von Matroschka-Puppen, die in keiner anderen Matroschka-Puppe enthalten sind, beträgt $1$.
• Für $(A,B)=(3,9)$ werden die Matroschka-Puppen mit einem Grundflächendurchmesser von mindestens $3$ cm und einer Höhe von höchstens $9$ cm geliefert, also die Puppen Nummer $1$, $2$, $3$ und $7$. In diesem Fall kann die Matroschka-Puppe Nummer $7$ in der Matroschka-Puppe Nummer $1$ und die Matroschka-Puppe Nummer $1$ in der Matroschka-Puppe Nummer $3$ aufbewahrt werden. Die kleinstmögliche Anzahl von Matroschka-Puppen, die in keiner anderen Matroschka-Puppe enthalten sind, beträgt $2$.

Eingabe 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

Ausgabe 2

3
1
3
5
0
2
1
3