题目描述

二维平面上有 $N$ 只怪物。怪物编号从 $1$ 到 $N$，第 $i$ 只怪物的坐标是 $(X_i,Y_i)$。保证 $(X_i,Y_i) \neq (0,0)$。（每只怪物可以看作静止的点，没有体积大小。）

高桥站在平面的坐标原点。他的眼睛会持续发射一道强力激光，瞬间消灭他面朝方向上所有怪物。如果他面朝的方向上有多只怪物，则这些怪物会被瞬间全部消灭。

青木进行 $Q$ 组互相独立的假想实验。第 $j$ 次假想实验如下：

• 初始时，高桥面朝怪物 $A_j$ 的方向。接下来高桥会顺时针旋转，当他刚好转到面朝怪物 $B_j$ 的方向时立刻停止。求在此过程中，一共会消灭多少只怪物（包含 $A_j$、$B_j$）。若怪物 $A_j$ 和 $B_j$ 在原点的同一方向上，则高桥完全不会发生旋转。

请求出每组假想实验的答案。

数据范围

• $2\leq N \leq 2\times 10^5$
• $1\leq Q \leq 2\times 10^5$
• $-10^9\leq X_i,Y_i \leq 10^9$
• $(X_i,Y_i)\neq (0,0)$
• $1\leq A_j,B_j\leq N$
• $A_j\neq B_j$
• 所有输入均为整数。

输入格式

输入由标准输入给出，格式如下：

$N$ $Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

输出格式

输出 $Q$ 行。第 $j$ 行（$1\le j\le Q$）输出第 $j$ 次假想实验的答案。

样例输入1

5 4
0 1
1 -2
1 0
-2 0
3 0
4 1
1 4
5 4
3 5

样例输出1

2
5
4
2

• 第1组假想实验：初始高桥朝向怪物4（此时怪物4被消灭）。从该位置开始顺时针旋转，刚好转到朝向怪物1时停止（怪物1被消灭）。途中没有扫过其他怪物，答案为 $2$。
• 第2组假想实验：初始高桥朝向怪物1（怪物1被消灭）。顺时针旋转途中依次扫过怪物3、5，将其消灭；继续旋转扫过怪物2，将其消灭；最终转到朝向怪物4时停止（怪物4被消灭）。答案为 $5$。
• 第3组假想实验：被消灭的怪物为 \(\(3,5\),2,4\)，答案为 $4$。
• 第4组假想实验：被消灭的怪物为 \(3,5\)，答案为 $2$。注意怪物3、5处在原点的同一个方向，高桥不会发生旋转。

样例输入2

2 1
1 2
1 2
1 2

样例输出2

2

可以有多只怪物拥有完全相同的坐标。

样例输入3

8 10
-84 -60
-100 8
77 55
-14 -10
50 -4
-63 -45
26 -17
-7 -5
3 7
2 4
8 4
8 4
7 1
1 7
6 3
4 7
4 5
2 6

样例输出3

3
8
4
4
5
8
6
8
7
8

原题链接

原题链接