It is 9:00 PM, and Xiao Wang is about to sing a song for his group members.

There are $n$ group members in total, and Xiao Wang has prepared $n+1$ songs. However, the group members have not yet decided which song Xiao Wang should sing.

The group members have decided to select the final song according to the following rules:

1. First, a number $p$ is chosen from $1$ to $n$, representing the person who makes the first decision. Initially, all $n+1$ songs are in the candidate list.
2. Everyone takes turns making decisions in the order $p, p+1, p+2, \dots, n-1, n, 1, 2, \dots, p-2, p-1$.
   • In each decision, the decision-maker must choose exactly one song from the candidate list and remove it.
3. Obviously, after everyone has made their decision, only one song will remain in the candidate list, which is the song Xiao Wang will finally sing for the group members.

Each of the $n$ group members has different opinions on these $n+1$ songs. The value of the $j$-th song to the $i$-th person is $a_{i,j}$. Everyone wants to hear Xiao Wang sing the song that they value as highly as possible.

It is guaranteed that for all $i$, $a_{i,1}, a_{i,2}, \dots, a_{i,n}, a_{i,n+1}$ form a permutation of $1$ to $n+1$.

All group members are perfectly rational and will follow the optimal strategy.

Now, you want to know which song Xiao Wang will sing for each $p = 1, 2, 3, \dots, n$.

Input

The first line contains two integers $n$ and $seed$.

If $seed = 0$, the next $n$ lines each contain $n+1$ space-separated integers. The $j$-th integer in the $i$-th line represents $a_{i,j}$.

Otherwise, no further input is required. You can use the following code to call gen(n, seed) to generate $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]);
        }
    }
}

Output

Output $n$ space-separated integers on a single line. The $i$-th integer represents the song Xiao Wang will sing when $p = i$.

Examples

Input 1

2 0
1 2 3
1 3 2

Output 1

3 2

Note

Let's take $p=1$ as an example.

Initially, the candidate list is $\{1, 2, 3\}$.

First, group member $1$ removes song $2$ from the candidate list; the candidate list becomes $\{1, 3\}$.

Next, group member $2$ removes song $1$ from the candidate list; the candidate list becomes $\{3\}$.

Finally, Xiao Wang will sing the $3$-rd song.

Subtasks

For all data, $1 \leq n \leq 5000$ and $0 \leq seed \leq 10^9$.

It is guaranteed that for all data where $n > 2000$, $seed \neq 0$.