在摩拉维亚（Moravia）的下维斯特尼采（Dolní Věstonice），考古发现的年代估计约为 28,000 年。因此，我们可以说，我们领土上的文化根源至少可以追溯到那么久远的过去。在这一遗址中，意想不到且鲜为人知的发现之一是地面上一些奇特的、几乎看不见的平行沟槽系统。在其中一些沟槽的尽头，可能放置了祭祀石，可以假设，著名的新石器时代纪念碑——如法国卡纳克（Carnac）的石阵或克拉德诺（Kladno）以西波希米亚的考诺夫石行（Kounov Rows）——就是从这种结构发展而来的。

在史前时代，人类有目的的活动与祭祀以及个人和群体参与想象中的宇宙秩序是密不可分的。在解释古代遗迹时，必须始终牢记这一点。狩猎也是如此。在下维斯特尼采附近，大群迁徙的动物——马、鹿等——经常经过。在狩猎之前，猎人的任务是迷惑与兽群一起移动并可能影响狩猎结果的神灵。因此，猎人们根据祭祀规定改变了他们的移动方式。

沟槽总是起点和终点都在整点上，并且总是与 $X$ 轴平行，也就是说，一条沟槽起点和终点在某些点 $(x_p, y_p)$ 和 $(x_q, y_q)$ 上，满足 $y_p = y_q$。$N$ 名猎人最初位于点 $(1, 0), (2, 0), \dots, (N, 0)$。在每一步中，他们沿 $Y$ 轴正方向移动 $1$ 的距离。每当猎人的位置与沟槽的端点重合时，他就会在一次快速跳跃中移动到该沟槽的另一个端点。即使沟槽的两个端点上都有猎人，这也会顺利发生。如果猎人进入沟槽的任何其他点（非端点），他会直接忽略该沟槽。当猎人前方没有沟槽时，他就会停止移动。

随着猎人们以所述方式改变他们的相对位置，他们迷惑了兽群的神灵，这有助于确保狩猎成功。可以假设，在这些猎人中，也有一些人如果活在今天，能够直接为每个猎人确定他的最终位置——并且能够编写一个计算机程序来解决这个任务。

图 1：三名猎人穿过有沟槽区域的示例，猎人用彩色圆圈表示，沟槽用线段表示。从左到右：猎人的初始位置、第一次移动后的位置以及最终位置。

输入格式

第一行包含两个整数 $N, M$（$1 \le N \le 2 \cdot 10^5$，$0 \le M \le 2 \cdot 10^5$），分别表示猎人的数量和沟槽的数量。

接下来的 $M$ 行，每行包含 $4$ 个整数 $x_p, y_p, x_q, y_q$，通过 $(x_p, y_p)$ 和 $(x_q, y_q)$ 指定一条沟槽的两个端点。

保证任意两个端点（即使来自不同的沟槽）都不会重合，并且对于每条沟槽，其端点坐标满足 $y_p = y_q$。保证 $1 \le y_p, y_q \le 10^9$ 且 $1 \le x_p, x_q \le N$。

输出格式

输出恰好 $N$ 行。在输出的第 $i$ 行（从 $1$ 开始索引）中，指出最初位于 $(i, 0)$ 的猎人在狩猎开始前最终停在的 $x$ 坐标。

样例

输入样例 1

3 2
1 1 2 1
2 2 3 2

输出样例 1

3
1
2