Problem: It happened at the times of the Great Berland Empire. Once the Emperor dreamt that the Messenger from the gods ordered to build a temple whose base would be a convex polygon with n angles. Next morning the Emperor gave the command to build a temple whose base was a regular polygon with n angles. The temple was built but soon the Empire was shaken with disasters and crop failures. After an earthquake destroyed the temple, the Emperor understood that he somehow caused the wrath of gods to fall on his people. He ordered to bring the wise man. When the wise man appeared, the Emperor retold the dream to him and asked "Oh the wisest among the wisest, tell me how could I have infuriated the Gods?". "My Lord," the wise man answered. "As far as I can judge, the gods are angry because you were too haste to fulfill their order and didn't listen to the end of the message".

Indeed, on the following night the Messenger appeared again. He reproached the Emperor for having chosen an imperfect shape for the temple. "But what shape can be more perfect than a regular polygon!?" cried the Emperor in his dream. To that the Messenger gave a complete and thorough reply. 

  * All the vertices of the polygon should be positioned in the lattice points. 
  * All the lengths of its sides should be different. 
  * From the possible range of such polygons a polygon which maximum side is minimal possible must be chosen. 



You are an obedient architect who is going to make the temple's plan. Note that the polygon should be simple (having a border without self-intersections and overlapping) and convex, however, it is acceptable for three consecutive vertices to lie on the same line.

Input

The first line contains the single number n (3 ≤ n ≤ 10000).

Output

Print "YES" (without quotes) in the first line if it is possible to build a polygon possessing the needed qualities. In the next n lines print integer coordinates of the polygon vertices in the order in which they would be passed counter clockwise. The absolute value of the coordinates shouldn't exceed 109. No two vertices can coincide. It is permitted to print any of the possible solutions. Print "NO" if to build the polygon is impossible.

Examples

Input

3


Output

YES
0 0
1 0
0 2


Input

3


Output

YES
0 1
-1 0
-1 -1

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
public class Polygon implements Runnable {
		
	public static void main(String[] args) {
		new Polygon().run();
	}
	
	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter writer;
	
	static class Side implements Comparable<Side>{
		int dx;
		int dy;
		double angle;
		Side next;
		
		Side(){
			
		}
		
		public Side(int dx,int dy){
			this.dx=dx;
			this.dy=dy;
		}
		
		public int compareTo(Side side) {
			return Double.compare(angle, side.angle);
		}
		
		public void getAngle() {
			angle=Math.atan2(dy,dx);
		}
		
		public Side add(Side side){
			return new Side(dx+side.dx,dy+side.dy);
		}
		
		public Side sub(Side side){
			return new Side(dx-side.dx,dy-side.dy);
		}
		

		public int value(){
			return dx*dx+dy*dy;
		}
		
		public boolean check(){
			return dx==0 && dy==0;
		}
	}
	
	public static int Max=500;
	public static int Magic=7;
	List<Side> res;
	Side now;
	public int together(Side a,Side b){
		return a.add(b).value();
	}
	
	
	private void solve()throws IOException{
		int n=nextInt();
		Side first[]=new Side[Max*Max+1];
		for(int dx=-Max;dx<=Max;dx++)
			for(int dy=-Max;dy<=Max;dy++){
				int z=dx*dx+dy*dy;
				if(z<=Max*Max){
					Side s=new Side(dx,dy);
					s.next=first[z];
					first[z]=s;
				}
			}
		int cnt=0;
		List<Side> firsts=new ArrayList<Side>();
		for(int len=1;;len++){
			if(first[len]==null)
				continue;
			++cnt;
			firsts.add(first[len]);
			if(cnt<n)
				continue;
			if(doit(firsts,n))
				break;
		}
		for(Side s:res){
			s.getAngle();
		}
		Collections.sort(res);
		int x=0;
		int y=0;
		writer.println("YES");
		for(Side s:res){
			writer.println(x+" "+y);
			x+=s.dx;
			y+=s.dy;
		}
	}
	
	private boolean doit(List<Side> firsts,int n){
		res=new ArrayList<Side>();
		now=new Side(0,0);
		return rec(firsts,n,firsts.size()-1);
	}
	
	private boolean rec(List<Side> firsts,int rest,int at){
		if(rest==0){
			return now.check();
		}
		if(at>=Magic){
			Side cur=firsts.get(at);
			Side best=cur;
			cur=cur.next;
			while(cur!=null){
				if(together(cur, now)<together(best, now)){
					best=cur;
				}
				cur=cur.next;
			}
			res.add(best);
			now=now.add(best);
			if(rec(firsts,rest-1,at-1))
				return true;
			res.remove(res.size()-1);
			now=now.sub(best);
		}else{
			Side best=firsts.get(at);
			while(best!=null){
				res.add(best);
				now=now.add(best);
				if(rec(firsts,rest-1,at-1))
					return true;
				res.remove(res.size()-1);
				now=now.sub(best);
				best=best.next;
			}
			if(at>=rest)
				if(rec(firsts,rest,at-1))
					return true;
		}
		return false;
	}
	
	public void run(){
		try{
			reader=new BufferedReader(new InputStreamReader(System.in));
			tokenizer=null;
			writer=new PrintWriter(System.out);
			solve();
			reader.close();
			writer.close();
		} catch(Exception e){
			e.printStackTrace();
			System.exit(1);
		}
	}
	
	int nextInt() throws IOException{
		return Integer.parseInt(nextToken());
	}
	
	String nextToken() throws IOException {
		while(tokenizer==null || !tokenizer.hasMoreTokens()){
			tokenizer=new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
}