在 Bajtocja 有 $n$ 个城市和 $m$ 条连接这些城市的双向道路。通过一条连接两个城市的道路需要一天。城市编号为 $1$ 到 $n$。骑士位于 $1$ 号城市，想要在最多 $d$ 天内到达 $n$ 号城市，并在那里击败一只强大的野兽。

为了击败野兽，骑士将使用 $k$ 把剑，每把剑的类型各不相同。剑的类型编号为 $1$ 到 $k$。每把剑都有一个非负整数值。起初，骑士拥有 $1$ 到 $k$ 类型的每种剑各一把，且他拥有的每把剑的值均为 $0$。

每条道路上都有 $k$ 名精通剑术的工匠。对于第 $i$ 条道路，第 $j$ 名工匠可以将 $j$ 类型剑的值变为 $a_{i,j}$。骑士在经过某条道路时，可以使用任意工匠子集的服务，从而修改他选择的任意剑的子集。每种类型的剑都可以被修改任意多次。

骑士希望 $1$ 类型剑的值尽可能大；在最大化 $1$ 类型剑值的前提下，他希望 $2$ 类型剑的值尽可能大，以此类推，直到 $k$ 类型剑。修改不同类型剑的顺序并不重要，他只关心剑的最终值。

已知通过道路网可以在最多 $d$ 天内从 $1$ 号城市到达 $n$ 号城市。骑士可以多次经过同一个城市或同一条道路。如果骑士最优地规划他的路径，他最终会使用什么样的剑？

输入格式

输入的第一行包含四个整数 $n, m, d$ 和 $k$ ($2 \le n \le 10\,000, 1 \le m, d \le 10\,000, 1 \le k \le 10$)，分别表示 Bajtocja 的城市数量、道路数量、最大天数以及剑的类型数量。接下来的 $m$ 行，每行描述一条道路，包含 $k+2$ 个整数 $u_i, v_i, a_{i,1}, \dots, a_{i,k}$。$u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$) 表示第 $i$ 条道路连接的城市编号。$a_{i,j}$ ($0 \le a_{i,j} \le 10^9$) 表示在选择第 $i$ 条道路上的工匠修改后，$j$ 类型剑的新值。可能存在多条连接相同城市的边。

输出格式

输出一行，包含 $k$ 个非负整数 $w_1, \dots, w_k$，用空格分隔。$w_1$ 表示骑士在最多 $d$ 天内到达 $n$ 号城市所能获得的 $1$ 类型剑的最大值。$w_2$ 表示在获得 $1$ 类型剑值为 $w_1$ 的前提下，骑士在最多 $d$ 天内到达 $n$ 号城市所能获得的 $2$ 类型剑的最大值，以此类推。换句话说，序列 $(w_1, \dots, w_k)$ 必须是所有骑士能在最多 $d$ 天内到达 $n$ 号城市并获得剑值序列中字典序最大的一个。

样例

输入 1

7 7 6 2
1 2 7 9
2 7 1 0
1 3 5 6
3 4 10 1
4 7 0 0
5 6 2 17
5 7 3 15

输出 1

10 15

说明

样例解释：最佳路径已在图中用粗线和箭头标出，箭头方向表示骑士的行进方向。带下划线的粗体边标签表示在该道路上进行的修改。

从 $3$ 号城市到 $4$ 号城市的道路使得获得 $1$ 类型剑的最大值成为可能。无法在最多 $6$ 天内到达 $7$ 号城市并同时经过连接 $3$ 和 $4$ 的道路以及连接 $5$ 和 $6$ 的道路。因此，骑士必须满足于 $2$ 类型剑的值为 $15$，通过连接 $5$ 和 $7$ 的道路。他的路径将经过以下城市：$1, 3, 4, 7, 5, 7$。他还会剩下一天时间，该时间不会被使用。

子任务