Dirty Sheets

Little Donald washed and dried N white sheets in his backyard. He arranged them as axis‐parallel rectangles so that none of them touch on the tips or the sides and none of their sides intersect. It is possible that a smaller sheet is placed completely on top of a bigger one, resulting in a stack.

While Donald slept, his friend Kim shot M paintballs at the sheets. Each shot is represented as a point in the infinite coordinate system. When a shot hits the topmost sheet at that point, the paint color bleeds down to all the sheets underneath that cover that point. (A shot that misses all the sheets has no effect.)

You are given the positions of the sheets and the coordinates and colors of the paintball shots. Compute for each sheet the number of new (distinct) colors it ended up with.

The sheets are given as rectangles. For a sheet with bottom‐left corner (x₁, y₁) and top‐right corner (x₂, y₂), a shot at point (x, y) hits the sheet if and only if \[ x_1 < x < x_2 \quad \text{and} \quad y_1 < y < y_2. \]

inputFormat

The first line contains two integers N and M (1 ≤ N, M ≤ 105): the number of sheets and the number of paintball shots.

The next N lines each contain four numbers x₁ y₁ x₂ y₂ (x₁ < x₂ and y₁ < y₂), describing the coordinates of a sheet's bottom‐left and top‐right corners. It is guaranteed that the sides of any two sheets do not touch or intersect.

The next M lines describe the paintball shots. Each shot is given by two numbers x and y followed by a color string. A shot at (x, y) hits a sheet if and only if x₁ < x < x₂ and y₁ < y < y₂.

outputFormat

Output N lines. The i-th line should contain a single integer representing the number of distinct new colors that appear on the i-th sheet (in the input order) after all the shots.

sample

2 3
0 0 10 10
2 2 8 8
5 5 red
3 3 blue
11 11 green

2
2