Bajtazar 是位化学家。正如你可能记得的那样，多年前他因制造出物质 X 而闻名。由于该物质并没有解决人类的所有问题，这一次他不再试图制造它或任何其他特定的溶液，而只是进行实验并评估结果。

在 Bajtazar 的实验室里有 $n$ 个试管，编号从 $1$ 到 $n$，通过 $m$ 根管道连接，物质可以通过这些管道流动。所有试管的高度各不相同。每根管道中的液体只能向下流动。每根管道有两个端点——第 $i$ 根管道的一端连接到编号为 $a_i$ 的试管，另一端连接到编号为 $b_i$ 的试管，已知试管 $a_i$ 的位置高于试管 $b_i$。此外，每根管道都配有一个特殊的夹子，用于阻断物质的流动。Bajtazar 可以随时选择任意一个夹子并将其打开，允许物质从试管 $a_i$ 自由流向试管 $b_i$，并在物质从一个试管完全流向另一个试管后再次将其夹紧。由于这些是机械夹子，且保持打开状态需要消耗体力，因此在任何时刻只能打开一个夹子。

编号为 $1$ 到 $k$ 的试管中含有危险化学品。这些试管中的每一支都含有不同的物质。编号大于 $k$ 的试管最初是空的。

这些化学品极其危险，在任何情况下都不得让不同的物质混合——这种混合的后果可能是灾难性的。由于流动的物质会留下微小的沉积物，甚至不允许将物质倒入曾经含有任何其他物质的试管中。

Bajtazar 唯一能做的就是将物质在试管之间移动，同时确保没有任何两种物质混合。这并非毫无意义——通过安全地运输物质，他可以将它们移动到更方便研究其特性的试管中。

现在，化学家想要选择一个区间 $[\ell, r]$，其中满足 $k + 1 \le \ell \le r \le n$，将尽可能多的液体转移到该区间内的任意试管中，并研究这些放置方便的化学品。由于他无法决定哪个区间对他最方便，他想知道对于每个可能的区间 $[\ell, r]$，他最多能将多少种不同的液体运输到编号在 $[\ell, r]$ 范围内的试管中。我们将此值记为 $f(\ell, r)$。

请帮助 Bajtazar 编写一个程序，根据他实验室的描述，计算对于区间 $[0, k]$ 中的每个 $x$，有多少个区间 $[\ell, r]$ 满足 $f(\ell, r) = x$。

输入格式

输入的第一行包含三个整数 $n, m$ 和 $k$ ($2 \le n \le 10^5$; $1 \le m \le 10^6$; $1 \le k \le 50; k < n$)，分别表示试管的数量、连接它们的管道数量以及最初含有 Bajtazar 研究的物质的试管数量。

接下来的 $m$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le n; k + 1 \le b_i \le n$)，表示存在一根管道，液体可以通过它直接从试管 $a_i$ 流向试管 $b_i$。

保证实验室的描述是正确的。也就是说，不存在数字 $p \ge 2$ 和试管序列 $v_1, v_2, v_3, \dots, v_p$，使得 $v_1 = v_p$，且对于每个 $i \in [1, p-1]$，都存在一根液体可以从试管 $v_i$ 流向 $v_{i+1}$ 的管道。换句话说，如果我们把试管看作图的顶点，把管道看作有向边，那么输入描述了一个有向无环图。

请注意，输入中没有给出试管的高度。然而，对于每一对直接由管道连接的试管，已知哪一个试管位置更高。

输出格式

输出应包含 $k + 1$ 行。第 $i$ 行应包含一个整数，表示满足 $k + 1 \le \ell \le r \le n$ 且 $f(\ell, r) = i - 1$ 的区间 $[\ell, r]$ 的数量。

所有测试用例的时间限制为 10 秒。

样例

输入 1

9 10 2
1 3
1 5
2 5
5 4
5 6
2 6
2 9
2 8
1 5
1 9

输出 1

1
9
18

说明 1

由于没有任何管道通向第七个试管，因此 $f(7, 7) = 0$。

Bajtazar 只能将一种物质运输到试管区间 $[3, 3], [4, 4], [5, 5], [6, 6], [8, 8], [9, 9], [4, 5], [6, 7]$ 和 $[7, 8]$ 中的每一个。因此 $f(3, 3) = f(4, 4) = f(5, 5) = f(6, 6) = f(8, 8) = f(9, 9) = f(4, 5) = f(6, 7) = f(7, 8) = 1$。对于区间 $[3, 3]$，这必须是来自第一个试管的物质（当然它会最终位于第三个试管中），而对于区间 $[7, 8]$ 和 $[8, 8]$，这必须是来自第二个试管的物质。

请注意，如果我们想将两种物质都转移到区间 $[4, 5]$，即第四和第五个试管，那么倒入第四个试管的物质在途中必须经过第五个试管并留下沉积物，这使得无法将第二种物质转移到其中。

对于其余的每个区间，Bajtazar 都能转移两种物质。