Description

现在是 4202 年，Lutece 已经成为了测评系统的事实标准，因为它拥有由 $n$ 台服务器组成的超大计算集群，使用基于任务流和符号执行构建的可扩展测评范式，并提供置信度极高的时间和空间测量值。更重要的是，使用它是免费的。

你现在已经成为了 Lutece 开发组的运维工程师，现在你要实现你的第一个需求：监控测评集群某一时段的题目提交状态。Lutece 上共有 $t$ 道题，题目从 $1$ 到 $t$ 进行编号。测评每道题的一个提交所花的时间均为 $1$ 分钟。由于 Lutece 已经成为了测评系统的事实标准，所以测评量很大，接下来 $m$ 分钟内，每台测评机每分钟都会按测评队列中的顺序，测评针对一道题的提交。

现在给定每台测评机 $m$ 分钟内的测评队列，你需要计算对于每道题，同时测评这道题的测评机数的最小值和最大值。

Input

第一行三个整数 $n,m,t$ ($1\le n,m,t\le 5\times 10^5,n\times m\le 5\times 10^5$)，意义如题目描述。

接下来 $n$ 行，每行 $m$ 个正整数 $s_{i,j}$ ($1\le s_{i,j}\le t$)，表示测评机 $i$ 会在第 $j$ 分钟测评对 $s_{i,j}$ 题目的提交。

Output

输出 $t$ 行，第 $i$ 行输出两个整数，表示同时测评题目 $i$ 的测评机数的最小值和最大值。

Samples

3 2 3
1 2
2 3
2 3

0 1
1 2
0 2

3 4 3
2 3 2 2
2 3 3 2
2 2 3 2

0 0
1 3
0 2

Resources

The 22nd UESTC Programming Contest Preliminary