Description

There are N walls. A wall has an infinity height, so it looks like a segment in a plane from high sky. Obviously, they don't intersect. Let's take a series of interesting experiments. Everytime, we put a lovely bird called Xiaoniao in the place. Then, she will choose any one of four possible directions paralleled to axes and disregarded anything else but fly forward. It may occur that she touch a wall and fainted. So poor Xiaoniao is, she always choose the direction which made her fainted as early as possible. You're asked to count, how many times did Xiaoniao touched each wall.

It is guaranteed that each time there will be exactly one direction that makes Xiaoniao faints as early as possible. I.E. She won't have no choice to get faint, neither have more than one direction producing the same fainting time. Xiaoniao won't be placed on a wall, either. Touching an end point of a wall is also considered a touch.

Input

The first line contains N and M (both not exceeding 50,000). M is the number we put Xiaoniao in the place.
The following N lines describe the walls. Each line consists 4 integers x₁, y₁, x₂, y₂, meaning a wall from (x₁,y₁) to (x₂,y₂). The wall is always parallel to the coordinate axes.
The next M lines describe where we put Xiaoniao. Each line consists 2 integers x and y. This means we put Xiaoniao at the point (x,y).

Output

N lines, i-th line contains one integer that is the number of Xiaoniao touches the i-th wall.

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

Source

POJ Monthly--2007.11.25, Zhou Dong