404341: GYM101484 B Nicoleta's Cleaning

Nicoleta is a very rich and lazy man. He lives in a huge mansion with his sister Marge. Their mansion is perfectly rectangular and has no inner walls. They made it that way so Nicoleta wouldn't need to open doors and avoid walls.

Last night, he invited some friends to play games at his mansion and they made a big mess. Marge is furious about it and demanded that he cleans everything up today.

There are N dirty spots on the mansion's floor and Nicoleta tried to cover them with M expensive rectangular rugs. Each dirty spot on the floor is represented by a point and each rug is represented by a rectangle.

Marge is used to having all rugs parallel to the walls. Nicoleta made sure that no rug is rotated so that she doesn't notice. However, he might have left some rugs overlapping because he is lazy.

He asked you to double check his "cleaning" by counting how many rugs are covering each spot. A rug is covering a spot if the spot is strictly inside the rug's rectangle.

The first line of the input contains two integers N and M (1 ≤ N, M ≤ 10⁵), indicating respectively the number of dirty spots and the number of rectangular rugs.

Each of the following N lines contains two integers: the i-th line contains x_i^s and y_i^s ( - 10⁹ ≤ x_i, y_i ≤ 10⁹), indicating the coordinates of the i-th dirty spot.

Each of the following M lines contains four integers: the i-th line contains x_i^bl, y_i^bl, x_i^tr and y_i^tr ( - 10⁹ ≤ x_i^bl < x_i^tr ≤ 10⁹ and  - 10⁹ ≤ y_i^bl < y_i^tr ≤ 10⁹), indicating respectively the coordinates of the i-th rug bottom left corner and the coordinates of the i-th rug top right corner.

Output N lines each with a single integer: the i-th integer indicating the number of rugs covering the i-th dirty spot.

2 3
0 0
10 10
-10 -10 10 15
5 5 20 20
9 9 11 11

1
2

2 2
0 0
10 10
-1 -100 1 100
-100 -1 100 1

2
0