Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

Language:
Walls
 Time Limit: 6000MS Memory Limit: 131072K Total Submissions: 1842 Accepted: 299 Case Time Limit: 3000MS

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 x1, y1, x2, y2, meaning a wall from (x1,y1) to (x2,y2). 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.

Sample Input

```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```

Sample Output

```1
1
1
1```

Source

[Submit]   [Go Back]   [Status]   [Discuss]