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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Emperor implements Runnable {
    static class Side implements Comparable<Side> {
        int dx;
        int dy;
        double alpha;
        Side next;

        public int compareTo(Side side) {
            return Double.compare(alpha, side.alpha);
        }

        public void getAlpha() {
            alpha = Math.atan2(dy, dx);
        }
    }

    static final int MAX = 500;
    static final int MAGIC = 7;
    List<Side> res;
    int tdx;
    int tdy;

    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();
                    s.dx = dx;
                    s.dy = dy;
                    s.next = first[z];
                    first[z] = s;
                }
            }
        int total = 0;
        List<Side> firsts = new ArrayList<Side>();
        for (int len = 1;; ++len) {
            if (first[len] == null)
                continue;
            ++total;
            firsts.add(first[len]);
            if (total < n)
                continue;
            if (doit(firsts, n)) {
                System.err.println(n + " " + total);
                break;
            }
        }
        for (Side s : res)
            s.getAlpha();
        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>();
        tdx = 0;
        tdy = 0;
        return rec(firsts, n, firsts.size() - 1);
    }

    private boolean rec(List<Side> firsts, int toMake, int at) {
        if (toMake == 0) {
            return (tdx == 0 && tdy == 0);
        }
        if (at < 0) {
            throw new RuntimeException();
        }
        if (at >= MAGIC) {
            Side best = firsts.get(at);
            int bdist = (tdx + best.dx) * (tdx + best.dx) + (tdy + best.dy) * (tdy + best.dy);
            Side cur = best.next;
            while (cur != null) {
                int cdist = (tdx + cur.dx) * (tdx + cur.dx) + (tdy + cur.dy) * (tdy + cur.dy);
                if (cdist < bdist) {
                    bdist = cdist;
                    best = cur;
                }
                cur = cur.next;
            }
            res.add(best);
            tdx += best.dx;
            tdy += best.dy;
            if (rec(firsts, toMake - 1, at - 1))
                return true;
            res.remove(res.size() - 1);
            tdx -= best.dx;
            tdy -= best.dy;
        } else {
            Side best = firsts.get(at);
            while (best != null) {
                res.add(best);
                tdx += best.dx;
                tdy += best.dy;
                if (rec(firsts, toMake - 1, at - 1))
                    return true;
                res.remove(res.size() - 1);
                tdx -= best.dx;
                tdy -= best.dy;
                best = best.next;
            }
            if (at >= toMake)
                if (rec(firsts, toMake, at - 1))
                    return true;
        }
        return false;
    }

    public static void main(String[] args) {
        new Emperor().run();
    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter writer;

    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());
    }

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

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

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }
}