你听说过酸雨，但听说过反物质雨吗？反物质雨威力巨大，当它接触到其他物体时，会立即将自身和该物体同时湮灭。Kayla 作为一名太空舰队研究员，其工作是收集外星行星上的天气数据。这一次，她的任务是监测反物质降雨。

传感器被设置在行星的大气层中，即将迎来反物质雨。糟糕！Kayla 监测的是一个二维截面。每个传感器要么是一条水平线段，要么是一个点。当一个或多个反物质液滴落在一个传感器上时，所有这些液滴和该传感器会同时湮灭。也就是说，它们会消失。其他所有液滴将继续下落，穿过传感器原本所在的位置。

Kayla 在所有反物质雨滴开始下落前的那一刻观察到了它们。所有液滴下落的速度完全相同。

对于每一个液滴，Kayla 都想知道它会在哪里湮灭（如果会湮灭的话）。请帮助她完成这项艰巨的任务！

第一个样例的示意图。垂直线连接了液滴与其击中的传感器。没有关联垂直线的液滴不会击中任何传感器。

输入格式

输入的第一行包含两个整数 $D$ ($1 \le D \le 100\,000$)，表示反物质液滴的数量，以及 $S$ ($1 \le S \le 100\,000$)，表示传感器的数量。

接下来的 $D$ 行按顺序描述液滴。每行包含两个整数 $x$ ($1 \le x \le 10^9$)，表示液滴的 $x$ 坐标，以及 $y$ ($1 \le y \le 10^9$)，表示液滴的 $y$ 坐标。

接下来的 $S$ 行描述传感器。每行包含三个整数 $x_1, x_2$ ($1 \le x_1 \le x_2 \le 10^9$)，表示传感器的最左侧和最右侧 $x$ 坐标，以及 $y$ ($1 \le y \le 10^9$)，表示传感器的 $y$ 坐标。

保证没有两个液滴起始于相同位置，没有液滴起始于任何传感器上，且没有两个传感器接触（即使是在单点处也不接触）。

输出格式

对于每个液滴，按输入顺序输出一个整数，表示它湮灭时的 $y$ 坐标。如果液滴不会湮灭，则输出 $0$。这些值应分别在单独的行中显示。

样例

样例输入 1

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

样例输出 1

4
1
4
6
0

样例输入 2

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

样例输出 2

1
3
9
9
9
0