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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int M = 100013;
set<long long> s;
int a[M], px[M];
vector<pair<double, pair<int, int> > > t;
pair<int, int> xx[M];
int main() {
  srand(1313);
  int n;
  scanf("%d", &n);
  for (int i = 0; i < (M); ++i) a[i] = i;
  a[0] = 1;
  long long sx = 0, sy = 0;
  for (int j = 0; j < (n + 1); ++j) {
    int x = 0;
    long long r = 1LL * a[0] * a[0];
    for (int i = 0; i < (M); ++i) {
      while (s.count(1LL * i * i + 1LL * a[i] * a[i])) a[i]++;
      if (1LL * i * i + 1LL * a[i] * a[i] < r)
        x = i, r = 1LL * i * i + 1LL * a[i] * a[i];
      if (a[i] == i) break;
    }
    if (rand() % 2) {
      sx += x;
      sy += a[x];
      t.push_back(make_pair(atan2(a[x], x), make_pair(x, a[x])));
    } else {
      sx += a[x];
      sy += x;
      t.push_back(make_pair(atan2(x, a[x]), make_pair(a[x], x)));
    }
    s.insert(r);
    a[x]++;
  }
  for (__typeof(((int)(t).size()) - 1) i = (((int)(t).size()) - 1); i >= (1);
       --i)
    if ((sx - t[i].second.first) % 2 == (sy - t[i].second.second) % 2) {
      sx -= t[i].second.first;
      sy -= t[i].second.second;
      for (__typeof(i) j = (i); j <= (((int)(t).size()) - 2); ++j)
        t[j] = t[j + 1];
      t.pop_back();
      if (sx % 2) swap(t[0].second.first, t[0].second.second);
      break;
    }
  for (int i = 0; i < (n); ++i) xx[i] = make_pair(t[i].second.first, i);
  sort(xx, xx + n);
  int ss = 0;
  for (__typeof(n - 1) i = (n - 1); i >= (0); --i)
    if (ss <= 0) {
      ss += xx[i].first;
    } else {
      t[xx[i].second].second.first *= -1;
      ss -= xx[i].first;
    }
  if (ss)
    while (1)
      ;
  for (int i = 0; i < (n); ++i) xx[i] = make_pair(t[i].second.second, i);
  sort(xx, xx + n);
  ss = 0;
  for (__typeof(n - 1) i = (n - 1); i >= (0); --i)
    if (ss <= 0) {
      ss += xx[i].first;
    } else {
      t[xx[i].second].second.second *= -1;
      ss -= xx[i].first;
    }
  if (ss)
    while (1)
      ;
  for (int i = 0; i < (n); ++i)
    t[i].first = atan2(t[i].second.second, t[i].second.first);
  sort(t.begin(), t.end());
  sx = 0, sy = 0;
  puts("YES");
  for (int i = 0; i < (n); ++i) {
    cout << sx << " " << sy << endl;
    sx += t[i].second.first;
    sy += t[i].second.second;
  }
  return 0;
}