时间限制：1秒　　内存限制：256M

---

【问题描述】

　　Farmer John 的 \(N（1≤N≤10^5）\) 头奶牛每头都喜欢日常沿围着牧场的栅栏散步。不幸的是，每当一头奶牛走过栅栏柱子时，她就会碰到它，这要求 Farmer John 需要定期重新粉刷栅栏柱子。

　　栅栏由 \(P\)（\(4≤P≤2⋅10^5，P\) 为偶数） 根柱子组成，每根柱子的位置是 FJ 农场地图上的一个不同的二维坐标点 \((x,y)（0≤x,y≤10^9）\)。每根柱子通过垂直或水平线段的栅栏连接到两根相邻的柱子，因此整个栅栏可以被视为各边平行于 \(x\) 轴或 \(y\) 轴的一个多边形（最后一根柱子连回第一根柱子，确保围栏形成一个包围牧场的闭环）。栅栏多边形是「规则的」，体现在栅栏段仅可能在其端点处重合，每根柱子恰好属于两个栅栏段，同时每两个在端点处相交的栅栏段都是垂直的。

　　每头奶牛的日常散步都有一个偏好的起始和结束位置，均为沿栅栏的某个点（可能在柱子处，也可能不在）。每头奶牛日常散步时沿着栅栏行走，从起始位置开始，到结束位置结束。由于栅栏形成闭环，奶牛有两条路线可以选择。由于奶牛是一种有点懒的生物，每头奶牛都会选择距离较短的方向沿栅栏行走。值得注意的是，这个选择总是明确的——不存在并列的情况！

　　一头奶牛会触碰一根栅栏柱子，当她走过这根柱子，或者当这根栅栏柱子是她散步的起点或终点时。请帮助 FJ 计算每个栅栏柱子每天所经历的触碰次数，以便他知道接下来要重新粉刷哪根柱子。

　　可以证明，给定所有柱子的位置，组成的栅栏仅有唯一的可能性。

【输入格式】

　　输入的第一行包含 \(N\) 和 \(P\)。
　　以下 \(P\) 行的每一行包含两个整数，表示栅栏柱子的位置，没有特定的顺序。
　　以下 \(N\) 行的每一行包含四个整数 \(x_1\ y_1\ x_2\ y_2\) ，表示一头奶牛的起始位置 \((x_1,y_1)\) 和结束位置 \((x_2 ,y_2)\)。

【输出格式】

　　输出 \(P\) 个整数，包含每个栅栏柱子所经历的触碰次数。

【输入输出样例1】

　Input

5 4
3 1
1 5
3 5
1 1
2 1 1 5
1 5 3 4
3 1 3 5
2 1 2 1
3 2 3 3

　Output

1
2
2
1

【样例1解释】

　　柱子以如下方式由栅栏段连接：(3,1)↔(3,5)↔(1,5)↔(1,1)↔(3,1)，各奶牛接触的柱子如下：
　　　柱子 2 和 4。
　　　柱子 2 和 3。
　　　柱子 1 和 3。
　　　无。
　　　无。

【输入输出样例2】

　Input

2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 3

　Output

1
0
0
0
1
1
1
2

【输入输出样例2】

　Input

1 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 2

　Output

1
1
1
1
1
0
0
0
0
0
0
0

【测试点性质】

　　测试点 \(4−6：N,P≤1000\)。
　　测试点 \(7−9：\)所有位置均有 \(0≤x,y≤1000\)。
　　测试点 \(10−15\)：没有额外限制。

【来源】

　　Mr.he