Problem: Nezzar loves the game osu!.

osu! is played on beatmaps, which can be seen as an array consisting of distinct points on a plane. A beatmap is called nice if for any three consecutive points A,B,C listed in order, the angle between these three points, centered at B, is strictly less than 90 degrees.

<image> Points A,B,C on the left have angle less than 90 degrees, so they can be three consecutive points of a nice beatmap; Points A',B',C' on the right have angle greater or equal to 90 degrees, so they cannot be three consecutive points of a nice beatmap.

Now Nezzar has a beatmap of n distinct points A_1,A_2,…,A_n. Nezzar would like to reorder these n points so that the resulting beatmap is nice.

Formally, you are required to find a permutation p_1,p_2,…,p_n of integers from 1 to n, such that beatmap A_{p_1},A_{p_2},…,A_{p_n} is nice. If it is impossible, you should determine it.

Input

The first line contains a single integer n (3 ≤ n ≤ 5000).

Then n lines follow, i-th of them contains two integers x_i, y_i (-10^9 ≤ x_i, y_i ≤ 10^9) — coordinates of point A_i.

It is guaranteed that all points are distinct.

Output

If there is no solution, print -1.

Otherwise, print n integers, representing a valid permutation p.

If there are multiple possible answers, you can print any.

Example

Input


5
0 0
5 0
4 2
2 1
3 0


Output


1 2 5 3 4

Note

Here is the illustration for the first test:

<image>

Please note that the angle between A_1, A_2 and A_5, centered at A_2, is treated as 0 degrees. However, angle between A_1, A_5 and A_2, centered at A_5, is treated as 180 degrees.

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main {
	static pair[]a;
	static int n;
	static double  p=Math.PI/2;
	public static boolean isgood(int ind) {
		if(ind==0||ind==n-1)return true;
		return (a[ind+1].x-a[ind].x)*(a[ind-1].x-a[ind].x)+(a[ind+1].y-a[ind].y)*(a[ind-1].y-a[ind].y)>0;
		
	}
	public static void main(String[] args) throws Exception {


		
		n=sc.nextInt();
		a=new pair[n];
		int []b=new int[n];
		for(int i=0;i<n;i++) {
			a[i]=new pair(sc.nextLong(),sc.nextLong());
			b[i]=i+1;
		}
		pair te;
		int tt;
		for(int i=2;i<n;i++) {
			if(isgood(i-1)) {
				continue;
			}else {
				int j=i-1;
				while(j>=0) {
					te=a[j+1];
					a[j+1]=a[j];
					a[j]=te;
					tt=b[j+1];
					b[j+1]=b[j];
					b[j]=tt;
					if(isgood(j)&&(j==0||isgood(j-1))&&(isgood(j+1)||j==i-1)){
						break;
					}
					j--;
				}
			}
		}
		for(int i=0;i<n;i++)pw.print(b[i]+" ");
		
		
		pw.close();
	}
	public static class Point implements Comparable<Point>{

		static final double EPS = 1e-9;

		double x, y;                  

		Point(double a, double b) { x = a; y = b; }  
		
		public int compareTo(Point p)
		{
			if(Math.abs(x - p.x) > EPS) return x > p.x ? 1 : -1;
			if(Math.abs(y - p.y) > EPS) return y > p.y ? 1 : -1;
			return 0;
		}
		
		public double dist(Point p) { return Math.sqrt(sq(x - p.x) + sq(y - p.y)); }
		
		static double sq(double x) { return x * x; }
		
		Point rotate(double angle)
		{
			double c = Math.cos(angle), s = Math.sin(angle);
			return new Point(x * c - y * s, x * s + y * c);
		}
		// for integer points and rotation by 90 (counterclockwise) : swap x and y, negate x
		
		Point rotate(double theta, Point p)			//rotate around p
		{
			Vector v = new Vector(p, new Point(0, 0));
			return translate(v).rotate(theta).translate(v.reverse());
		}
		
		Point translate(Vector v) { return new Point(x + v.x , y + v.y); }
		
		
		
		boolean between(Point p, Point q)
		{
			return x < Math.max(p.x, q.x) + EPS && x + EPS > Math.min(p.x, q.x)
					&& y < Math.max(p.y, q.y) + EPS && y + EPS > Math.min(p.y, q.y);
		}
		
		//returns true if it is on the line defined by a and b
		boolean onLine(Point a, Point b) 
		{
			if(a.compareTo(b) == 0) return compareTo(a) == 0;
			return Math.abs(new Vector(a, b).cross(new Vector(a, this))) < EPS;
		}
		
		boolean onSegment(Point a, Point b)
		{
			if(a.compareTo(b) == 0) return compareTo(a) == 0;
			return onRay(a, b) && onRay(b, a);
		}
		
		//returns true if it is on the ray whose start point is a and passes through b
		boolean onRay(Point a, Point b)
		{
			if(a.compareTo(b) == 0) return compareTo(a) == 0;
			return new Vector(a, b).normalize().equals(new Vector(a, this).normalize());	//implement equals()
		}
		
		// returns true if it is on the left side of Line pq
		
		static boolean collinear(Point p, Point q, Point r)
		{
			return Math.abs(new Vector(p, q).cross(new Vector(p, r))) < EPS;
		}
		
		static double angle(Point a, Point o, Point b)  // angle AOB
		{
			Vector oa = new Vector(o, a), ob = new Vector(o, b);
			return Math.acos(oa.dot(ob) / Math.sqrt(oa.norm2() * ob.norm2()));
		}
		
	
		// Another way: find closest point and calculate the distance between it and p

		
		// Another way: find closest point and calculate the distance between it and p
	}
	public static class Vector {

		double x, y; 

		Vector(double a, double b) { x = a; y = b; }

		Vector(Point a, Point b) { this(b.x - a.x, b.y - a.y); }

		Vector scale(double s) { return new Vector(x * s, y * s); }              //s is a non-negative value

		double dot(Vector v) { return (x * v.x + y * v.y); }

		double cross(Vector v) { return x * v.y - y * v.x; }

		double norm2() { return x * x + y * y; }

		Vector reverse() { return new Vector(-x, -y); }

		Vector normalize() 
		{ 
			double d = Math.sqrt(norm2());
			return scale(1 / d);
		}		
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public long[] nextlongArray(int n) throws IOException {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public Long[] nextLongArray(int n) throws IOException {
			Long[] a = new Long[n];
			for (int i = 0; i < n; i++)
				a[i] = nextLong();
			return a;
		}

		public int[] nextIntArray(int n) throws IOException {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public Integer[] nextIntegerArray(int n) throws IOException {
			Integer[] a = new Integer[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}

	static class pair implements Comparable<pair> {
		long x;
		long y;

		public pair(long x, long y) {
			this.x = x;
			this.y = y;
		}

		public String toString() {
			return x + " " + y;
		}

		public boolean equals(Object o) {
			if (o instanceof pair) {
				pair p = (pair) o;
				return p.x == x && p.y == y;
			}
			return false;
		}

		public int hashCode() {
			return new Double(x).hashCode() * 31 + new Double(y).hashCode();
		}

		public int compareTo(pair other) {
			if (this.x == other.x) {
				return Long.compare(this.y, other.y);
			}
			return Long.compare(this.x, other.x);
		}
	}

	static class tuble implements Comparable<tuble> {
		int x;
		int y;
		int z;

		public tuble(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}

		public String toString() {
			return x + " " + y + " " + z;
		}

		public int compareTo(tuble other) {
			if (this.x == other.x) {
				if (this.y == other.y) {
					return this.z - other.z;
				}
				return this.y - other.y;
			} else {
				return this.x - other.x;
			}
		}
	}

	static long mod = 1000000007;
	static Random rn = new Random();
	static Scanner sc = new Scanner(System.in);
	static PrintWriter pw = new PrintWriter(System.out);
}