Програмчлалын олимпиадын бодлогын архив

NxN шатрын хөлөг дээр N ширхэг бэрсийг бүх мөр, багана, диагональ дээр нэгээс илүүгүй бэрс байхаар байрлуулах боломжийн тоог ол (хажуугийн болон гол диагоналиас гадна N-ээс бага урттай бүх диагоналиудыг тооцно).

Input

N бүхэл тоо (N<12)

Output

Эхний гурван байрлуулалтыг эхний гурван мөрөнд дүрсэлнэ (мөр тус бүрийн хувьд хэд дэх багананд бэрс байгааг илэрхийлэх тоонуудыг хооронд нь хоосон зайгаар тусгаарласнаар үүсэх N оронтой тоонуудаас эхний 3-ыг нь хэвлэнэ) Дөрөв дэх мөрөнд нийт боломжийн тоо байна

Example

Input:
7

Output:
1 3 5 7 2 4 6
1 4 7 3 6 2 5
1 5 2 6 3 7 4
40