Kuno Kunibertson 正在从安曼（Amman）搬家到巴西利亚（Brasília）。他的新雇主支付旅费并允许他进行任意次数的经停；仅有的两个条件是：（1）行程中第 $i$ 个经停城市距离巴西利亚的距离应比第 $(i-1)$ 个经停城市更近；（2）行程总耗时不得超过 $m$ 个夜晚。此外，由于巴西利亚是一个交通枢纽，每个城市都有直飞巴西利亚的航班。Kuno Kunibertson 必须向旅行评估机构提供以下信息：
- 三个整数 $n, m, h$，其中 $n$ 是行程中可能访问的城市数量，$m$ 是行程总耗时的上限，$h$ 是每个经停城市后续航班的数量（为了方便记号，城市编号为 $0, 1, \dots, n-1$，其中 $0$ 是安曼，$n-1$ 是巴西利亚）。
- 对于每个经停城市，提供恰好 $h$ 个可能的后续航班列表，每个航班由下一个城市以及在下一个城市的最少住宿晚数指定。只有那些前往距离巴西利亚更近的城市的航班才是相关的，其他航班应被程序忽略。
旅行评估机构随后将利用某种人工智能程序为他规划合适的行程，该程序根据旅游景点的数据库优化行程。然而，为了不使其计算机过载，旅行评估机构有以下要求：
（*）使用 $k$ 个夜晚（$k < m$）的行程数量不应超过 $500000000$（即 $5 \times 10^8$）。
注意，在计数时，如果满足以下任一条件，则认为两个行程是不同的：
- 一个行程包含在城市 $i$ 的经停，而另一个不包含；
- 从城市 $i$ 出发的日期在两个行程中不同；
- 两个行程都从城市 $i$ 前往城市 $j$，但使用了不同的航班（如果 Kuno Kunibertson 在数据中列出了从城市 $i$ 到城市 $j$ 的两个或多个航班，则会出现这种情况）。
例如，如果行程是安曼 - 开罗 - 达喀尔 - 巴西利亚，那么在第 2 天从开罗出发的行程与在第 3 天从开罗出发的行程不同。此外，如果有两个从达喀尔到巴西利亚的航班（即使它们在同一天出发和到达），由于它们使用了不同的航班，这些行程也是不同的。
由于违反条件（*）会受到处罚，Kuno Kunibertson 请他的朋友 Herbert Hercules 为他编写一个计算机程序，计算使用最多 $k$ 天的行程数量。
输入格式
程序必须从标准输入读取数据。
输入的第一行包含三个整数 $n, m$ 和 $h$，其中 $n$ 是城市数量，$m$ 是所用夜晚数的严格上限，$h$ 是每个城市的后续航班数量。我们假设城市 $0$ 是安曼，城市 $n-1$ 是巴西利亚。我们还假设如果 $i > j$，则城市 $i$ 比城市 $j$ 更靠近巴西利亚。
然后，输入包含 $n-1$ 行，其中第 $i$ 行（$i = 0, 1, \dots, n-2$）包含 $h$ 对整数 $(j, k)$，这意味着 Kuno Kunibertson 可以从城市 $i$ 飞往城市 $j$ 并至少停留 $k$ 个夜晚。如果前往同一个城市有多个航班，它们被视为不同的航班。所有 $2h$ 个整数在一行中以空格分隔。
输出格式
程序必须仅输出到标准输出。
输出是一个包含 $m$ 个整数的列表，这些整数在 $0$ 到 $500000001$ 之间，分别是从安曼到巴西利亚耗时 $0, 1, \dots, m-1$ 个夜晚的行程数量。如果行程数量为 $500000001$ 或更多，则输出应为 $500000001$。
子任务
共有四个子任务；每个子任务将在多个实例上进行测试，每个实例的最大执行时间为 1.0 秒。子任务及其分值如下：
| 子任务 | 分值 | 条件 |
|---|---|---|
| 1 | 20 | 最多一次经停，$n, m, h \le 10$ |
| 2 | 23 | 无最少停留要求，$n, m, h \le 20$ |
| 3 | 26 | $n, m, h \le 100$ |
| 4 | 31 | $n \le 10000, m \le 400, h \le 100$ |
“最多一次经停”意味着所有从经停点出发的航班都直接飞往巴西利亚。“无最少停留要求”意味着每次经停的停留时间可以是任意数字（包括 $0$），并且 Kuno Kunibert 在抵达巴西利亚后即可报告工作。
样例
样例输入 1
4 8 3 1 0 2 1 3 0 3 1 3 2 3 0 3 1 3 1 3 0
样例输出 1
2 5 11 17 23 29 35 41
样例输入 2
4 11 3 1 0 2 0 3 0 0 0 2 0 3 0 0 0 0 0 3 0
样例输出 2
4 8 13 19 26 34 43 53 64 76 89
样例输入 3
8 8 8 1 0 1 0 1 0 1 0 1 0 1 0 1 0 7 0 2 0 2 0 2 0 2 0 2 0 2 0 2 0 7 0 3 0 3 0 3 0 3 0 3 0 3 0 3 0 7 0 4 0 4 0 4 0 4 0 4 0 4 0 4 0 7 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 7 0 6 0 6 0 6 0 6 0 6 0 6 0 6 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0 7 0
样例输出 3
960800 6702725 26746084 80092734 199948848 439388874 500000001 500000001
说明
样例 3 的输出中插入了人工换行符以避免行过长。这些换行符仅用于显示目的，输出中不需要。