题目描述

小明选中了若干个实体以及若干个一次性删除 trigger，并将它们胡乱地在制图器中摆了一通。这些实体会以相同的速度下落，并在接触到任意一个删除trigger时就会被删除。值得一提的是，由于游戏代码写成了屎山，所以**删除 trigger 的逻辑是在接触到任意一个实体的时候删除所有与自己接触的实体。**每个删除 trigger 只会工作一次。

游（shi）戏（shan）地图是一个二维的平面，在二维坐标中 $y$ 轴是竖直方向，也就是说实体在重力的作用下下落即为 $y$ 坐标减小，经过一分钟的制（la）图（shi），小明一共放了 $n$ 个实体和 $m$ 个 trigger，第 $i$ 个实体位于坐标 $(x_i,y_i)$ 处。由于小明对制图器的使用不能说是不太熟悉，只能说是一窍不通，所以小明只会摆放一类 trigger，也就是位于形如从 $(l_i,v_i)$ 到 $(r_i,v_i)$ 的一片区域（包含两端）的地方。

小明准备去玩（chi）一下自己做的图（shi），在此之前，你能预测一下每个实体是在下落至纵坐标为多少的时候被删除的吗？当然，若一个实体没有被删除，也请你将这一情况预测出来。

输入格式

第一行两个正整数 $n,m$，表示实体的数量和删除 trigger 的数量。

之后的 $n$ 行，每行两个正整数 $x_i,y_i$，表示每一个实体的位置。

之后的 $m$ 行，每行三个正整数 $l_i,r_i,v_i$，表示每一个 trigger 的位置。

输出格式

共 $n$ 行，每行一个非负整数表示每个实体被删除时的纵坐标。特别地，若一个实体一直未被删除，则输出 $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

其余样例见下发文件，其分别满足下表每一个子任务的限制。

数据范围

对于 $100\%$ 的数据，$1\le n,m\le10^5,1\le x_i,y_i,v_i\le10^9,1\le l_i\le r_i\le10^9$。保证没有实体和删除 trigger 在一开始就是重叠的，保证同一个位置不会出现两个及以上的实体，保证删除 trigger 不会重叠。

本题采用子任务测试，且会有极大的合理子任务依赖。只有你通过了一个子任务中的所有测试点，且通过了其所有依赖子任务时，才可得到该子任务的分数。