题目描述

有 N 面墙，每面墙的高度无限，从高空看就像平面中的一条线段。这些墙互不相交。我们进行一系列有趣的实验：每次将一只可爱的小鸟（Xiaoniao）放在某个位置，它会从平行于坐标轴的四个方向（上、下、左、右）中选择一个飞行，直到撞到墙后晕倒。小鸟总是选择能最快撞墙的方向（即路径最短的方向）。题目保证每次有且仅有一个方向满足该条件，且小鸟初始位置不会在墙上。触碰墙的端点也算撞击。

你需要统计每面墙被小鸟撞击的次数。

输入格式

• 第一行：N（墙的数量）和 M（实验次数，即小鸟放置次数），均不超过 50,000。
• 接下来 N 行：每行四个整数 x1, y1, x2, y2，表示一面从 (x1,y1) 到 (x2,y2) 的墙（平行于坐标轴）。
• 接下来 M 行：每行两个整数 x, y，表示小鸟的初始位置 (x,y)。

输出格式

N 行，第 i 行输出第 i 面墙被撞击的次数。

输入样例 1

4 4
10 0 10 40
0 40 40 40
10 10 50 10
40 50 40 10
15 12
12 35
35 38
38 15

输出样例 1

1
1
1
1

题目来源

POJ Monthly--2007.11.25, Zhou Dong