Leo Jr. 在笔记本上用方格纸(即每张纸上印有规则的方形网格)画图。我们可以假设片材在任何方向上都是无限大的。
为了绘制图片,Leo Jr. 将工作表上的一些单元格涂成灰色。他认为如果满足以下条件,最终的画面就很漂亮:
- 图片是连通的,也就是说,可以通过沿着灰色单元链从任何一个灰色单元到达任何其他单元,路径中的每对相邻单元都是邻居(即共享一条边)。
- 每个灰色单元格都有偶数个灰色邻居。
- 正好有 $$$n$$$ 个灰色单元格,其邻居都是灰色的。其他灰色单元格的数量可以是任意的(但要合理,以便它们都可以列出)。
Leo Jr. 现在正在努力通过 $$$n$$$ 的特定选择来绘制一幅美丽的图画。帮助他,并提供任何美丽图片的例子。
要在答案中输出单元格坐标,假设工作表提供了笛卡尔坐标系,其中一个单元格被选择为原点 $$$(0, 0)$$$,轴 $$$0x$$$ 和 $$$0y$$$ 与网格线正交并平行,并且沿任何方向的任何轴的单位步长会将您带到相邻的单元格。
输入
唯一的一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 500$$$) — 一幅美丽图片中具有所有灰色邻居的灰色单元格的数量。
输出
在第一行中,打印一个整数 $$$k$$$ — 图片中灰色单元格的数量。由于技术原因,$$$k$$$ 不应超过 $$$5 \cdot 10^5$$$。
以下 $$$k$$$ 行中的每一行都应包含两个整数 - 图片中灰色单元格的坐标。所有列出的单元格应该是不同的,并且图片应该满足上面列出的所有属性。所有坐标的绝对值不应超过 $$$10^9$$$。
可以证明存在一个满足所有要求且 $$$k$$$ 足够小的答案。
示例
输入 #1
4
输出 #1
12 1 0 2 0 0 1 1 1 2 1 3 1 0 2 1 2 2 2 3 2 1 3 2 3
注意
样本的答案如下图所示: