你在一家外币兑换中心，这里有 $N$ 种货币。

汇率以一个四列的表格形式呈现。你可以在下方看到这样一个表格的例子：

这意味着你可以将 4785 RUB 兑换为 100 EUR，反之亦然，可以将 100 EUR 兑换为 4785 RUB。

该外币兑换中心不收取额外的兑换手续费。

给定这张表格，你需要找出所有货币的汇率等价类。换句话说，你需要为每种货币分配一个整数标签，使得两种货币之间存在 $1:1$ 的兑换率，当且仅当它们具有相同的标签。

兑换中心的表格不包含任何歧义和矛盾。并且，借助该表格可以计算出任意两种货币之间的汇率。

输入格式

第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 10^5$，$1 \le M \le 10^6$），分别表示兑换中心的货币数量和汇率表中的行数。

接下来的 $M$ 行描述汇率表。

每行包含恰好四个整数 $u, v, w_u, w_v$，表示你可以将 $w_u$ 单位的货币 $u$ 兑换为 $w_v$ 单位的货币 $v$（$1 \le u, v \le N$，$1 \le w_u, w_v \le 3 \cdot 10^6$）。

输出格式

输出 $N$ 个整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 是货币 $i$ 的汇率等价类标签（$1 \le c_i \le N$）。

样例

输入样例 1

6 7
1 2 7 2
1 3 1 1
2 4 2 7
2 3 2 7
3 5 7 2
3 6 7 2
4 6 7 2

输出样例 1

1
2
1
1
2
2