Problem: Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony.

<image>

A sequence of positive integers bi is harmony if and only if for every two elements of the sequence their greatest common divisor equals 1. According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

<image>

You are given sequence ai, help Princess Twilight to find the key.

Input

The first line contains an integer n (1 ≤ n ≤ 100) — the number of elements of the sequences a and b. The next line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 30).

Output

Output the key — sequence bi that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

Examples

Input

5
1 1 1 1 1


Output

1 1 1 1 1 

Input

5
1 6 4 2 8


Output

1 5 3 1 8 

Solution (in JAVA):

Solution:
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.math.BigInteger.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

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

@SuppressWarnings("unused")
public class B {

	public B () {
		int _N = sc.nextInt();
		Integer [] _A = obj(sc.nextInts());
		int [] J = si(_A); sort(_A);

		Integer [] A = _A;
		if (_A.length > 16) A = copyOfRange(_A, _A.length - 16, _A.length);
		int N = min(_N, 16);

		int MAX = 59;
		int [] P = primes(MAX - 1); int M = (1 << P.length);
		int [] L = new int [MAX];
		for (int i : rep(MAX))
			for (int j : rep(P.length))
				if (i % P[j] == 0)
					L[i] |= bit(j);

		@SuppressWarnings("unchecked")
		List<Integer> [] Y = new List[M];
		for (int j : rep(M)) {
			Y[j] = new ArrayList<>();
			for (int k : rep(MAX))
				if ((j & L[k]) == 0)
					Y[j].add(k);
		}

		int [][][] F = new int [N+1][M][3];
		for (int i : req(1, N))
			for (int j : rep(M))
				F[i][j][0] = INF;



		for (int i : rep(N))
			for (int j : rep(M))
				for (int k : Y[j]) {
					int x = F[i][j][0] + abs(k - A[i]);
					if (x < F[i+1][j|L[k]][0]) {
						F[i+1][j|L[k]] = new int [] { x, j, k };
					}
				}

		int Q = INF; int b = -1;
		for (int j : rep(M))
			if (F[N][j][0] < Q) {
				Q = F[N][j][0];
				b = j;
			}

		LinkedList<Integer> T = new LinkedList<>();
		for (int i : sep(N)) {
			T.addFirst(F[i+1][b][2]);
			b = F[i+1][b][1];
		}

		while (T.size() < _N)
			T.addFirst(1);

		int [] res = new int [_N];
		for (int i : rep(_N))
			res[J[i]] = T.get(i);
		exit(res);
	}

	private static final double eps = 1e-9;
	private static final int INF = (int) 1e9;
	private static final long LINF = (long) 1e18;
	private static final double DINF = 1e50;
	private static final int MOD = (int) 1e9 + 7;
	///////////////////////////////////////////////////////////////////////////
	private static <K, V> void add (Map<K, List<V>> map, K key, V value) {
		if (!map.containsKey(key))
			map.put(key, new ArrayList<V>());
		map.get(key).add(value);
	}
	private static long and (long x, int i) { return (x & bit(i)); }
	private static <T> T [] a (@SuppressWarnings("unchecked") T ... A) { return A; }
	private static long bit (int i) { return (1L << i); }
	private static int [] cc (int [][] E, int N) {
		int [] res = singletons(N);
		dsu(E, 0, E.length, res);
		for (int i = 0; i < N; ++i)
			res[i] = root(res, i);
		return res;
	}
	private static int [] ccw (int [] D) { return new int [] { -D[1], D[0] }; }
	private static long ceil(double x) { return round(Math.ceil(x - eps)); }
	private static long ceil (long p, long q) { return fc(p, q, true); }
	private static <T> String chain(@SuppressWarnings("unchecked") T ... A) {
		StringBuilder res = new StringBuilder();
		for (T a : A) res.append(a);
		return res.toString();
	}
	private static double [] cross (double [] X, double [] Y) { assert X.length <= 3 && Y.length <= 3; X = copyOf(X, 3); Y = copyOf(Y, 3); return new double [] { X[1]*Y[2] - Y[1]*X[2], X[2]*Y[0] - Y[2]*X[0], X[0]*Y[1] - Y[0]*X[1] }; }
	private static int [] cw (int [] D) { return new int [] { D[1], -D[0] }; }
	private static Comparator<int[]> comp() { return new Comparator<int[]>() { public int compare(int[] x, int[] y) { return x[0] - y[0]; }}; }
	private static int [] dec(int ... A) {
		int [] res = A.clone();
		for (int i = 0; i < A.length; ++i)
			--res[i];
		return res;
	}
	private static int [][] dec(int [] ... E) {
		for (int [] e : E)
			for (int i = 0; i < e.length; ++i)
				--e[i];
		return E;
	}
	private static <T> T deepClone(T A) {
		try {
			ByteArrayOutputStream bout = new ByteArrayOutputStream();
			ObjectOutputStream  out = new ObjectOutputStream(bout);
			out.writeObject(A);
			ByteArrayInputStream bin = new ByteArrayInputStream(bout.toByteArray());
			ObjectInputStream in = new ObjectInputStream(bin);
			@SuppressWarnings("unchecked") T res = (T)in.readObject();
			return res;
		} catch (Exception e) {
			throw new Error(e);
		}
	}
	private static int [][] dgraph (int N, int [][] E) { return dwgraph(N, E)[0]; }
	private static int [][][] dwgraph(int N, int [][] E) {
		int [] D = new int [N];
		for (int [] e : E)
			++D[e[0]];
		int [][][] res = new int [2][N][];
		for (int i = 0; i < 2; ++i)
			for (int j = 0; j < N; ++j)
				res[i][j] = new int [D[j]];
		D = new int [N];
		for (int [] e : E) {
			int x = e[0], y = e[1], z = e.length > 2 ? e[2] : 1;
			res[0][x][D[x]] = y;
			res[1][x][D[x]] = z;
			++D[x];
		}
		return res;
	}
	private static double [] diff (double [] X, double [] Y) { return sum(X, scalar(-1, Y)); }
	private static int [] digits(long N, int B, int sz) {
		int [] res = new int [sz];
		for (int i = sz - 1; i >= 0; --i)
			if (N > 0) {
				res[i] = (int)(N % B);
				N /= B;
			}
		return res;
	}
	private static int digitSum(long N) {
		int res = 0;
		for (; N > 0; res += N % 10, N /= 10);
		return res;
	}
	private static double dist (double [] X, double [] Y) { return norm(diff(X, Y)); }
	private static long [] distinctPrimeDivisors(long N) {
		List<Long> res = new ArrayList<Long>();
		for (long p = 2; p*p <= N; ++p) {
			if (N % p == 0)
				res.add(p);
			while (N % p == 0)
				N /= p;
		}
		if (N > 1)
			res.add(N);
		return pri(res.toArray(e(0L)));
	}
	private static double dot(double [] X, double [] Y) { double res = 0; for (int i = 0; i < min(X.length, Y.length); ++i) res += X[i] * Y[i]; return res; }
	private static boolean dsu(int u, int v, int [] C) {
		u = root(C, u);
		v = root(C, v);
		C[u] = C[v];
		return u != v;
	}
	private static int dsu(int [][] E, int s, int t, int [] C) {
		int res = 0;
		for (int i = s; i < t; ++i)
			if (dsu(E[i][0], E[i][1], C))
				++res;
		return res;
	}
	private static int [][] dup(int [][] E) {
		int [][] res = new int [2*E.length][];
		for (int i = 0; i < E.length; ++i) {
			res[2*i] = E[i].clone();
			res[2*i+1] = E[i].clone();
			res[2*i+1][0] = E[i][1]; res[2*i+1][1] = E[i][0];
		}
		return res;
	}
	private static <T> T [] e (@SuppressWarnings("unchecked") T ... A) { return newArray(A, 0); }
	private static long [] envelope(long [] f, long [] c) {
		int N = f.length;
		long [] res = new long [N]; res[0] = f[0];
		int [] T = new int [N]; int Z = 0;
		for (int i = 1, k = 0; i < N; ++i) {
			for (;;)
				if (Z > 0 && (f[i] - f[T[Z]]) * (T[Z] - T[Z-1]) <=  (f[T[Z]] - f[T[Z-1]]) * (i - T[Z]))
					--Z;
				else {
					T[++Z] = i;
					break;
				}

			k = min(k, Z);
			for (; k < Z && (f[T[k+1]] - f[T[k]]) <= c[i] * (T[k+1] - T[k]); ++k);
			res[i] = f[T[k]] - c[i] * T[k];
		}
		return res;
	}
	private static boolean eq(double x, double y) { return abs(x - y) < eps; }
	private static boolean eq(double [] X, double [] Y) { return eq(dist(X, Y), 0); }
	private static long [] fact(int N) {
		long [] res = new long [N+1];
		res[0] = 1;
		for (int i = 1; i <= N; ++i)
			res[i] = res[i-1] * i;
		return res;
	}
	private static long fc(long p, long q, boolean up) {
		if (up) {
			if (q < 0) return fc(-p, -q, true);
			else if (p < 0) return -fc(-p, q, false);
			else return (p+q-1) / q;
		} else if (q < 0) return fc(-p, -q, false);
		else if (p < 0) return -fc(-p, q, true);
		else return p / q;
	}
	private static long floor(double x) { return round(Math.floor(x + eps)); }
	private static long floor(long p, long q) { return fc(p, q, false); }
	private static <T extends Comparable<T>> int fmax(T [] A) { return fmax(A, 0, A.length); }
	private static <T extends Comparable<T>> int fmax(T [] A, int s, int t) {
		int res = s;
		for (int i = s; i < t; ++i)
			if (A[i].compareTo(A[res]) > 0)
				res = i;
		return res;
	}
	private static <T extends Comparable<T>> int fmin(T [] A) { return fmin(A, 0, A.length); }
	private static <T extends Comparable<T>> int fmin(T [] A, int s, int t) {
		int res = s;
		for (int i = s; i < t; ++i)
			if (A[i].compareTo(A[res]) < 0)
				res = i;
		return res;
	}
	private static int [] freq(int [] A, int N) {
		int [] res = new int [N];
		for (int i = 0; i < A.length; ++i)
			++res[A[i]];
		return res;
	}
	private static boolean [][] fw(boolean [][] G) {
		int N = G.length;
		for (int k = 0; k < N; ++k)
			for (int i = 0; i < N; ++i)
				for (int j = 0; j < N; ++j)
					G[i][j] = G[i][j] || (G[i][k] && G[k][j]);
		return G;
	}
	private static long [][] fw(long [][] G) {
		int N = G.length;
		for (int k = 0; k < N; ++k)
			for (int i = 0; i < N; ++i)
				for (int j = 0; j < N; ++j)
					G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
		return G;
	}
	private static long gcd(long x, long y) { return BigInteger.valueOf(x).gcd(BigInteger.valueOf(y)).longValue(); }
	private static <K, V> V get(Map<K, V> map, K key) { return key != null ? map.get(key) : null; }
	private static boolean geq(double x, double y) { return x > y - eps; }
	private static int [][] graph (int N, int [][] E) { return wgraph(N, E)[0]; }
	private static boolean greater(double x, double y) { return x > y + eps; }
	private static boolean has(long x, int i) { return and(x, i) != 0; }
	private static int [] hungarian (long [][] C) {
		int T = C.length, N = T > 0 ? C[0].length : 0;
		assert (N >= T);
		if (T < N) {
			C = copyOf(C, N);
			for (int i = T; i < N; ++i)
				C[i] = new long [N];
		}
		long [] YS = new long [N], YT = new long [N];
		int [] M = new int [N], res = new int [N];
		fill(M, -1); fill(res, -1);

		for (int n = 0; n < N; ++n) {
			int [] Z = new int [N], Q = new int [N];
			long [] L = new long [N];
			fill(Z, -1); fill(L, LINF);

			int t = -1, fi = 0, la = 0;
			for (int i = 0; i < N; ++i)
				if (res[i] == -1)
					Q[la++] = i;

			boolean [] VS = new boolean [N], VT = new boolean [N];
			out: for (;;) {
				while (fi < la) {
					int x = Q[fi++]; VS[x] = true;
					for (int j = 0; j < N; ++j)
						if (!VT[j]) {
							long p = L[j];
							if ((L[j] = min(L[j], C[x][j] - YS[x] - YT[j])) < p) {
								int z = M[j]; Z[j] = x;
								if (L[j] == 0) {
									VT[j] = true;
									if (z == -1) {
										t = j; break out;
									}
									else if (!VS[z])
										Q[la++] = z;
								}
							}
						}
				}

				long D = LINF;
				for (int j = 0; j < N; ++j)
					if (!VT[j])
						D = min(D, L[j]);
				for (int i = 0; i < N; ++i)
					if (VS[i])
						YS[i] += D;
				for (int j = 0; j < N; ++j)
					if (VT[j])
						YT[j] -= D;
					else
						L[j] -= D;
				for (int j = 0; j < N; ++j)
					if (!VT[j] && L[j] == 0) {
						VT[j] = true; int z = M[j];
						if (z == -1) {
							t = j; break out;
						}
						else if (!VS[z])
							Q[la++] = z;
					}
			}

			while (t != -1) {
				int u = res[M[t] = Z[t]];
				res[M[t]] = t;
				t = u;
			}
		}

		res = copyOf(res, T);
		return res;
	}
	private static int [] inc(int ... A) {
		for (int i = 0; i < A.length; ++i)
			++A[i];
		return A;
	}
	private static boolean integer(double x) { return eq(x, floor(x)); }
	private static int [] invert(int [] J) {
		int N = J.length;
		int [] res = new int [N];
		for (int i = 0; i < N; ++i)
			res[J[i]] = i;
		return res;
	}
	private static long [][] islands(int N) {
		long [][] res = new long [N][N];
		for (long [] r : res)
			fill(r, LINF);
		for (int i = 0; i < N; ++i)
			res[i][i] = 0;
		return res;
	}
	private static long lcm(int ... A) {
		long res = 1;
		for (int a : A)
			res = lcm(res, a);
		return res;
	}
	private static long lcm(long x, long y) { return x/gcd(x, y)*y; }
	private static boolean leq(double x, double y) { return x < y + eps; }
	private static boolean less(double x, double y) { return  x < y - eps; }
	private static int [][] manacher(char [] C, char separator) {
		int N = C.length, M = 2*N+1;
		char [] D = new char [M]; fill(D, separator);
		for (int i = 0; i < N; ++i)
			D[2*i+1] = C[i];
		int [] L = new int [M];
		int c = 0, r = 0;
		int m = 0, n = 0;
		for (int i = 1; i < M; i++) {
			if (i > r) {
				L[i] = 0; m = i-1; n = i+1;
			} else {
				int j = 2*c - i;
				if (L[j] < (r-i)) {
					L[i] = L[j];
					m = -1;
				} else {
					L[i] = r-i;
					n = r+1; m = 2*i - n;
				}
			}
			while (m >= 0 && n < M && D[m] == D[n]) {
				++L[i]; --m; ++n;
			}
			if ((i + L[i]) > r) {
				c = i; r = i + L[i];
			}
		}
		int [][] res = new int [2][N];
		for (int i = 0; i < N; ++ i) {
			res[0][i] = L[2*i+2];
			res[1][i] = L[2*i+1];
		}
		return res;
	}
	private static <T extends Comparable<T>> T maximum(T x, T y) { return x.compareTo(y) > 0 ? x : y; }
	private static <T extends Comparable<T>> T maximum(@SuppressWarnings("unchecked") T ... A) { return A[fmax(A)]; }
	private static <T extends Comparable<T>> T median(@SuppressWarnings("unchecked") T ... A) {
		assert A.length > 0;
		T [] B = A.clone();
		sort(B);
		T res = B[B.length/2];
		return res;
	}
	private static long minCost(long [][] C) {
		long res = 0; int [] H = hungarian(C);
		for (int i = 0; i < C.length; ++i)
			res += C[i][H[i]];
		return res;
	}
	private static <T extends Comparable<T>> T minimum(T x, T y) { return x.compareTo(y) < 0 ? x : y; }
	private static <T extends Comparable<T>> T minimum(@SuppressWarnings("unchecked") T ... A) { return A[fmin(A)]; }
	private static long mod(long x) { return mod(x, MOD); }
	private static long mod(long x, long mod) { return ((x % mod) + mod) % mod; }
	private static long [][] modBin(int N, int K) {
		long [][] res = new long [N+1][K+1];
		for (int n = 0; n <= N; ++n) {
			res[n][0] = 1;
			for (int k = 1; k <= K && k <= n; ++k)
				res[n][k] = mod(res[n-1][k] + res[n-1][k-1]);
		}
		return res;
	}
	private static long [] modFact(int N) {
		long [] res = new long [N+1]; res[0] = 1;
		for (int i = 1; i <= N; ++i)
			res[i] = mod(res[i-1] * i);
		return res;
	}
	private static long modInv(long x) { return modPow(x, -1); }
	private static long modPow(long b, long e) { return BigInteger.valueOf(b).modPow(BigInteger.valueOf(e), BigInteger.valueOf(MOD)).longValue(); }
	private static <T> T [] newArray(T [] A, int N) {
		T [] res = copyOf(A, N);
		fill(res, null);
		return res;
	}
	private static <T> T [][] newArray(T [][] A, int N, int M) {
		T [][] res = copyOf(A, N); assert N > 0;
		for (int i = 0; i < N; ++i)
			res[i] = newArray(A[0], M);
		return res;
	}
	private static double norm (double ... X) { return sqrt(dot(X, X)); }
	private static double [] normalize (double ... X) { return eq(norm(X), 0) ? X : scalar(1/norm(X), X); }
	private static Character [] obj (char ... A) { Character [] res = new Character [A.length];	for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static Character [][] obj (char [] ... A) { Character [][] res = new Character [A.length][]; for (int i = 0; i < A.length; ++i) res[i] = obj(A[i]); return res; }
	private static Integer [] obj (int ... A) { Integer [] res = new Integer [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static Integer [][] obj (int [] ... A) { Integer [][] res = new Integer [A.length][]; for (int i = 0; i < A.length; ++i) res[i] = obj(A[i]); return res; }
	private static Long [] obj (long ... A) { Long [] res = new Long [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static long or(long x, int i) { return (x | bit(i)); }
	private static int [] pa (int ... A) { return A; }
	private static <T> boolean palindrome(T X) {
		char [] C = X.toString().toCharArray();
		int N = C.length;
		for (int i = 0; 2*i <= N; ++i)
			if (C[i] != C[N-i-1])
				return false;
		return true;
	}
	private static int [][] permutations(int N) {
		if (N == 1)
			return new int [][] {{ 0 }};
		int [][] P = permutations(N-1);
		int [][] res = new int[N * P.length][N];
		for (int i = 0, n = 0; i < P.length; ++i)
			for (int j = 0; j < N; ++j, ++n) {
				for (int k = 0; k < N-1; ++k) {
					int x = P[i][k];
					res[n][k] = x < j ? x : x+1;
				}
				res[n][N-1] = j;
			}
		return res;
	}
	private static <T> T [] permute(T [] A, int [] J) {
		T [] res = A.clone();
		for (int i = 0; i < J.length; ++i)
			res[i] = A[J[i]];
		return res;
	}
	private static long pow (long b, int e) { return BigInteger.valueOf(b).pow(e).min(BigInteger.valueOf(LINF)).longValue(); }
	private static PriorityQueue<int[]> pq() { return new PriorityQueue<>(10, comp()); }
	private static int [] prefix(char [] C) {
		int [] res = new int [C.length];
		prefix(C, C, res, 0);
		return res;
	}
	private static void prefix(char [] C, char [] P, int [] F, int i) {
		int j = i > 0 ? F[i-1] : 0;
		for (int k = 0; k < C.length; ++k)
			if (i+k > 0) {
				while (j > 0 && C[k] != P[j])
					j = F[j-1];
				if (C[k] == P[j])
					++j;
				F[i+k] = j;
			}
	}
	private static double [] pri(Double [] A) { double [] res = new double [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static double [][] pri(Double [][] A) { double [][] res = new double [A.length][]; for (int i = 0; i < A.length; ++i) res[i] = pri(A[i]); return res; }
	private static int [] pri(Integer [] A) { int [] res = new int [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static int [][] pri(Integer [][] A) { int [][] res = new int [A.length][]; for (int i = 0; i < A.length; ++i) res[i] = pri(A[i]); return res; }
	private static long [] pri(Long [] A) { long [] res = new long [A.length]; for (int i = 0; i < A.length; ++i) res[i] = A[i]; return res; }
	private static char [][] pri(String [] S) {	char [][] res = new char [S.length][]; for (int i = 0; i < S.length; ++i) res[i] = S[i].toCharArray(); return res; }
	private static boolean prime(long N) { return BigInteger.valueOf(N).isProbablePrime(50); }
	private static long [] primeFactorization(long N) {
		List<Long> res = new ArrayList<Long>();
		for (long p = 2; p*p <= N; ++p)
			while (N % p == 0) {
				res.add(p);
				N /= p;
			}
		if (N > 1)
			res.add(N);
		return pri(res.toArray(e(0L)));
	}
	private static int [] primes(int N) {
		boolean [] C = new boolean [N+1];
		int Q = (int)floor(sqrt(N));
		for (int p = 3; p <= Q; p += 2)
			if (!C[p]) {
				int R = N/p;
				for (int j = p; j <= R; ++j)
					C[j*p] = true;
			}
		List<Integer> res = new ArrayList<Integer>();
		if (N >= 2)
			res.add(2);
		for (int p = 3; p <= N; p += 2)
			if (!C[p])
				res.add(p);
		return pri(res.toArray(e(0)));
	}
	private static double [] project(double [] X, double [] K) { return diff(X, scalar(dot(X,K)/dot(K,K), K)); }
	private static long qnorm (long ... X) {
		long S = 0;
		for (long x : X)
			S += x*x;
		return S;
	}
	private static int [] rep(int N) { return rep(0, N); }
	private static int [] rep(int S, int T) { if (T <= S) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static int [] req(int N) { return req(0, N); }
	private static int [] req(int S, int T) { return rep(S, T+1); }
	private static String reverse (String S) { return new StringBuilder(S).reverse().toString(); }
	private static int root (int [] C, int s) {
		int res = s;
		while (C[res] != res)
			res = C[res];
		int v = s;
		while (v != res) {
			v = C[v];
			C[v] = res;
		}
		return C[s] = res;
	}
	private static <T> T [][] rotate (T [][] A) {
		assert A.length > 0 && A[0].length > 0;
		int N = A.length, M = A[0].length;
		T [][] res = newArray(A, M, N);
		for (int i = 0; i < N; ++i)
			for (int j = 0; j < M; ++j) {
				int [] R = rotate(A, i, j);
				res[R[0]][R[1]] = A[i][j];
			}
		return res;
	}
	private static <T> int [] rotate (T [][] A, int i, int j) {
		assert i < A.length && j < A[0].length;
		return pri(a(A[0].length - 1 - j, i));
	}
	private static double [] scalar (double c, double ... X) { double [] res = new double [X.length]; for (int i = 0; i < X.length; ++i) res[i] = c * X[i]; return res; }
	private static int [] sep(int N) { return sep(0, N); }
	private static int [] sep(int S, int T) { if (T <= S) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[T-1-i] = i; return res; }
	private static int [] seq(int S, int T) { return sep(S, T+1); }
	private static <T> T [] shift(T [] A, int k) {
		int N = A.length;
		T [] res = newArray(A, N+k);
		System.arraycopy(A, 0, res, k, N);
		return res;
	}
	private static <T extends Comparable<T>> int [] si(final T [] X) { return si(X, reverseOrder(reverseOrder())); }
	private static <T> int [] si(final T [] X, final Comparator<T> C) {
		int N = X.length;
		Integer [] res = obj(rep(N));
		sort(res, new Comparator<Integer>() {
			public int compare(Integer i, Integer j) {
				int res = C.compare(X[i], X[j]);
				return res != 0 ? res : i.compareTo(j);
			}
		});
		return pri(res);
	}
	private static int [] singletons(int N) { return rep(N); }
	private static <T> Queue<T> stack() { return asLifoQueue(new LinkedList<T>()); }
	private static double [] sum (double [] ... X) {
		int L = 0;
		for (double[] x : X)
			L = max(L, x.length);
		double [] res = new double [L];
		for (double[] x : X)
			for (int j = 0; j < x.length; ++j)
				res[j] += x[j];
		return res;
	}
	private static <T> T [] ta(Collection<T> C, T t) { @SuppressWarnings("unchecked") T[] res = C.toArray(e(t)); return res; }
	private static int [] toInt(long [] A) { int [] res = new int [A.length]; for (int i = 0; i < A.length; ++i) res[i] = (int)A[i]; return res; }
	private static String [] toString(char [] ... A) { String [] res = new String[A.length]; for (int i = 0; i < A.length; ++i) res[i] = new String(A[i]); return res; }
	private static String toString(long x, int L) {
		long D = 1;
		for (int i = 0; i < L; ++i, D *= 10);
		String res = ("" + (D + x)).substring(1);
		return res;
	}
	private static <T> T [][] transpose(T [][] S) {
		int R = S.length, C = S[0].length;
		T [][] res = newArray(S, C);
		for (int i = 0; i < C; ++i) {
			res[i] = newArray(S[0], R);
			for (int j = 0; j < R; ++j)
				res[i][j] = S[j][i];
		}
		return res;
	}
	private static int [][] treeToEdges(int [] T) {
		int [][] res = new int [T.length - 1][];
		for (int i = 0, j = 0; i < T.length; ++i)
			if (T[i] != i)
				res[j++] = new int [] { T[i], i };
		return res;
	}
	private static <T> Tuple<T> tuple (@SuppressWarnings("unchecked") T ... A) { return new Tuple<T>(A); }
	private static int [][] vtk(int [][] KV, int W) {
		int [] C = new int [W+1];
		for (int [] kv : KV)
			C[kv[1]]++;
		int [][] res = new int [W+1][];
		for (int v = 0; v <= W; ++v)
			res[v] = new int [C[v]];
		fill(C, 0);
		for (int [] kv : KV)
			res[kv[1]][C[kv[1]]++] = kv[0];
		return res;
	}
	private static <T> Map<T, Integer> vtk(@SuppressWarnings("unchecked") T ... A) {
		Map<T, Integer> res = new HashMap<>();
		for (int i = 0; i < A.length; ++i)
			res.put(A[i], i);
		return res;
	}
	private static int [][][] wgraph(int N, int [][] E) { return dwgraph(N, dup(E)); }
	private static boolean zero(double ... X) { return eq(norm(X), 0); }
	private static int [] z(char [] C) {
		int [] res = new int [C.length];
		int L = 0, R = 1;
		for (int i = 1; i < C.length; ++i) {
			if (i < R) {
				res[i] = min(res[i-L], R-i);
				if (res[i] == R-i)
					for (int j = 0; R+j < C.length && C[R+j] == C[R-i+j]; ++j, ++res[i]);
			} else
				for (int j = 0; i+j < C.length && C[i+j] == C[j]; ++j, ++res[i]);
			if (res[i] >= R-i) {
				L = i;
				R = i + res[i];
			}
		}
		return res;
	}
	////////////////////////////////////////////////////////////////////////////////////
	private static class AhoCorasick {
		private static class Node {
			final String val; boolean in; Node sf, dsf;
			final Map<Character, Node> ch = new HashMap<>();
			Node(String val) { this.val = val; }
			String suffix(char c) {
				if (ch.containsKey(c))
					return ch.get(c).val;
				else if (sf != null)
					return sf.suffix(c);
				else
					return "";
			}
			void words(Collection<String> C) {
				if (in)
					C.add(val);
				if (dsf != null)
					dsf.words(C);
			}
		}
		private final Map<String, Node> all = new HashMap<String, Node>();
		private final Node root = new Node("");
		public AhoCorasick(String [] W) {
			all.put(root.val, root);
			for (String w : W) {
				Node p = root;
				for (int i = 0; i < w.length(); ++i) {
					Node q = get(w.substring(0, i+1));
					p.ch.put(w.charAt(i), q);
					p = q;
				}
				p.in = true;
			}
			for (Node p : all.values()) {
				String v = p.val;
				while (p.sf == null && v.length() > 0) {
					v = v.substring(1);
					p.sf = all.get(v);
				}
				if (p.sf != null && p.sf.in)
					p.dsf = p.sf;
				while (p.dsf == null && v.length() > 0) {
					v = v.substring(1);
					Node q = all.get(v);
					if (q != null && q.in)
						p.dsf = q;
				}
			}
		}
		public String [] prefixes() { return all.keySet().toArray(e("")); }
		public String suffix(String p, char c) { return all.get(p).suffix(c); }
		public String [] words(String p) {
			List<String> res = new ArrayList<>();
			all.get(p).words(res);
			return res.toArray(new String [0]);
		}
		private Node get(String v) {
			if (!all.containsKey(v))
				all.put(v, new Node(v));
			return all.get(v);
		}
	}
	private static class Circle {
		public final double [] C;
		public final double R;
		public static final Circle R2 = new Circle(new double [2], INF);
		public Circle(double [] C, double R) { this.C = C; this.R = R; }
		public static Circle toCircumference(double [] ... X) {
			assert X.length > 0 && X.length <= 3;
			switch(X.length) {
			case 1: return new Circle(X[0], 0);
			case 2: return new Circle(scalar(.5, sum(X)), .5 * dist(X[0], X[1]));
			case 3:
				if (eq(X[0], X[1])) return toCircumference(X[1], X[2]);
				else if (eq(X[1], X[2])) return toCircumference(X[2], X[0]);
				else if (eq(X[2], X[0])) return toCircumference(X[0], X[1]);
				else return	calc(X[0], X[1], X[2]);
			default: throw new Error();
			}
		}
		public static Circle toCircle(double [] ... X) {
			assert X.length > 0; shuffle(asList(X));
			return welzl(X, X.length, new double[3][], 0);
		}
		private static Circle calc(double [] X, double [] Y, double [] Z) {
			assert X.length == 2 && Y.length == 2 && Z.length == 2;
			boolean u = eq(X[0], Y[0]), v = eq(Y[0], Z[0]);
			if (u && v) return R2;
			else if (u) return calc(Y, Z, X);
			else if (v) return calc(Z, X, Y);
			else {
				double U = (Y[1] - X[1]) / (Y[0] - X[0]);
				double V = (Z[1] - Y[1]) / (Z[0] - Y[0]);
				if (eq(U, V)) return R2;
				if (eq(U, 0)) return calc(Z, Y, X);
				double CX = (U * V * (X[1] - Z[1]) + V * (X[0] + Y[0]) - U * (Y[0] + Z[0])) / (2 * (V - U));
				double CY = ((X[0] + Y[0]) / 2 - CX) / U + (X[1] + Y[1]) / 2;
				double [] C = new double [] { CX, CY };
				double R = dist(C, X); assert eq(dist(C, Y), R) && eq(dist(C, Z), R);
				return new Circle(C, R);
			}
		}
		private static Circle welzl(double [][] X, int N, double [][] S, int K) {
			if (K == 3) return Circle.toCircumference(S);
			else if (K == 0 && N == 1) return new Circle(X[0], 0);
			else if (K == 1 && N == 1) return Circle.toCircumference(S[0], X[0]);
			else if (K == 2 && N == 0) return Circle.toCircumference(S[0], S[1]);
			else {
				Circle C = welzl(X, N-1, S, K);
				if (greater(dist(C.C, X[N-1]), C.R)) {
					S[K++] = X[N-1];
					C = welzl(X, N-1, S, K);
				}
				return C;
			}
		}
		public String toString() { Map<String, Object> M = new HashMap<>(); M.put("C", Arrays.toString(C)); M.put("R", R); return M.toString(); }
	}
	private static class Fenwick {
		private final long [] X;
		public Fenwick(int N) { X = new long [N]; }
		public void add(long x, int i) {
			++i; assert i <= X.length;
			while (i <= X.length) {
				X[i-1] += x; // MOD?
				i += (i & (-i));
			}
		}
		public long get(int to) {
			assert to <= X.length;
			long res = 0;
			for (; to > 0; res += X[to-1], to -= (to & (-to)));
			return res;
		}
	}
	private static class LCA {
		private int [][] P;
		private int [] L, T;
		private int N, G;
		public LCA(int [] T) {
			this.T = T;
			N = T.length; G = Integer.numberOfTrailingZeros(Integer.highestOneBit(2*N));
			L = new int [N]; fill(L, -1);
			for (int i = 0; i < N; ++i)
				level(i);
			P = new int [N][G];
			for (int i = 0; i < N; ++i)
				for (int j = 0; 1 << j < N; ++j)
					P[i][j] = -1;
			for (int i = 0; i < N; ++i)
				P[i][0] = T[i];
			for (int j = 1; (1 << j) < N; ++j)
				for (int i = 0; i < N; ++i)
					if (P[i][j - 1] != -1)
						P[i][j] = P[P[i][j - 1]][j - 1];
		}
		public int query(int p, int q) {
			if (L[p] < L[q])
				return query(q, p);
			int log; for (log = 1; (1 << log) <= L[p]; ++log); --log;
			for (int i = log; i >= 0; --i)
				if (L[p] - (1 << i) >= L[q])
					p = P[p][i];
			if (p == q)
				return p;
			for (int i = log; i >= 0; --i)
				if (P[p][i] != -1 && P[p][i] != P[q][i]) {
					p = P[p][i]; q = P[q][i];
				}
			return T[p];
		}
		private int level(int i) {
			if (T[i] == i)
				L[i] = 0;
			else if (L[i] == -1)
				L[i] = 1 + level(T[i]);
			return L[i];
		}
	}
	private static class MatrixRangeSum {
		private final long [][] S;
		public long get(int r1, int c1, int r2, int c2) { return S[r2][c2] - S[r1][c2] - S[r2][c1] + S[r1][c1]; }
		public MatrixRangeSum (long [][] A) {
			int R = A.length, C = A[0].length;
			S = new long [R+1][C+1];
			for (int i = 1; i <= R; ++i)
				for (int j = 1; j <= C; ++j)
					S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i-1][j-1];
		}
	}
	private static class Rodrigues {
		private final double [] K, T;
		public Rodrigues(double ... A) {
			assert A.length <= 3; A = copyOf(A, 3);
			K = normalize(new double [] { -A[1], A[0] }); double [] L = new double [] { K[1], -K[0] };
			if (!zero(K)) {
				double [] V = new double [3];
				while (zero(V))
					V = project(project(new double [] { random(), random(), random() }, A), K);
				T = normalize(new double [] { dot(L, V), V[2] });
			} else
				T = null;
		}
		public double [] rotate(double ... X) {
			assert X.length <= 3; X = copyOf(X, 3);
			if (T != null) {
				double [] Y = scalar(T[0], X);
				Y = sum(Y, scalar(T[1], cross(K, X)));
				X = sum(Y, scalar(dot(K, X) * (1 - T[0]), K));
			}
			assert eq(X[2], 0);
			return copyOf(X, 2);
		}
	}
	private static class RootedTree {
		final int [] J, D, H;
		RootedTree (int [][] F) {
			int N = F.length;
			int [][] G = new int [N][];
			J = new int [N];
			D = new int [N];
			H = new int [N];
			java.util.Arrays.fill(J, -1);
			int [] C = new int [N], E = new int [N], Q = new int [N];
			int L = 1, K = 0;
			while (L > 0) {
				int q = Q[--L];
				J[q] = K;
				D[K++] = E[q];
				for (int i = 0; i < F[q].length; ++i)
					if (J[F[q][i]] == -1) {
						J[F[q][i]] = -2;
						E[F[q][i]] = 1 + E[q];
						Q[L++] = F[q][i];
					} else
						F[q][i] = -1;
			}
			for (int i = 0; i < N; ++i) {
				for (int j : F[i])
					if (j != -1)
						++C[i];
				G[J[i]] = new int [C[i]];
				for (int j = 0, k = 0; j < F[i].length; ++j)
					if (F[i][j] != -1)
						G[J[i]][k++] = J[F[i][j]];
			}
			int M = 1;
			L = 1;
			Q[0] = 0;
			while (L > 0) {
				int q = Q[--L];
				if (q >= 0) {
					Q[L++] = -(q+1);
					for (int i = 0; i < G[q].length; ++i)
						Q[L++] = G[q][i];
				} else {
					q = -(q+1);
					H[q] = M = max(M, q+1);
				}
			}
		}
	}
	private static class SetNode<T> {
		@SuppressWarnings("rawtypes")
		private final SetNode L, R;
		private final int from, to, m;
		private T X = null;
		public SetNode(int N) { this(0, N); }
		public void set(T X, int from, int to) {
			assert(from >= this.from && to <= this.to && from < to);
			if (from == this.from && to == this.to)
				this.X = X;
			else {
				dfs(this.X, this.from, from);
				dfs(X, from, to);
				dfs(this.X, to, this.to);
				this.X = null;
			}
		}
		@SuppressWarnings("unchecked")
		public T get(int i) {
			assert(from <= i && i < to);
			T res = null;
			if (X != null)
				res = X;
			else if (i < m)
				res = (T)L.get(i);
			else if (i >= m && m > from)
				res = (T)R.get(i);
			else
				assert false;
			return res;
		}
		@SuppressWarnings({ "rawtypes" })
		private SetNode(int from, int to) {
			assert(from < to);
			this.from = from;
			this.to = to;
			m = (from + to) / 2;
			if (m > from) {
				L = new SetNode(from, m);
				R = new SetNode(m, to);
			} else
				L = R = null;
		}
		@SuppressWarnings("unchecked")
		private void dfs(T X, int from, int to) {
			if (X == null)
				return;
			if (from == to)
				return;
			if (from < m)
				L.set(X, from, min(to, m));
			if (to > m)
				R.set(X, max(from, m), to);
		}
	}
	private static class SumNode {
		private final SumNode L, R;
		private final int from, to, m;
		private long X = 0;
		public SumNode(int N) { this(0, N); }
		public void add(long X, int from, int to) {
			assert(from >= this.from && to <= this.to && from < to);
			if (from == this.from && to == this.to)
				this.X += X;
			else {
				if (from < m)
					L.add(X, from, min(to, m));
				if (to > m)
					R.add(X, max(from, m), to);
			}
		}
		private long get(int i) {
			assert(from <= i && i < to);
			long res = X;
			if (i < m)
				res += L.get(i);
			if (i >= m && m > from)
				res += R.get(i);
			return res;
		}
		private SumNode(int from, int to) {
			assert(from < to);
			this.from = from;
			this.to = to;
			m = (from + to) / 2;
			if (m > from) {
				L = new SumNode(from, m);
				R = new SumNode(m, to);
			} else
				L = R = null;
		}
	}
	private static class Tu {
		private static class ple<T> implements Comparable<ple<T>> {
			public final T [] a;
			public ple(@SuppressWarnings("unchecked") T ... a) { this.a = a; }
			@SuppressWarnings("unchecked") public int compareTo(ple<T> o) {
				if (a.length > o.a.length)
					return -o.compareTo(this);
				for (int i = 0; i < a.length; ++i)
					if (((Comparable<T>)a[i]).compareTo(o.a[i]) != 0)
						return ((Comparable<T>)a[i]).compareTo(o.a[i]);
				return a.length - o.a.length;
			}
			@SuppressWarnings("unchecked") public boolean equals(Object o) { return Arrays.equals(a, ((ple<T>)o).a); }
			public int hashCode() { return Arrays.hashCode(a); };
			public String toString() { return Arrays.toString(a); }
		}
	}
	private static class Tuple<T> extends Tu.ple<T> { public Tuple(@SuppressWarnings("unchecked") T ... a) { super(a); }}
	private static abstract class XAbstractMap<K> implements Map<K, Long> {
		private final Map<K, Long> map;
		protected XAbstractMap(Map<K, Long> map) { this.map = map; }
		public void dec(K key) { dec(key, 1); }
		public void dec(K key, long value) { inc(key, -value); }
		public void inc(K key) { inc(key, 1); }
		public void inc(K key, long value) { put(key, get(key) + value); }
		public Entry<K, Long> maximum() {
			Entry<K, Long> res = null;
			for (Entry<K, Long> x : entrySet())
				if (res == null || x.getValue() > res.getValue())
					res = x;
			return res;
		}
		public void maximum(K key, long value) { put(key, max(get(key), value)); }
		public long set(K key, long value) {
			long res = get(key);
			if (value != 0)
				map.put(key, value);
			else
				remove(key);
			return res;
		}
		///////////////////////////////////////////////////////////////////
		public int size() { return map.size(); }
		public boolean isEmpty() { return map.isEmpty(); }
		public boolean containsKey(Object key) { if (!isEmpty()) keySet().iterator().next().getClass().cast(key); return map.containsKey(key); }
		public boolean containsValue(Object value) { return map.containsValue(value); }
		public Long get(Object key) { return containsKey(key) ? map.get(key) : 0; }
		public Long put(K key, Long value) { return set(key, value); }
		public Long remove(Object key) { return map.remove(key); }
		public void putAll(Map<? extends K, ? extends Long> m) { map.putAll(m); }
		public void clear() { map.clear(); }
		public Set<K> keySet() { return map.keySet(); }
		public Collection<Long> values() { return map.values(); }
		public Set<java.util.Map.Entry<K, Long>> entrySet() { return map.entrySet(); }
	}
	private static class XMap<K> extends XAbstractMap<K> { public XMap() { super(new HashMap<K, Long>()); } }
	private static class XTreeMap<K> extends XAbstractMap<K> { public XTreeMap() { super(new TreeMap<K, Long>()); } }
	private final static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static void print (Object o, Object ... A) { IOUtils.print(o, A); }
	private static void println (Object o) { IOUtils.println(o); }
	private static void println (Object o, Object p, Object ... A) { IOUtils.println(o, p, A); }
	private static void clock(Object o, Object ... A) { IOUtils.err(IOUtils.time(), o, A); }
	private static void err(Object o, Object ... A) { IOUtils.err(o, A); }
	private static void exit (Object o, Object ... A) { IOUtils.print(o, A); IOUtils.exit(); }
	private static class IOUtils {
		public static class MyScanner {
			public String next() { newLine(); return line[index++]; }
			public char nextChar() { return next().charAt(0); }
			public int nextInt() { return Integer.parseInt(next()); }
			public long nextLong() { return Long.parseLong(next()); }
			public double nextDouble() { return Double.parseDouble(next()); }
			public String nextLine() { line = null; return readLine(); }
			public String [] nextStrings() { return split(nextLine()); }
			public char [] nextChars() { return next ().toCharArray (); }
			public int [] nextInts() {
				String [] L = nextStrings();
				int [] res = new int [L.length];
				for (int i = 0; i < L.length; ++i)
					res[i] = Integer.parseInt(L[i]);
				return res;
			}
			public long [] nextLongs() {
				String [] L = nextStrings();
				long [] res = new long [L.length];
				for (int i = 0; i < L.length; ++i)
					res[i] = Long.parseLong(L[i]);
				return res;
			}
			public double [] nextDoubles() {
				String [] L = nextStrings();
				double [] res = new double [L.length];
				for (int i = 0; i < L.length; ++i)
					res[i] = Double.parseDouble(L[i]);
				return res;
			}
			public String [] next (int N) {
				String [] res = new String [N];
				for (int i = 0; i < N; ++i)
					res[i] = next();
				return res;
			}
			public int [] nextInt (int N) {
				int [] res = new int [N];
				for (int i = 0; i < N; ++i)
					res[i] = nextInt();
				return res;
			}
			public long [] nextLong (int N) {
				long [] res = new long [N];
				for (int i = 0; i < N; ++i)
					res[i] = nextLong();
				return res;
			}
			public double [] nextDouble (int N) {
				double [] res = new double [N];
				for (int i = 0; i < N; ++i)
					res[i] = nextDouble();
				return res;
			}
			public String [] nextLine(int N) {
				String [] res = new String [N];
				for(int i = 0; i < N; ++i)
					res[i] = nextLine();
				return res;
			}
			public String [][] nextStrings (int N) {
				String [][] res = new String [N][];
				for (int i = 0; i < N; ++i)
					res[i] = nextStrings();
				return res;
			}
			public char [][] nextChars(int N) {
				char [][] res = new char [N][];
				for (int i = 0; i < N; ++i)
					res[i] = nextChars();
				return res;
			}
			public int [][] nextInts (int N) {
				int [][] res = new int [N][];
				for (int i = 0; i < N; ++i)
					res[i] = nextInts();
				return res;
			}
			public long [][] nextLongs (int N) {
				long [][] res = new long [N][];
				for (int i = 0; i < N; ++i)
					res[i] = nextLongs();
				return res;
			}
			public double [][] nextDoubles (int N) {
				double [][] res = new double [N][];
				for (int i = 0; i < N; ++i)
					res[i] = nextDoubles();
				return res;
			}
			//////////////////////////////////////////////
			private boolean eol() { return index == line.length; }
			private String readLine() {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine() {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split(String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build(Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim(String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static void start() { if (t == 0) t = millis(); }
		private static void append(StringBuilder b, Object o, String delim) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					append(b, java.lang.reflect.Array.get(o, i), delim);
			} else if (o instanceof Iterable<?>)
				for (Object p : (Iterable<?>) o)
					append(b, p, delim);
			else {
				if (o instanceof Double)
					o = new java.text.DecimalFormat("#.############").format(o);
				b.append(delim).append(o);
			}
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void print(Object o, Object ... A) { pw.println(build(o, A)); }
		private static void println(Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					print(java.lang.reflect.Array.get(o, i));
			} else if (o instanceof Iterable<?>)
				for (Object p : (Iterable<?>) o)
					print(p);
			else
				print(o);
		}
		private static void println(Object o, Object p, Object ... A) {
			print(o); print(p);
			for (Object q : A)
				print(q);
		}
		private static void err(Object o, Object ... A) { System.err.println(build(o, A)); }
		private static void exit() {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(IOUtils.time());
			System.exit(0);
		}
		private static long t;
		private static long millis() { return System.currentTimeMillis(); }
		private static String time() { return "Time: " + (millis() - t) / 1000.0; }
	}
	////////////////////////////////////////////////////////////////////////////////////
	private static void statics () { parseInt(""); parseLong(""); probablePrime(-1, null); sort(new Object [0]); reverseOrder(); }
	public static void main (String[] args) { new B(); IOUtils.exit(); }
}