Problem: There is a strange peculiarity: if you connect the cities of Rostov, Taganrog and Shakhty, peculiarly, you get a triangle

«Unbelievable But True»

Students from many different parts of Russia and abroad come to Summer Informatics School. You marked the hometowns of the SIS participants on a map.

Now you decided to prepare an interesting infographic based on this map. The first thing you chose to do is to find three cities on this map, such that they form a triangle with area S.

Input

The first line of input contains two integers n and S (3 ≤ n ≤ 2000, 1 ≤ S ≤ 2 ⋅ 10^{18}) — the number of cities on the map and the area of the triangle to be found.

The next n lines contain descriptions of the cities, one per line. Each city is described by its integer coordinates x_i, y_i (-10^9 ≤ x_i, y_i ≤ 10^9). 

It is guaranteed that all cities are located at distinct points. It is also guaranteed that no three cities lie on the same line.

Output

If the solution doesn't exist — print «No».

Otherwise, print «Yes», followed by three pairs of coordinates (x, y) — the locations of the three cities, which form the triangle of area S.

Examples

Input

3 7
0 0
3 0
0 4


Output

No


Input

4 3
0 0
2 0
1 2
1 3


Output

Yes
0 0
1 3
2 0

Solution (in JAVA):

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

public class Main{
	static long crossProduct(long[]p1,long[]p2) {
		return p1[0]*p2[1]-p1[1]*p2[0];
	}
	
	static int compare(long[]p1,long[]p2) {
		long cp=crossProduct(p1, p2);
		if(cp>0) {
			return -1;
		}
		if(cp<0) {
			return 1;
		}
		return 0;
	}
	static long[] vector(long[]point1,long[]point2) {
		return new long[] {point2[0]-point1[0],point2[1]-point1[1]};
	}
	static long[] perpendicular(long[]v) {
		return new long[] {v[1],-v[0]};
	}
	static long[] positiveY(long[]vec) {
		if(vec[1]>=0)return vec;
		vec[0]*=-1;vec[1]*=-1;
		return vec;
	}
	static long areaDoubled(long[]p1,long[]p2,long[]p3) {
		return Math.abs(p1[0]*(p2[1]-p3[1])+p2[0]*(p3[1]-p1[1])+p3[0]*(p1[1]-p2[1]));
	}
	static void answer(long[]p1,long[]p2,long[]p3) {
		pw.println("Yes");
		pw.println(p1[0]+" "+p1[1]);
		pw.println(p2[0]+" "+p2[1]);
		pw.println(p3[0]+" "+p3[1]);
	}
	static void main() throws Exception{
		int n=sc.nextInt();long S=sc.nextLong()*2;
		long[][]in=new long[n][3];
		for(int i=0;i<n;i++) {
			for(int j=0;j<2;j++)in[i][j]=sc.nextInt();
			in[i][2]=i;
		}
		long[][]vecs=new long[n*(n-1)/2][];
		int idx=0;
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				long[]curVec=positiveY(perpendicular(vector(in[i], in[j])));
				vecs[idx++]=new long[] {curVec[0],curVec[1],i,j};
			}
		}
		int[]curIdx=new int[n];
		Arrays.sort(vecs,(x,y)->compare(x,y));
		Arrays.sort(in,(x,y)->x==y?Long.compare(x[1], y[1]):Long.compare(x[0], y[0]));
		
		for(int i=0;i<n;i++) {
			curIdx[(int)in[i][2]]=i;
		}
		
		for(int direction=0;direction<vecs.length;direction++) {
			int idx1=(int)vecs[direction][2],idx2=(int)vecs[direction][3];
			int p1=curIdx[idx1];
			int p2=curIdx[idx2];
			long[] tmp=in[p1].clone();
			in[p1]=in[p2].clone();
			in[p2]=tmp.clone();
			curIdx[idx1]=p2;curIdx[idx2]=p1;
			
			if(p1>p2) {
				int tmpp=p1;
				p1=p2;
				p2=tmpp;
			}
			//now p1 and p2 are beside each other and all points are above or below edge p1-p2
			int lo=p2+1,hi=n-1;
			while(lo<=hi) {
				int mid=(lo+hi)>>1;
				long curArea=areaDoubled(in[p1], in[p2], in[mid]);
				if(curArea==S) {
					answer(in[p1], in[p2], in[mid]);
					return;
				}
				if(curArea>S) {
					hi=mid-1;
				}
				else {
					lo=mid+1;
				}
			}
			
			lo=0;hi=p1-1;
			while(lo<=hi) {
				int mid=(lo+hi)>>1;
				long curArea=areaDoubled(in[p1], in[p2], in[mid]);
				if(curArea==S) {
					answer(in[p1], in[p2], in[mid]);
					return;
				}
				if(curArea>S) {
					lo=mid+1;
				}
				else {
					hi=mid-1;
				}
			}
		}
		
		
		pw.println("No");
	}
	public static void main(String[] args) throws Exception {
		sc = new MScanner(System.in);
		pw = new PrintWriter(System.out);
//		int tc = 1;
//		tc=sc.nextInt();
//		while (tc-- > 0)
			main();
		pw.flush();
	}

	static PrintWriter pw;
	static MScanner sc;

	static class MScanner {
		StringTokenizer st;
		BufferedReader br;

		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

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

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

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

		public int[] intSortedArr(int n) throws IOException {
			int[] in = new int[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}

		public long[] longSortedArr(int n) throws IOException {
			long[] in = new long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}

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

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

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

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

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

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

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}

	static void shuffle(int[] in) {
		for (int i = 0; i < in.length; i++) {
			int idx = (int) (Math.random() * (i + 1));
			int tmp = in[i];
			in[i] = in[idx];
			in[idx] = tmp;
		}
	}

	static void shuffle(long[] in) {
		for (int i = 0; i < in.length; i++) {
			int idx = (int) (Math.random() * (i + 1));
			long tmp = in[i];
			in[i] = in[idx];
			in[idx] = tmp;
		}
	}
}