Sheets and Paintballs

Time limit2sMemory limit512 MB

Summary

Given axis-aligned rectangles and colored points, count the distinct color labels that reach each rectangle along the vertical stacking order.

Level: Hard8 of 10
Topics: Sorting, Segment tree, Simulation, DFS
Solved: No attempts yet

Problem

One day little Donald washed all $N$ of his white sheets. After washing them he spread them out on the ground in his backyard to dry. No two sheets touch at a corner or along an edge, and no two edges cross, but a smaller sheet may lie entirely on top of a bigger one, and one sheet may cover another one completely. Once the sheets were laid out, Donald went to bed.

Donald's friend Kim heard that the sheets were drying outside and decided to play a trick. In the attic Kim found his father's paintball gun and $M$ paintballs. The balls come in several colours, and several balls may share the same colour. As soon as Donald fell asleep, Kim walked into the backyard and started shooting at the sheets. Sheets soak up paint, so when the topmost sheet is hit, its colour bleeds down to every sheet lying beneath it. Kim used up all the balls and left in a good mood.

In the morning Donald came out to collect the sheets and found a pile of colours he had never seen. Donald likes exact data and is too shocked to think, so he asks you to count how many new colours ended up on each sheet.

Model the backyard as an infinite coordinate plane, each sheet as a rectangle with sides parallel to the axes, and each shot as a point on that plane. A shot that lands on the boundary of a sheet counts as a hit on that sheet.

A shot may miss every sheet. The coordinates of the shots are pairwise different.

Input

The first line contains the number of sheets $N$ and the number of paintballs $M$ . ( $1 \le N \le 80000$ , $1 \le M \le 80000$ )

The $i$ -th of the next $N$ lines contains the lower left corner $A_i$ , $B_i$ and the upper right corner $C_i$ , $D_i$ of the $i$ -th sheet. ( $1 \le A_i < C_i \le 10^9$ , $1 \le B_i < D_i \le 10^9$ )

The $j$ -th of the following $M$ lines contains the coordinates $X_j$ , $Y_j$ where Kim's $j$ -th shot landed and the colour label $K_j$ of that ball. ( $1 \le X_j \le 10^9$ , $1 \le Y_j \le 10^9$ , $1 \le K_j \le 10^9$ )

Output

Print $N$ lines. The $i$ -th line contains the number of new colours on the $i$ -th sheet.

Hint

In the pictures the number next to a point is the colour label of that shot.

First example

The picture for the first example.

Second example

The picture for the second example.

Examples3

Example 1
Input
```
2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2
```
Expected output
```
1
0
```

Example 2

Input

Expected output

3
2
1

Example 3
Input
```
1 3
1 1 7 7
2 6 2
4 7 3
4 4 1
```
Expected output
```
3
```