Problem Description

Little Donald decided to wash all N of his white sheets one day. After washing them, he put them to dry on the ground in his backyard. Donald placed the sheets so that none of them touch on the tips or the sides and that none of their sides intersect, but it is possible that he placed smaller sheets on top of bigger ones, or that a sheet is completely covering another sheet. After doing this, Donald went to bed.

Donald’s friend Kim somehow got the information that Donald is drying his sheets and decided to mess with him. He found a paintball gun from his father in the attic. Along with the gun, there were M paintball balls in different colors, but it is possible that there were more balls having the same color. As soon as Donald fell asleep, Kim walked into his backyard and started shooting the sheets with his paintball gun. We all know that sheets bleed, so when Kim shoots the topmost sheet, that sheet would bleed the color of the ball down to all of the sheets beneath it. After Kim used all the balls, he happily left Donald’s backyard.

When Donald woke up and went to get his sheets, shock ensued. On most of Donald’s sheets, there was a number of new colors. Since Donald is very interested in correct data, and he’s in shock and not able to think, he is asking you to tell him the number of new colors on each sheet.

We can represent Donald’s backyard as an infinite coordinate system, and the sheets as rectangles parallel to the coordinate axes. Kim’s shots can be represented as points in that system.

Please note: it is possible that Kim’s shot missed all the sheets, but coordinates of each shot are unique.

Input Format

The first line of input contains the positive integers N (1 ≤ N ≤ 80,000), the number of sheets, and M (1 ≤ M ≤ 80,000), the number of paintball balls.

The $i^{th}$ of the following N lines contains four numbers: the coordinates of the lower left corner $A_i$, $B_i$ (1 ≤ $A_i$, $B_i$ ≤ $10^9$) and the upper right corner $C_i$, $D_i$ (1 ≤ $C_i$, $D_i$ ≤ $10^9$) of the $i^{th}$ sheet.

The $j^{th}$ of the following M lines contains the coordinates where Kim’s $j^{th}$ shot landed $X_j$, $Y_j$ (1 ≤ $X_j$, $Y_j$ ≤ $10^9$), and $K_j$ (1 ≤ $K_j$ ≤ $10^9$), the color label of the $j^{th}$ ball.

Output Format

The $i^{th}$ of N lines must contain the number of new colors on the $i^{th}$ sheet.

Sample Input and Output

Sample Input #1

2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2

Sample Output #1

1
0

Sample Input #2

3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 1
2 6 2
4 7 3

Sample Output #2

3
2
1

Sample Input #3

1 3
1 1 7 7
2 6 2
4 7 3
4 4 1

Sample Output #3

3

见题面 Input 部分

见题面 Output 部分