SPOJ in Armenian

Տրված n բնական թվի համար հարկավոր է կառուցել պարզ թվերի օղակ։ Այսինքն, պահանջվում է 1-ից n թվերը շրջանաձև դասավորել այնպես, որ յուրաքանչյուր երկու հարևան թվերի գումարը լինի պարզ թիվ։ Օղակում 1-ից n թվերից յուրաքանչյուրը պետք է մասնակցի և պետք է հանդիպի ճիշտ մեկ անգամ։

Մուտք

Մուտքում տրված է մի n (0 < n <= 12) բնական թիվ։ n-ը զույգ է։

Ելք

Ելքային տվյալների տեսքը պետք է լինի այնպես, ինչպես ցույց է տրված օրինակում։ Յուրաքանչյուր տողում պետք է տրված լինի շրջանաձև գրված թվերի մի հաջորդականություն ժամ սլաքի կամ հակառակ ուղղությամբ։ Հաջորդականության ամեն թվից (նաև վերջին թվից) հետո պետք է լինի մեկ բացակ։ Համարակալումը միշտ պետք է սկսվի 1-ից։ Հարկավոր է արտածել բոլոր հնարավոր լուծումները։ Կրկնություն չպետք է լինի։ Լուծումները պետք է դասավորված լինեն բառարանային կարգով։ Դա նշանակում է, որ i-րդ և i+1-րդ հաջորդականությունների համար պետք է գոյություն ունենա այնպիսի մի k թիվ, որ երկու հաջորդականությունների առաջին k անդամներն իրար հավասար են, սակայն i-րդ հաջորդականության k+1-րդ անդամը մեծ է i+1-րդ հաջորդականության k+1-րդ անդամից։

Օրինակներ

Մուտք
6

Ելք
1 4 3 2 5 6
1 6 5 2 3 4

Մուտք
8
Ելք
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2