事情发生在大贝尔兰帝国时期。有一次,皇帝梦见众神的使者下令建造一座寺庙,其底座是一个有n个角的凸多边形。第二天早上,皇帝下令建造一座寺庙,其基座是n个角的正多边形。寺庙建成了,但很快帝国就因灾难和农作物歉收而动摇。一场地震摧毁了圣殿后,皇帝明白他不知何故让众神的愤怒降临到了他的人民身上。他命人带智者来。当智者出现时,皇帝向他复述了这个梦,并问道:“哦,智者中的智者,请告诉我,我怎么会激怒众神呢?”。 “我的主,”智者回答道。 “据我判断,众神很生气,因为你太急于执行他们的命令,没有听完消息的结尾”。
确实,第二天晚上,信使再次出现。他责备皇帝为寺庙选择了不完美的形状。 “但是还有什么形状能比正多边形更完美呢!?”皇帝在梦中喊道。对此,使者给出了完整而彻底的答复。
- 多边形的所有顶点都应位于晶格点中。
- 所有边的长度都应该不同。
- 从此类多边形的可能范围中,必须选择最大边最小的多边形。
你是一个听话的建筑师,负责制定寺庙的计划。请注意,多边形应该是简单的(具有没有自相交和重叠的边界)并且是凸的,但是三个连续的顶点位于同一条线上是可以接受的。
输入
第一行包含单个数字 n (3 ≤ n ≤ 10000)。
输出
如果可以构建具有所需质量的多边形,则在第一行打印“YES”(不带引号)。在接下来的 n 行中,按照逆时针传递的顺序打印多边形顶点的整数坐标。坐标的绝对值不能超过109。两个顶点不能重合。允许打印任何可能的解决方案。如果无法构建多边形,则打印“NO”。
示例
输入 #1
3
输出 #1
YES 0 0 1 0 0 2
输入 #2
3
输出 #2
YES 0 1 -1 0 -1 -1