E - すぬけそだて――わっか――

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700

問題文

あなたは「すぬけそだて」を楽しんでいます。すぬけ君は、驚くほど賢くなりました!

レベルを上げ、めきめきと知力をつけたすぬけ君は、今や様々なビジネスに手を出しています。すぬけ君の一生懸命に働く姿を見たいあなたは、すぬけ君のオフィスを作ってあげることにしました。

ゲーム内通貨を溜めに溜めたあなたは、ついにすぬけ君の居住スペースを設計するためのアイテム「むげんのわっか」を手に入れました。 「むげんのわっか」は任意の長さの平面上の閉曲線として使うことができ、以下の条件を満たすように配置することができます。

  • 「むげんのわっか」の点のうち 5000 点以下を選ぶ。選んだ点を柱の点と呼ぶ。柱の点では「むげんのわっか」は直角に曲がらなければならない。また、その他の点で曲がってはならない。
  • 2 つの柱の点の間の部分は、x 軸または y 軸に平行でなければならない。
  • すべての柱の点は、x 座標と y 座標がともに絶対値が 10^9 以下の整数である平面上の点に配置されなければならない。
  • すべての柱の点について、その点の配置される平面上の点を、「むげんのわっか」の他の点が通ってはならない。「むげんのわっか」が、柱の点以外で自己交叉することは許される。
  • 「むげんのわっか」によって、平面全体が(外平面も含めて)ちょうど K 個に分割されなければならない。

下図の最初の配置は条件を満たしますが、2 番目や 3 番目の配置は柱の点の配置された点を「むげんのわっか」が二度以上通っているので、条件を満たしません。

K が与えられるので、条件を満たす配置をひとつ求めてください。

制約

  • 2 \leq K \leq 10^6

入力

入力は以下の形式で標準入力から与えられる。

K

出力

最初に、柱の点の個数 N を出力せよ。 その後、N 個の柱の点の配置される座標を順に出力せよ。 i 行目には、i 個目の点の配置される x 座標を表す整数と y 座標を表す整数を空白区切りで出力せよ。


入力例 1

3

出力例 1

6
1 5
1 3
5 3
5 1
3 1
3 5

以下の図のように、平面が 3 つの部分に分かれています。


入力例 2

6

出力例 2

12
2 0
0 0
0 2
6 2
6 0
4 0
4 6
6 6
6 4
0 4
0 6
2 6