现在是晚上九点，小王即将为群友们献歌一首。

群里总共有 $n$ 位群友，小王也准备了 $n+1$ 首歌。但群友们还没决定好让小王唱哪首。

于是群友准备按照以下规则选取小王最终唱的歌：

1. 首先从 $1$ 到 $n$ 中选取一个数 $p$ ，表示最先决策的人。初始时， $n+1$ 首歌都在候选歌单中。
2. 所有人按照 $p,p+1,p+2,\dots,n-1,n,1,2,\dots,p-2,p-1$ 的顺序轮流决策。
   • 在一次决策中，决策者必须从候选歌单中恰好选出一首移除候选歌单。
3. 显然在所有人都决策完后，候选歌单中只会剩下一首歌，那便是小王最终给群友唱的歌。

$n$ 位群友中的每个人对这 $n+1$ 首歌的看法不一定相同，第 $i$ 个人对第 $j$ 首歌的评价值为 $a_{i,j}$ 。每个人都希望听到小王唱他的评价值尽可能高的歌。

保证对于所有 $i$ ， $a_{i,1},a_{i,2},\dots,a_{i,n},a_{i,n+1}$ 构成一个 $1$ 到 $n+1$ 的排列。

所有群友都绝顶聪明，均会按照最优策略决策。

现在你想知道，对于 $p=1,2,3,\dots,n$ ，最终小王会唱哪首歌？

输入格式

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

若 $seed=0$ ，则接下来 $n$ 行中每行 $n+1$ 个用空格分隔的整数。其中第 $i$ 行的第 $j$ 个整数表示 $a_{i,j}$ 。

否则不需要后续任何输入，可使用以下代码，调用 gen(n,seed) 来生成 $a$ ：

#include<bits/stdc++.h>
const int MAXN=5010;
int a[MAXN][MAXN];
void gen(int n,int seed){
    std::mt19937 rnd(seed);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n+1;++j){
            a[i][j]=j;
            std::swap(a[i][j],a[i][rnd()%j+1]);
        }
    }
}

输出格式

一行 $n$ 个整数，用空格分隔。其中第 $i$ 个表示当 $p=i$ 时小王所唱的歌。

样例数据

样例 1 输入

2 0
1 2 3
1 3 2

样例 1 输出

3 2

样例 1 解释

我们以 $p=1$ 为例。

初始时候选歌单为 $\{1,2,3\}$

首先 $1$ 号群友将 $2$ 移出候选歌单，候选歌单变为 $\{1,3\}$ 。

接着 $2$ 号群友将 $1$ 移出候选歌单，候选歌单变为 $\{3\}$ 。

最终，小王将唱第 $3$ 首歌。

子任务

对于所有数据，满足 $1\leq n\leq 5000,0\leq seed\leq 10^9$ 。

保证对于所有 $n>2000$ 的数据，$seed\neq 0$ 。