SPOJ in Armenian

Սու-դոմինո-կու գլուխկոտրուկը սուդոկու խաղի տարբերակ է, որում դատարկ վանդակները պետք է լցնել դոմինոյի քարերի միջոցով։ Ստանդարտ սուդոկուի նման տրված է 9x9 չափի ցանց, որի վանդակները պետք է լցնել 1-ից 9-ը թվանշաններով։ Ճիշտ լրացնելու դեպքում

• Յուրաքանչյուր տող պետք է պարունակի 1-ից 9 բոլոր թվանշանները։
• Յուրաքանչյուր սյուն պետք է պարունակի 1-ից 9 բոլոր թվանշանները։
• Յուրաքանչյուր նշված 3x3 չափի քառակուսի պետք է պարունակի 1-ից 9 բոլոր թվանշանները։

Ինը կամայական վանդակներ սկզբնարժեքավորված են 1-ից 9 թվերով։ Մնում է 72 դատարկ վանդակ։ Դրանք պետք է լրացվեն դոմինոյի 36 քարերի միջոցով։ Դոմինոյի հավաքածուի մեջ 1-ից 9 թվերի յուրաքանչյուր թվազույգի համար (այսինքն՝ (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8), (1,9), (2,3), (2,4), (2,5), ...) կա մեկ խաղաքար։ Նկատենք՝ օրինակ (1,2)-ին և (2,1)-ին համապատասխանում է մեկ խաղաքար և, հետևաբար, այդ դոմինոն կարելի է պտտեցնել։  Նկատենք նաև, որ դոմինոները կարող են հատել 3x3 չափի քառակուսիեների եզրագծերը (ինչպես (2,9) դոմինոն ներքևի օրինակում)։

Օգնության կարգով ձեզ կտրվեն այնպիսի գլուխկոտրուկներ, որոնցում որոշ դոմինոներ տեղադրված են իրենց տեղերում։ Օրինակ՝ նկար 1-ում պատկերված է գլուխկոտրուկի սկզբնական դիրքը, նկար 2-ում պատկվերված է այդ գլուխկոտրուկի միակ լուծումը։

Նկար 1

Նկար 2

Մուտք

Առաջին տողում տրված է սկզբնական դիրքում տեղադրված դոմինոների N քանակը (10 ≤ N ≤ 35):  Հաջորդ N տողերից յուրաքանչյուրում նկարագրված է մեկ դոմինո a La b Lb քառյակի միջոցով։ a-ն դոմինոյի առաջին կեսի թիվն է, իսկ La-ն երկու սիմվոլանոց տող է, որը նկարագրում է a-ի դիրքը խաղատախտակի վրա՝ նկար 1,2-ում տրված կոորդինատային համակարգի միջոցով։ b թիվը և Lb տողը նկարագրում են դոմինոյի մյուս կեսի արժեքը և դիրքը։ Երաշխավորվում է, որ La-ն և Lb-ն նկարագրում են հարևան վանդակներ։ 

Մուտքի վերջին տողում տրված են 1-ից 9 թվերի դիրքերը՝ համաձայն վերը նկարագրվածի։ Մուտքում տրված բոլոր կոորդինատներն իրարից տարբեր են։

Ելք

Ելքում պետք է արտածել գլուխկոտրուկի լուծումը 9x9 չափի թվանշանների աղյուսակի տեսքով, ինչպես ցույց է տրված օրինակում։

Օրինակ

Մուտքը.
10
6 B2 1 B3
2 C4 9 C3
6 D3 8 E3
7 E1 4 F1
8 B7 4 B8
3 F5 2 F6
7 F7 6 F8
5 G4 9 G5
7 I8 8 I9
7 C9 2 B9
C5 A3 D9 I4 A9 E5 A2 C6 I1etc.

Ելքը.
872643195361975842
549218637
126754983
738169254
495832761
284597316
657381429
913426578