Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Walls
Time Limit: 6000MSMemory Limit: 131072K
Total Submissions: 3179Accepted: 523
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]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator