Você pretende abrir uma loja de bonecas matryoshka e, para isso, encomendou $N$ bonecas a uma fábrica. Elas são numeradas de $1$ a $N$. A $i$-ésima boneca ($1\le i\le N$) pode ser considerada um cilindro circular reto oco, com diâmetro da base de $R_i$ cm e altura de $H_i$ cm.

As bonecas podem ser guardadas umas dentro das outras. Cada boneca pode conter apenas uma outra boneca cujo diâmetro da base e cuja altura sejam ambos estritamente menores que os seus. A boneca colocada dentro de outra pode, por sua vez, conter outra boneca.

Um dia, a fábrica entrou em contato com você. Como não consegue preparar todas as $N$ bonecas encomendadas de uma só vez, ela enviará antecipadamente todas as bonecas cujo diâmetro da base seja pelo menos $A$ cm e cuja altura seja no máximo $B$ cm.

Os valores de $A$ e $B$ podem mudar repentinamente. Por isso, você decidiu calcular antecipadamente, para cada um dos $Q$ pares $(A_j,B_j)$ ($1\le j\le Q$), o número mínimo de bonecas que não ficam dentro de nenhuma outra quando as bonecas entregues antecipadamente são guardadas umas dentro das outras.

Tarefa

São fornecidas as informações sobre o diâmetro da base e a altura de cada boneca, além de $Q$ pares $(A_j,B_j)$ ($1\le j\le Q$). Escreva um programa que, para cada par, calcule o número mínimo de bonecas que não ficam dentro de nenhuma outra ao guardar as bonecas entregues antecipadamente umas dentro das outras.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém os inteiros $N,Q$, separados por um espaço. Isso indica que foram encomendadas $N$ bonecas e que são fornecidos $Q$ pares de valores de $A,B$.
• A $i$-ésima das $N$ linhas seguintes ($1\le i\le N$) contém os inteiros $R_i,H_i$, separados por um espaço. Isso indica que a $i$-ésima boneca tem diâmetro da base de $R_i$ cm e altura de $H_i$ cm.
• A $j$-ésima das $Q$ linhas seguintes ($1\le j\le Q$) contém os inteiros $A_j,B_j$, separados por um espaço.

Saída

A saída deve conter $Q$ linhas. Na $j$-ésima linha ($1\le j\le Q$), escreva, para o par $(A_j,B_j)$, o número mínimo de bonecas que não ficam dentro de nenhuma outra ao guardar as bonecas entregues antecipadamente umas dentro das outras.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

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

Subtarefas

Subtarefa 1 [11 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 2 [15 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 3 [25 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 4 [49 pontos]

Não há restrições adicionais.

Exemplos

Entrada 1

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

Saída 1

0
1
2

Nota

• Para $(A,B)=(10,5)$, nenhuma boneca possui diâmetro da base de pelo menos $10$ cm e altura de no máximo $5$ cm. Portanto, a saída é 0.
• Para $(A,B)=(3,5)$, chegam as bonecas cujo diâmetro da base é pelo menos $3$ cm e cuja altura é no máximo $5$ cm, ou seja, as bonecas de números $1$ e $7$. A boneca $7$ pode ser colocada dentro da boneca $1$. O número mínimo de bonecas que não ficam dentro de nenhuma outra é $1$.
• Para $(A,B)=(3,9)$, chegam as bonecas cujo diâmetro da base é pelo menos $3$ cm e cuja altura é no máximo $9$ cm, ou seja, as bonecas de números $1,2,3,7$. Nesse caso, a boneca $7$ pode ser colocada dentro da boneca $1$, que pode ser colocada dentro da boneca $3$. O número mínimo de bonecas que não ficam dentro de nenhuma outra é $2$.

Entrada 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

Saída 2

3
1
3
5
0
2
1
3