Nauuo是一个喜欢下棋的女孩。
有一天,她自己发明了一种游戏,需要$$$n$$$棋子才能在$$$m\times m$$$棋盘上下棋。行和列的编号从 $$$1$$$ 到 $$$m$$$。我们将第 $$$r$$$ 行和第 $$$c$$$ 列的交叉点上的单元格表示为 $$$(r,c)$$$。
游戏的目标是将编号从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 棋子放置在棋盘上,第 $$$i$$$ 棋子位于 $$$(r_i,\,c_i)$$$ 上,同时满足以下规则:对于所有棋子对 $$$i$$$ 和 $$$j$$$, $$$|r_i-r_j|+|c_i-c_j|\ge|i-j|$$$。这里$$$|x|$$$表示$$$x$$$的绝对值。
然而,Nauuo发现,有时她找不到解决办法,因为棋盘太小了。
她想找到最小的棋盘,可以根据规则放置 $$$n$$$ 个棋子。
她还想知道如何将棋子放在这样的棋盘上。你能帮助她吗?
输入
唯一的一行包含一个整数 $$$n$$$ ($$$1\le n\le 1000$$$) — 游戏的棋子数量。
输出
第一行包含一个整数 - $$$m$$$ 的最小值,其中 $$$m$$$ 是合适棋盘的边长。
接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$r_i$$$ 和 $$$c_i$$$ ($$$1\le r_i,c_i\le m$$$) — 第 $$$i$$$ 棋子的坐标。
如果有多个答案,请打印其中一个。
示例
输入 #1
2
输出 #1
2 1 1 1 2
输入 #2
4
输出 #2
3 1 1 1 3 3 1 3 3
注意
在第一个示例中,如果不违反规则,则无法将两个棋子放在 $$$1\times1$$$ 棋盘上。但是你可以将两颗棋子放在 $$$2\times2$$$ 棋盘上,如下所示:
在第二个示例中,您不能在 $$$2\times2$$$ 棋盘上放置四个棋子而不违反规则。例如,如果您像这样放置碎片:
则 $$$|r_1-r_3|+|c_1-c_3|=|1-2|+|1-1|=1$$$, $$$|1-3|=2$$$, $$$1<2$$$;和 $$$|r_1-r_4|+|c_1-c_4|=|1-2|+|1-2|=2$$$、$$$|1-4|=3$$$、$$$2<3$$$。它不满足规则。
但是,在 $$$3\times3$$$ 棋盘上,您可以像这样放置四个棋子: