题目背景

译自 NOISG 2018 Finals B. Journey。

题目描述

Kuno 要从 A 市到 B 市旅行，但在路途中他可能会停下来休息。

允许他停留的共有 $N$ 个城市，编号为 $0$ 到 $N-1$，其中 $0$ 号城市表示 A 市，$N-1$ 号城市表示 B 市，编号越大的城市距离 B 市越近。

为了让旅行保持一定的效率，中途停留需要满足以下限制：

• 第 $i$ 次停留的城市必须比第 $i-1$ 次离 B 市严格更近。特别地，我们认为第 $0$ 次停留的城市是 A 市。
• 从 A 市出发，直到从 B 市结束停留离开，整个过程不能超过 $M$ 天。换句话说，我们不允许你在 A 市停留，但允许你在 B 市停留。

Kuno 在城市之间的移动和停留基于城市之间的航线和城市中的酒店系统。每个城市 $i$ 都存在 $H$ 条用 $(j,k)$ 表示的航线，表示你可以通过这条航线从城市 $i$ 前往城市 $j$，但是一旦使用这条航线，就必须在城市 $j$ 中停留不少于 $k$ 天。特别地，每个城市都有一条直接前往 B 市的航线。

注意可能存在完全相同或起点终点相同的航线，此时你需要把它们视为不同航线。你应当忽略远离 B 市的航线。

在飞机中度过的时间忽略不计。

到达一个城市即算作在该城市停留，即使停留了 $0$ 天。

你的任务是，对每一个 $d\in[1,m]$，帮助 Kuno 计数他从 A 市出发到从 B 市结束停留返回花费 $d$ 天的方案数。特别地，若方案数超过 $5\times 10^8$，你只需输出 $5\times 10^8+1$。

两个旅行方案不同当且仅当以下三条任意一条成立：

1. 一个旅行方案中需要在城市 $i$ 停留，而另一个不用。
2. 存在一个城市 $i$，使得两个旅行方案离开该城市的时间不同。特别地，也包括从 B 市离开的时间不同。
3. 两个行程都从城市 $i$ 到城市 $j$，但使用的航线不同。

例如，对于两个均为 A 市到 C 市，再从 C 市到 D 市，最后从 D 市到 B 市的旅行方案，如果一个是在第二天离开 C 市，另一个是在第三天离开 C 市，那么它们就是不同的方案。此外，如果输入中存在两条同样从 D 市前往 B 市的航线，即便出发时间和到达时间相同，也是不同的方案。

如你仍无法完全理解题意，请阅读样例解释。

输入格式

第一行包含三个整数 $N,M,H$，表示城市数量，旅行天数上限，和每个城市的航线数量。

接下来的输入包含 $N-1$ 行，第 $i$ 行包含 $2H$ 个用空格分割的整数，每两个为一组 $(j,k)$，描述从城市 $i-1$ 出发的 $H$ 条航线。

输出格式

输出 $m$ 个用空格隔开的整数，依次表示从 A 市出发直至从 B 市结束停留离开共花费恰好 $1,2,3,\cdots ,m$ 天的旅行方案数。注意如果方案数超过 $5\times 10^8$，则应输出 $5\times 10^8+1$。

4 4 3
1 2 2 2 3 0
2 2 2 3 3 0
3 1 3 3 3 0

1 1 3 6

4 8 3
1 0 2 1 3 0
3 1 3 2 3 0
3 1 3 1 3 0

2 5 11 17 23 29 35 41

4 11 3
1 0 2 0 3 0
0 0 2 0 3 0
0 0 0 0 3 0

4 8 13 19 26 34 43 53 64 76 89

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

960800 6702725 26746084 80092734 199948848 439388874 500000001 500000001

提示

样例 #1 解释

样例 #1 输入描述了一个具有 $4$ 座城市，每个城市有 $3$ 条不同的航线出发的情况：

出发城市	航线 $1$ 终点	$\text{Min.}$	航线 $2$ 终点	$\text{Min.}$	航线 $3$ 终点	$\text{Min.}$
A 市	城市 $1$	$2$ 天	城市 $2$	$2$ 天	B 市	$0$ 天
城市 $1$	城市 $2$			$3$ 天
城市 $2$	B 市	$1$ 天	B 市

为了方便表格描述，我们用 $\text{Min.}$ 表示了每条航线对目的地最少停留天数的要求。

所有 $1$ 天的旅行方案如下；

旅行方案	方案
$1$	在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。

所有 $2$ 天的旅行方案如下：

旅行方案	方案
$1$	在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $1$ 天。

所有 $3$ 天的旅行方案如下：

旅行方案	方案
$1$	在第 $1$ 天从 A 市通过航线 $1$ 抵达城市 $1$，在城市 $1$ 停留 $2$ 天；在第 $3$ 天从城市 $1$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。
$2$	在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $2$ 天；在第 $3$ 天从城市 $2$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。
$3$	在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $2$ 天。

所有 $4$ 天的旅行方案如下：

旅行方案	方案
$1$	在第 $1$ 天从 A 市通过航线 $1$ 抵达城市 $1$，在城市 $1$ 停留 $2$ 天；在第 $3$ 天从城市 $1$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $1$ 天。
$2$	在第 $1$ 天从 A 市通过航线 $1$ 抵达城市 $1$，在城市 $1$ 停留 $3$ 天；在第 $4$ 天从城市 $1$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。
$3$	在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $2$ 天；在第 $3$ 天从城市 $2$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $1$ 天。
$4$	在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $3$ 天；在第 $4$ 天从城市 $2$ 通过航线 $3$ 抵达 B 市，在 B 市停留 $0$ 天。
$5$	在第 $1$ 天从 A 市通过航线 $2$ 抵达城市 $2$，在城市 $2$ 停留 $2$ 天；在第 $3$ 天从城市 $2$ 通过航线 $1$ 抵达 B 市，在 B 市停留 $1$ 天。
$6$	在第 $1$ 天从 A 市通过航线 $3$ 抵达 B 市，在 B 市停留 $3$ 天。

样例 #2 解释

这组样例中除 A 市外所有城市的出发航线均直接到达 B 市。它满足子任务 $1,3,4$。

样例 #3 解释

这组样例中所有的航线均不限制目的地最少停留天数。它满足子任务 $2,3,4$。

样例 #4 解释

注意若方案数超过 $5\times 10^8$，你只需输出 $5\times 10^8+1$。它满足子任务 $2,3,4$。

子任务

对于 $100\%$ 的数据，$N\le 10^4,M\le 400,H\le 100$，其余输入均在此范围下合法。

子任务	得分	数据范围及特殊性质
$1$	$20$	除 A 市外所有城市的出发航线均直接到达 B 市，$N,M,H\le 10$
$2$	$23$	所有的航线均不限制目的地最少停留天数，$N,M,H\le 20$
$3$	$26$	$N,M,H\le 100$
$4$	$31$	无特殊限制