레이팅 미적용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 colours, but it is possible that there were more
balls having the same colour. 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 colours. 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
colours 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.
The first line of input contains the positive integers \(N\) (\(1 \le N \le 80\,000\)), the number of sheets,
and \(M\) (\(1 \le M \le 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 \le A_{i}\), \(B_{i} \le 10^{9}\)) and the upper right corner \(C_{i}\), \(D_{i}\), (\(1 \le C_{i}\), \(D_{i} \le 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_{i}\), Y_{i} (1 ≤
\(X_{j}\), \(Y_{j} \le 10^{9}\)), and \(K_{j}\) (\(1 \le K_{j} \le 10^{9}\)), the colour label of the j^{th} ball.
The i^{th} of \(N\) lines must contain the number of new colours on the i^{th} sheet.
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
1
0
3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 1
2 6 2
4 7 3
3
2
1
1 3
1 1 7 7
2 6 2
4 7 3
4 4 1
3