G. Задача Императора
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Это произошло во времена Великой Берляндской Империи. Однажды Император увидел сон, в котором к нему явился Посланник богов и приказал построить храм с выпуклым n-угольником в основании. На следующее утро Император отдал распоряжение возвести храм, в основании которого лежит правильный n-угольник. Храм был построен, но вскоре Империю постигли бедствия и неурожаи. После того, как случилось землетрясение, разрушившее храм, Император понял, что чем-то навлек на свой народ немилость богов. Он приказал позвать к себе Мудреца. Когда явился Мудрец, Император поведал ему о своем сне и задал вопрос: «Дай же мне ответ, о Мудрейший из Мудрых, чем мог я прогневить богов?». «О, Владыко!» — отвечал мудрец. — «Насколько дано мне судить, боги гневаются оттого, что ты поторопился выполнять их поручение и не дослушал Посланника до конца».

Действительно, на следующую же ночь Посланник явился вновь. Он укорял Императора за то, что тот выбрал несовершенную форму для храма. «Так какая же форма может быть совершеннее, чем правильный n-угольник?!!» — воскликнул император во сне. На что Посланник дал подробный и обстоятельный ответ.

  • Все вершины многоугольника должны располагаться в точках с целочисленными координатами.
  • Все длины его сторон должны быть различны.
  • Из всех таких многоугольников должен быть выбран такой, длина максимальной стороны которого минимальна.

Вы — подневольный архитектор, которому предстоит спроектировать храм. Учтите, что n-угольник должен быть простым (имеющим границу без самопересечений и наложений) и выпуклым, но при этом допускается, чтобы три последовательные вершины лежали на одной прямой.

Входные данные

В первой строке задано единственное число n (3 ≤ n ≤ 10000).

Выходные данные

В первой строке выведите «YES» (без кавычек), если n-угольник, обладающий требуемыми свойствами, построить возможно. В следующих n строках выведите целочисленные координаты вершин многоугольника в порядке обхода против часовой стрелки. Координаты не должны превосходить 109 по абсолютной величине. Никакие две вершины не должны совпадать. Разрешается выводить любое из возможных решений. Если многоугольник построить невозможно, выведите «NO».

Примеры
Входные данные
3
Выходные данные
YES
0 0
1 0
0 2
Входные данные
3
Выходные данные
YES
0 1
-1 0
-1 -1