K Square Resistance Value

問題

制限時間: 1 sec メモリ制限: 1024 MB

Square Resistance Value

Statement

抵抗値 $1\;[\Omega]$ の抵抗のみを用いて抵抗値 $\sqrt{D}\;[\Omega]$ の抵抗を作ってください。

正整数 $D$ が与えられます。次の条件をすべて満たす連結無向グラフをひとつ構築してください。本問題の制約下では条件を満たすグラフが常に存在することを証明できます。

頂点数 $N$ は $2$ 以上 $300$ 以下で、各頂点には $1$ から $N$ までの相異なる番号がついている
辺数 $M$ は $300$ 以下で、自己ループや多重辺を含んでよい
以下のように定義される「頂点 $1$ から頂点 $N$ への合成抵抗の大きさ」が $\sqrt D$ の絶対誤差 $\pm 10^{-6}$ に収まる

$G$ を $n$ 頂点 $m$ 辺連結無向グラフ $(n\geq2)$ として、$j$ 番目の辺は頂点 $a_j,b_j$ を結ぶとします。グラフ $G$ の各頂点に実数 $V_i\;(i=1,2,\cdots,n)$、各辺に実数 $I_j\;(j=1,2,\cdots,m)$ を、以下の等式をすべて満たすように割り当てることを考えます。

$I_j = V_{a_j}-V_{b_j}\;\;(j=1,2,\cdots,m)$
$\displaystyle\sum_{b_j=i} I_j-\sum_{a_j=i}I_j = 0\;\;(i=2,3,\cdots,n-1)$
$\displaystyle\sum_{b_j=n} I_j-\sum_{a_j=n}I_j = 1$

このような割り当てが常に存在し、さらに $V_1-V_n$ の値が一意に定まることを証明できるので、この値を「頂点 $1$ から頂点 $n$ への合成抵抗の大きさ」と定めます。

Input

$1$ 行に正整数 $D$ が与えられる。( $1 \leq D \leq 5000$ )

Output

$1$ 行目には構築したグラフの頂点数 $N$ と辺数 $M$ をこの順に空白区切りで出力せよ。

続く $M$ 行のうち $i\;(i=1,2,\cdots, M)$ 行目には、$i$ 番目に選んだ辺の端点を空白区切りで出力せよ。

条件を満たすグラフが複数考えられるときはそのうちどれを出力してもよい。

Example

Input 1

Output 1

Note

$1$ つ目のサンプルの出力を図解したものが以下です。

$\text{[math]}$

頂点 $1$ から頂点 $n$ への合成抵抗が $1\;[\Omega]$ であることは、以下の通りに説明されます。

抵抗は全て $1\;[\Omega]$ であること、対称性より頂点 $2$ と頂点 $3$ の電位が等しくなることから、それらの間にかかる抵抗は存在しないものとして扱える。
その結果、 $1\;[\Omega]$ の抵抗が $2$ つ直列に並んだものが $2$ 並列になっている抵抗へと帰着される。
$1\;[\Omega]$ の抵抗が $2$ つ直列に並んだものの合成抵抗は $2\;[\Omega]$ であり、 $2\;[\Omega]$ の抵抗が $2$ 並列になったものの合成抵抗は $1\;[\Omega]$ です。

他にも、以下の出力も正答とみなされます。

2 1

1 2

サンプル

b0889451ffb555fc879adb52e694ac0e7889a8d6.png