SPOJ in Armenian

Տրված է 2ⁿ  երկարությամբ կող ունեցող քառակուսի տախտակ, որը բաժանված է    2ⁿ  x  2ⁿ միավոր քառակուսիների (վանդակների): Այդ քառակուսիներից ուղիղ մեկը հեռացված է: Պահանջվում է տախտակի մնացած մասը ամբողջությամբ ծածկել անկյունակներով (անկյունակ կանվանենք այն պատկերը որը ստացվում է 2 x 2 քառակուսուց ուղիղ 1 վանդակ հեռացնելով) այնպես, որ ոչ մի երկու անկյունակ հատում չունենան և յուրաքանչյուր անկյունակի յուրաքանչյուր վանդակ լինի տախտակի վրա; կամ նշել որ այդպիսի ծածկույթ գոյություն չունի:

Մուտքը

Առաջին տողում գրված Է  n բնական թիվը (1 ≤ n ≤ 9): Երկրորդ տողում գրված են տախտակից հեռացված միավոր քառակուսու կոորդինատները՝       x , y (1 ≤ x, y ≤ 2ⁿ) ( x-ը տողի իսկ y-ը սյան համարն է, տախտակի ձախ վերևի միավոր քառակուսու կոորդինատն է՝ (1,1)):

ելքը

Ձեր ծրագիրը պետք է արտածի 2ⁿ հատ տող, յուրաքանչյուր տողում 2ⁿ հատ բնական թիվ եթե ծածկույթ գոյություն ունի: x-րդ տողի y-րդ թիվը պետք է ցույց տա (x,y) կոորդինատն ունեցող վանդակը ծածկող անկյունակի համարը: Տախտակից հեռացված վանդակի համապատասխան կոորդինատում պետք է արտածվի 0 թիվը: Անկյունակները համարակալված են 1 ից (2²ⁿ − 1) / 3 թվերով: Երկու անկյունակ չեն կարող համարակալվել նույն թվով: Եթե ծածկույթ գոյություն չունի անհրաժեշտ է արտածել -1 : Բավական է արտածել որևէ ծածկույթ:

Օրինակ

մուտքը.
2
1 1

ելքը.
0 1 3 3
1 1 4 3
2 4 4 5
2 2 5 5

Խնդիրը պատրաստել են Հրայր Հարությունյանը և Ռոբերտ Դավթյանը