Antimatter Rain

문제

You've heard of acid rain but have you heard of antimatter rain? Antimatter rain is so potent that when it comes into contact with another object, it immediately disintegrates both itself and the object. Kayla's job as a SpaceFleet Researcher is gathering weather data on exotic planets. This time, their assignment is to monitor the antimatter rainfall.

Sensors are set up in the planet's atmosphere and are about to be rained on with antimatter rain. Oh no! Kayla monitors a single 2D section. Each sensor is either a single horizontal strip or a single point. When one or more antimatter droplet fall on a single sensor, all of those droplets and the sensor disintegrate simultaneously. That is, they disappear. All other droplets will drop past where the sensor used to be.

Kayla sees all the antimatter rain drops the moment before they all start to fall. All droplets fall at exactly the same rate.

For each droplet, Kayla wants to know if and where it will disintegrate. Help them out with this demanding task!

Illustration of the first sample. The vertical lines connect the drops to the sensor they hit. The drop with no associated vertical line will not hit any sensor.

입력

The first line of input contains two integers $DD$ ($1\le D\le 1000001\; \backslash leq\; D\; \backslash leq\; 100\backslash ,000$), which is the number of antimatter droplets, and $SS$ ($1\le S\le 1000001\; \backslash leq\; S\; \backslash leq\; 100\backslash ,000$), which is the number of sensors.

The next $DD$ lines describe the droplets, in order. Each of these lines contains two integers $xx$ ($1\le x\le {10}^{9}1\; \backslash leq\; x\; \backslash leq\; 10^9$), which is the $xx$-coordinate of the droplet and $yy$ ($1\le y\le {10}^{9}1\; \backslash leq\; y\; \backslash leq\; 10^9$), which is the $yy$-coordinate of the droplet.

The next $SS$ lines describe the sensors. Each line contains three integers $x_{1}x\_1$, $x_{2}x\_2$ ($1\le x_1\le x_2\le {10}^{9}1\; \backslash leq\; x\_1\; \backslash leq\; x\_2\; \backslash leq\; 10^9$), which is the leftmost and the rightmost $xx$-coordinate of the sensor, and $yy$ ($1\le y\le {10}^{9}1\; \backslash leq\; y\; \backslash leq\; 10^9$), which is the $yy$-coordinate of the sensor.

It is guaranteed that no two drops will start in the same location, no drop will start on any sensor, and no two sensors touch (not even at a single point).

출력

For each droplet, in order, display a single number indicating the $yy$-coordinate that it will disintegrate. If the droplet does not disintegrate, display $00$ instead. These values should appear on separate lines.

5 3
1 8
2 3
2 8
5 8
5 9
3 6 6
1 7 4
1 3 1

4
1
4
6
0

6 3
1 2
4 8
5 10
6 10
7 10
8 10
1 1 1
3 4 3
5 7 9

1
3
9
9
9
0