#1125. 【NFLSPC #4】船

题目类型:传统型 时间限制:1000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:Special Judge

题目背景

一位船主,打算让一条移民船出海航行。他心里清楚,这条船已经老旧并且从一开始就造的不是甚好,而她已久经风浪常常需要修理。船主在怀疑这条船已经无法再经风浪,这种怀疑侵袭着他的思想,让他不快。他想,或许,即便要花上一大笔钱也要对这条船进行彻底的整修。但是,在船出航之前他成功克服了这种悲观反应。他对自己说这条船经历了如此多的航行,历经了多少风浪,认为她无法从这次航程中平安归来是一件很没意义的事。他信了神,神不会背弃那些背井离乡,去外边寻找更好生活的可悲家庭。船主从心底打消对造船者和承包人诚信的一切小心眼的怀疑。这样,他就能获得一种真诚而舒适的信念相信他的船能彻底安全,能经受得住风浪,以一种愉快的心情,船主看着船启程了,并且亲切地祝愿这些流亡者在他们奇特的新家中一切顺利。而他则会在船在海中沉掉,杳无音讯时获得他那份保险金。我们该怎么评述他呢?当然,对于那些死去的家庭他罪恶滔天。需要承认的是,他真切地相信他的船的可靠性。但是,他的真切信念绝对无法为他提供帮助。因为,他没有权利相信他面前的这等事实,他的信念并非从耐心调查中确实地得来而是通过扼杀自己的疑虑而造就。尽管到了最后,他认为无比确定再也想不到别的结果。既然他知道且乐意将自己放进那种思想条框中,那么,他就必须为此负责。
                                                                                                - 威廉·金顿·克利福德

题目描述

在一个平面直角坐标系中,如果 $n$ ($n>2$) 个点互相连通(本题中连通被定义为四连通,即若 $(x,y)$ 存在,其与 $(x-1,y)(x+1,y)(x,y-1)(x,y+1)$ 四个点中的存在者直接连接)且包含原点(即 $(0,0)$),它们被称为为一片大小为 $n$ 的海域。考虑一艘从原点出发的航行在海域内的船。每个单位时间,船会等概率地航行到海域内的某个相邻点上。定义海域的危险程度为这艘船第一次返回原点的时间的数学期望。你需要提供一份海域,使得海域的危险程度尽量大。


数学期望

数学期望是试验中每次可能结果的概率乘以其结果的总和。(摘自百度百科)

公式为 $E(x)=\sum_{i=1}^{+\infty} {p_i} {x_i}$

比如某个数,它有 $0.1$ 的概率是 $1$,有 $0.9$ 的概率是 $2$,那么它的数学期望是 $1.9$。


输入格式

一行,一个整数 $n$。

输出格式

输出 $n$ 行,每行两个整数,表示海域中一个点的坐标。

你应该使海域符合要求并且危险程度尽量大。


样例

input

3

output

0 0
0 1
0 2

样例解释

这个海域的危险程度为 $4$。


成绩评定

对单个测试点来说,如果你的代码没能在规定的时间和空间内输出一个正确的大小为 $n$ 的海域的描述(连通,无重复点,包含原点)则得 $0$ 分。

否则设 $x$ 为你描述的海域的危险程度,$y$ 为 std 描述的海域的危险程度,你的得分为:

若 $y \leq x$ 得 $100$ 分;

否则得 $\left\lfloor \frac {100 x} {y} \right\rfloor$ 分。

这道题的总得分会是所有单个测试点的得分的最小值。


限制与约定

  • 保证 $3 \leq n \leq 10^6$。

$by\ \text{skyline}$