Creating new tasks for every programming competition is very difficult. It is especially hard to create tasks for competitions that have participants from different countries, because the tasks need to be of very high quality.

Therefore, organizers usually prepare multiple tasks, and the chairman of the event decides which tasks will be used during the actual competition. Vesna has written the problem statements for N tasks, but she knows that the chairman will only select one of her tasks for the event. Therefore, she has prepared test cases and solutions for only one of her tasks (her favorite one), and she wants to make sure that the chairman will choose that one.

The chairman will be looking at the tasks one by one. For each task after the first one, he will compare the best task so far with the new task that he is currently looking at, and will choose the one that he prefers more. For each two tasks, Vesna knows which one the chairman will prefer. However, have in mind that the chairman doesn’t compare tasks by any objective measure (and instead uses his past experience and instinct), so it’s possible that out of tasks A and B he prefers task A, out of B and C he prefers task B, but out of A and C he prefers task C.

Help Vesna to convince the chairman to select her favorite task. She can send the chairman the tasks in whichever order she wants, and the chairman will always look at them in that order (from first task to last).

Input

The first line contains one integer number N (1 <= N <= 100), the number of tasks.

Each of the next N lines contains N integers (0 or 1), describing which tasks the chairman prefers. So, if the j-th number in the i-th row is equal to 1, then the chairman prefers the i-th task to the j-th task. (The j-th number in the i-th row will always be different from the i-th number in the j-th row. The numbers in the main diagonal (i-th number in i-th row) will always be equal to 0).

The next line contains a positive integer number X (1 <= X <= N), which is Vesna’s favorite task.

Output

In one line, print the order in which Vesna should send the tasks to the chairman (as a list, separated by single space). Each task should appear exactly once in the list. If there are multiple solutions available, find and print the lexicographically smallest one. If there is no solution, print -1.

(An array or list X is lexicographically smaller than Y if there exists an index i such that Xi < Yi, and Xj = Yj for all smaller indexes 1 ≤ j < i.)

Constraints

Time limit: 500 milliseconds
Memory limit: 256 megabytes

Examples

input
4
0 0 1 1
1 0 0 0
0 1 0 0
0 1 1 0
3

output
1 4 2 3

Subtasks
 1) In test cases worth 10 points, transitivity will apply – i.e. for each three tasks A, B and C, for which the chairman prefers A to B and B to C, he also prefers A to C.
 2) In other test cases worth 9 points, (1 <= N <= 10)
 3) In other test cases worth 12 points, (1 <= N <= 20)
 4) To earn all 100 points, your solution must work for the input constraints presented in the “Input” section.