ある携帯電話会社が次のようなキャンペーンを実施しています。各新規顧客は他の電話番号をちょうど $k$ 個選ぶことができ、その顧客と選んだ $k$ 人の連絡先のいずれかとの間の通話はすべて(双方向とも)無料になります。
$n$ 人の学生のグループ($1$ から $n$ までの番号が付けられています)がこのキャンペーンを利用したいと考えています。各学生 $i$ は集合 $\{1, 2, \dots, n\} \setminus \{i\}$ から相異なる連絡先をちょうど $k$ 人選ばなければなりません。
次のうち少なくとも一方が成り立つとき、2人の学生 $i$ と $j$ は無料で通話できるといいます。
- $i$ が無料連絡先の1人として $j$ を選んでいる、または
- $j$ が無料連絡先の1人として $i$ を選んでいる。
学生たちは、どの学生も他のどの学生とも無料で通話できるように、すなわち $1 \le i < j \le n$ を満たすすべての組 $(i, j)$ について学生 $i$ と $j$ が無料で通話できるように無料連絡先を選びたいと考えています。
与えられた $k$ に対して、あなたの仕事は以下の通りです。
- そのような構成が可能である学生の最大人数 $n$ を求めること、
- この最大の $n$ に対する有効な連絡先の選択構成を1つ構築すること。
入力
入力は単一の整数 $k$ からなります。
出力
1行目に、任意の2人の学生が互いに無料で通話できるように無料連絡先を選ぶことが可能な最大の学生数 $n$ を表す単一の整数を出力してください。
続く $n$ 行に、各学生が選んだ $k$ 人の無料連絡先を出力してください。$i+1$ 行目($1 \le i \le n$)には、$k$ 個の相異なる整数 $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ を出力してください。各 $a_{i,j}$ は $1 \le a_{i,j} \le n$ かつ $a_{i,j} \neq i$ を満たす必要があります。これらの行は、学生 $i$ が無料連絡先として学生 $a_{i,1}, a_{i,2}, \dots, a_{i,k}$ を選んだことを表します。
有効な答えが複数存在する場合は、そのうちのどれを出力しても構いません。
制約
- $1 \le k \le 1000$.
入力例 1
2
5
2 5
3 4
1 5
1 3
2 4
注記
入力例では $k = 2$ であり、任意の2人の学生が互いに無料で通話できるように無料連絡先を選べる最大の学生数は $n = 5$ です。相異なる学生のどの組についても、少なくとも一方が他方を選んでいるため、任意の2人が無料で通話できます。