3160: 机器人的花园

花园里有 $n$ 颗植株，编号从 $1$ 到 $n$ ，他们围成一圈。你控制机器人顺时针（第 $n$ 个植株采摘后回到 $1$）采摘植株（一个植株可以重复采摘），当你在 $t$ 时刻采摘到第 $i$ 个植株时，可以产生 $W_{i,t}$ 的价值（价值也可能为负)。每次采摘花费 $1$ 个单位时间，在植株之间移动不花费时间。机器人的电池只能支撑机器人采摘 $d$ 个单位时间，同时，$T$ 表示允许采摘的最大时间，从 $T+1$ 时刻开始则不允许再采摘，你可以提前停止采摘，你也可以不采摘。

分别输出从 $i$ 时刻（$1\le i \le T$）开始出发的情况下，你可以选择从任意一颗植株开始出发，请求出能过获得的最大价值。

第一行为三个整数n、 T、 d。$1\le n,T\le 10^6,1\le n*T\le10^6,1\le d\le10^6$。

接下来 $T$ 行。

每行 $n$ 个数字，第 i 个数字表示在 t 时刻 (输入的 t+1 行)采摘第 $i$ 个植株的价值 $W_{i,t}$ 。

输出共一行，$T$ 个数，第 $t$ 个数表示从第 $t$ 个时刻开始出发，能够获取的最大价值。

3 5 2
0 -4 1
3 -4 0
1 -2 4
-4 -4 1
2 5 5

4 3 4 3 5