人们总是喜欢给事物排名。确实，在大多数时候，排名毫无意义，除非你正在向老板提交年终报告。

在建设世界一流大学的推动下，许多大学都在竭尽全力提升排名。发表论文、申请资金、提高多样性……这些都太难了，而且你的成果可能无法被《美国新闻与世界报道》（US News）或《泰晤士高等教育》（Times）等机构公平地评判！然而，一些大学更聪明——他们发布自己的排名，这使得排名在间接上变得更好。例如，利用上海交通大学制作的上海软科世界大学学术排名（ARWU），Desprado2 可以证明他的学校比麻省理工学院（MIT）更好。

https://www.zizhengfang.com/applets/transitivity

总之，除非你正在找工作并需要吹嘘你的学校，否则这只是个笑话。但与此同时，Desprado2 提出了一个问题：假设总共有 $n$ 所大学，他收集了 $m$ 个大学排名。为简单起见，所有大学都用 $1$ 到 $n$ 的数字表示。在这里，Desprado2 定义：当且仅当存在一个大学排名，使得大学 $x$ 的排名高于大学 $y$ 时，大学 $x$ 直接优于大学 $y$。此外，Desprado2 定义：当且仅当存在一个序列 $\{s_1, s_2, \dots, s_k\}$ ($k \ge 2$)，使得：

• $s_1 = x, s_k = y$
• $\forall i \in \{1, 2, \dots, k - 1\}$，大学 $s_i$ 直接优于大学 $s_{i+1}$

则大学 $x$ 优于大学 $y$。

对于每一所大学，Desprado2 希望你告诉他，它优于多少所其他大学。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 5 \times 10^5, 1 \le m \le 5 \times 10^5, 1 \le n \times m \le 10^6$)，分别表示考虑的大学数量和大学排名的数量。

接下来 $m$ 行。第 $i$ 行包含 $n$ 个不同的整数 $s_{i,1}, s_{i,2}, \dots, s_{i,n}$ ($1 \le s_{i,j} \le n$)，表示第 $i$ 个大学排名的顺序（从高到低）。

输出格式

输出一行，包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，以空格分隔。第 $i$ 个数字 $a_i$ 表示大学 $i$ 优于的大学数量。

样例

样例输入 1

4 2
1 2 3 4
1 3 2 4

样例输出 1

3 2 2 0

样例输入 2

4 2
1 2 3 4
4 3 2 1

样例输出 2

3 3 3 3

样例输入 3

5 2
5 4 3 2 1
5 4 3 2 1

样例输出 3

0 1 2 3 4