Problem: Lenny had an n × m matrix of positive integers. He loved the matrix so much, because each row of the matrix was sorted in non-decreasing order. For the same reason he calls such matrices of integers lovely.

One day when Lenny was at school his little brother was playing with Lenny's matrix in his room. He erased some of the entries of the matrix and changed the order of some of its columns. When Lenny got back home he was very upset. Now Lenny wants to recover his matrix.

Help him to find an order for the columns of the matrix so that it's possible to fill in the erased entries of the matrix to achieve a lovely matrix again. Note, that you can fill the erased entries of the matrix with any integers.

Input

The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 105). Each of the next n lines contains m space-separated integers representing the matrix. An integer -1 shows an erased entry of the matrix. All other integers (each of them is between 0 and 109 inclusive) represent filled entries.

Output

If there exists no possible reordering of the columns print -1. Otherwise the output should contain m integers p1, p2, ..., pm showing the sought permutation of columns. So, the first column of the lovely matrix will be p1-th column of the initial matrix, the second column of the lovely matrix will be p2-th column of the initial matrix and so on.

Examples

Input

3 3
1 -1 -1
1 2 1
2 -1 1


Output

3 1 2 


Input

2 3
1 2 2
2 5 4


Output

1 3 2 


Input

2 3
1 2 3
3 2 1


Output

-1

Solution (in JAVA):

Solution:
/* Codeforces Template */

import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.fill;
import static java.util.Arrays.binarySearch;
import static java.util.Arrays.sort;

public class Main {
	
	static long initTime;
	static final Random rnd = new Random(7777L);
	static boolean writeLog = false;
	
	public static void main(String[] args) throws IOException {
		initTime = System.currentTimeMillis();
		try {
			writeLog = "true".equals(System.getProperty("LOCAL_RUN_7777"));
		} catch (SecurityException e) {}
		new Thread(null, new Runnable() {
			public void run() {
				try {
					try {
						if (new File("input.txt").exists())
							System.setIn(new FileInputStream("input.txt"));
					} catch (SecurityException e) {}
					long prevTime = System.currentTimeMillis();
					new Main().run();
					log("Total time: " + (System.currentTimeMillis() - prevTime) + " ms");
					log("Memory status: " + memoryStatus());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}, "1", 1L << 24).start(); 
	}

	void run() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		solve();
		out.close();
		in.close();
	}
	
	/*************************************************************** 
	 * Solution
	 **************************************************************/

	final int MAXV = 3 * 100 * 1000;
	final int MAXE = 10 * 100 * 1000;
	
	int rowNum;
	int colNum;
	int[][] translatedMatrix;
	
	Item[] columns;
	Item[] columnsOrderedByIds;
	
	int vNum;
	Graph graph;
	
	void solve() throws IOException  {
		
		// Input
		
		rowNum = nextInt();
		colNum = nextInt();
		translatedMatrix = new int [colNum][rowNum];
		
		for (int rowIdx = 0; rowIdx < rowNum; rowIdx++) {
			for (int colIdx = 0; colIdx < colNum; colIdx++) {
				translatedMatrix[colIdx][rowIdx] = nextInt();
			}
		}
		
		columns = new Item [colNum];
		columnsOrderedByIds = new Item [colNum];
		
		for (int colIdx = 0; colIdx < colNum; colIdx++) {
			columnsOrderedByIds[colIdx] = columns[colIdx] = new Item(colIdx, translatedMatrix[colIdx]);
		}
		
		
		// Build graph
		
		vNum = colNum;
		graph = new Graph(MAXV, MAXE);

		int[] groupFirstIdx = new int [colNum];
		int[] groupLastIdx = new int [colNum];
		
		for (int rowIdx = 0; rowIdx < rowNum; rowIdx++) {
			
			sort(columns, new RowComparator(rowIdx));
			
			int groupsNum = 0;
			
			int leftIdx = 0;
			
			while (leftIdx < colNum) {
				
				int rightIdx = leftIdx;
				
				while (rightIdx + 1 < colNum && columns[leftIdx].values[rowIdx] == columns[rightIdx + 1].values[rowIdx]) {
					rightIdx++;
				}
				
				groupFirstIdx[groupsNum] = leftIdx;
				groupLastIdx[groupsNum] = rightIdx;
				groupsNum++;
				
				leftIdx = rightIdx + 1;
			}
			
			for (int lowerGroupIdx = (columns[0].values[rowIdx] == -1 ? 1 : 0); lowerGroupIdx + 1 < groupsNum; lowerGroupIdx++) {
				int higherGroupIdx = lowerGroupIdx + 1;
				
				for (int colIdx = groupFirstIdx[lowerGroupIdx]; colIdx <= groupLastIdx[lowerGroupIdx]; colIdx++) {
					graph.addEdge(vNum, columns[colIdx].id);
				}
				
				for (int colIdx = groupFirstIdx[higherGroupIdx]; colIdx <= groupLastIdx[higherGroupIdx]; colIdx++) {
					graph.addEdge(columns[colIdx].id, vNum);
				}
				
				vNum++;
			}
			
		}
		
		
		// Find cycle
		
		if (findCycle()) {
			out.println(-1);
			return;
		}
		
		
		// Topsort
		
		topsort();
		
		
		// Output
		
		List<Integer> answer = new ArrayList<Integer>(colNum);
		
		for (int idx = 0; idx < vNum; idx++) {
			
			int v = order[idx];
			
			if (v < colNum) {
				answer.add(v + 1);
			}
			
		}
		
		printCollection(answer);
		
	}
	
	
	
	// Find cycle
	
	final int WHITE = 0;
	final int GREY = 1;
	final int BLACK = 2;
	
	int[] color;
	
	boolean findCycle() {
		
		color = new int [vNum]; // filled with 'WHITE'
		
		for (int v = 0; v < vNum; v++) {
			if (color[v] == WHITE) {
				if (findCycle(v)) {
					return true;
				}
			}
		}
		
		return false;
	}

	boolean findCycle(int v) {
		
		color[v] = GREY;
		
		for (int idx = graph.head[v]; idx != 0; idx = graph.next[idx]) {
			
			int nv = graph.vert[idx];
			
			if (color[nv] == WHITE) {
				if (findCycle(nv)) {
					return true;
				}
			}
			
			if (color[nv] == GREY) {
				return true;
			}
			
		}
		
		color[v] = BLACK;
		
		return false;
	}

	
	
	// Topsort
	
	boolean[] used;
	int[] order;
	int orderedIdx = 0;
	
	void topsort() {
		used = new boolean [vNum];
		order = new int [vNum];
		
		for (int v = 0; v < vNum; v++) {
			if (!used[v]) {
				topsortDFS(v);
			}
		}
		
	}
	
	void topsortDFS(int v) {
		used[v] = true;

		for (int idx = graph.head[v]; idx != 0; idx = graph.next[idx]) {
			
			int nv = graph.vert[idx];
			
			if (!used[nv]) {
				topsortDFS(nv);
			}
			
		}
		
		order[orderedIdx++] = v;
	}
	
	
	
	// Types
	
	class Graph {
		
		int[] head;
		int[] next;
		int[] vert;
		int cnt = 1;
		
		Graph(int vNum, int eNum) {
			head = new int [vNum];
			next = new int [eNum + 1];
			vert = new int [eNum + 1];
		}
		
		void addEdge(int u, int v) {
			next[cnt] = head[u];
			vert[cnt] = v;						
			head[u] = cnt++;
		}
		
	}
	
	class Item {
		int id;
		int[] values;

		Item(int id, int[] values) {
			this.id = id;
			this.values = values;
		}
		
		@Override
		public String toString() {
			return id + " " + Arrays.toString(values);
		}
	}
	
	class RowComparator implements Comparator<Item> {
		
		int rowIdx;
		
		public RowComparator(int row) {
			this.rowIdx = row;
		}

		@Override
		public int compare(Item i1, Item i2) {
			return i1.values[rowIdx] - i2.values[rowIdx];
		}
		
	}
	
	/*************************************************************** 
	 * Input 
	 **************************************************************/
	BufferedReader in;
	PrintWriter out;
	StringTokenizer st = new StringTokenizer("");
	
	String nextToken() throws IOException {
		while (!st.hasMoreTokens())
			st = new StringTokenizer(in.readLine());
		return st.nextToken();
	}
	
	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}
	
	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}
	
	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}
	
	int[] nextIntArray(int size) throws IOException {
		int[] ret = new int [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextInt();
		return ret;
	}
	
	long[] nextLongArray(int size) throws IOException {
		long[] ret = new long [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextLong();
		return ret;
	}
	
	double[] nextDoubleArray(int size) throws IOException {
		double[] ret = new double [size];
		for (int i = 0; i < size; i++)
			ret[i] = nextDouble();
		return ret;
	}
	
	String nextLine() throws IOException {
		st = new StringTokenizer("");
		return in.readLine();
	}
	
	boolean EOF() throws IOException {
		while (!st.hasMoreTokens()) {
			String s = in.readLine();
			if (s == null)
				return true;
			st = new StringTokenizer(s);
		}
		return false;
	}
	
	/*************************************************************** 
	 * Output 
	 **************************************************************/
	void printRepeat(String s, int count) {
		for (int i = 0; i < count; i++)
			out.print(s);
	}
	
	void printArray(int[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(long[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.print(array[i]);
		}
		out.println();
	}
	
	void printArray(double[] array, String spec) {
		if (array == null || array.length == 0)
			return;
		for (int i = 0; i < array.length; i++) {
			if (i > 0) out.print(' ');
			out.printf(Locale.US, spec, array[i]);
		}
		out.println();
	}
	
	void printArray(Object[] array) {
		if (array == null || array.length == 0)
			return;
		boolean blank = false;
		for (Object x : array) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	@SuppressWarnings("rawtypes")
	void printCollection(Collection collection) {
		if (collection == null || collection.isEmpty())
			return;
		boolean blank = false;
		for (Object x : collection) {
			if (blank) out.print(' '); else blank = true;
			out.print(x);
		}
		out.println();
	}
	
	/*************************************************************** 
	 * Utility
	 **************************************************************/
	static String memoryStatus() {
		return (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory() >> 20) + "/" + (Runtime.getRuntime().totalMemory() >> 20) + " MB";
	}
	
	static void checkMemory() {
		System.err.println(memoryStatus());
	}
	
	static long prevTimeStamp = Long.MIN_VALUE;
	
	static void updateTimer() {
		prevTimeStamp = System.currentTimeMillis();
	}
	
	static long elapsedTime() {
		return (System.currentTimeMillis() - prevTimeStamp);
	}
	
	static void checkTimer() {
		System.err.println(elapsedTime() + " ms");
	}
	
	static void chk(boolean f) {
		if (!f) throw new RuntimeException("Assert failed");
	}
	
	static void chk(boolean f, String format, Object ... args) {
		if (!f) throw new RuntimeException(String.format(format, args));
	}
	
	static void log(String format, Object ... args) {
		if (writeLog) System.err.println(String.format(Locale.US, format, args));
	}
}