题目描述

给定一个 $n\times n$ 的矩阵，每个位置有一个权值 $a_{i,j}$ 。当你位于 $(x,y)$ 时，可以走到 $(x-1,y+1),(x,y+1),(x+1,y+1)$ 中的任意一个。

现在你需要求出一条路径，满足从第一列走到最后一列，且经过的点权值和恰好为 $t$ 。具体的，你需要求出一个序列 $p_i$ 满足：

• $p$ 长度为 $n$
• $\forall 1\le i\le n,1\le p_i\le n$
• $\forall 1\le i\le n,|p_i-p_{i-1}|\le 1$
• $\sum_{i=1}^n a_{p_i,i}=t$

同时你求出的 $p$ 还需满足字典序最小。

输入格式

第一行两个整数 $n,t$ 。

下面 $n$ 行每行 $n$ 个整数 ，第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$ 。

输出格式

无解输出一行一个整数 $-1$ 。

否则，输出一行 $n$ 个整数，表示字典序最小的 $p_i$ 。

样例 #1

样例输入 #1

3 3
1 2 2
2 1 2
2 1 1

样例输出 #1

1 2 3

样例输入 #2

5 29
3 10 2 1 5
9 7 2 10 1
1 6 10 8 0
9 4 4 1 8
1 0 5 3 1

样例输出 #2

1 2 3 3 2

说明/提示

对于所有测试点，满足 $2\le n\le 200,1\le a_{i,j} \le 1000,1\le t \le 80000$ 。