SPOJ in Armenian

Տրված է 2048 խաղի մի դիրք։ Տրված է նաև ուղղությունը։ Պետք է պատկերել դիրքը տրված ուղղությամբ խաղալուց հետո համարելով, որ նոր թիվ չի ավելանում։

2048-ը մեկ խաղացողով  խաղ է։ Այն իրենից ներկայացնում է 4x4 չափի դաշտ, որի 16 վանդակներում (ոչ անպայման բոլորում) թվեր են գրված, որոնք մեկից մեծ են և հանդիսանում են 2-ի աստիճաններ։ Խաղացողը յուրաքանչյուր քայլին սեղմում է սլաքով ստեղներից մեկը, դրանով նշելով քայլի ուղղությունը։ Այդ դեպքում բոլոր վանդակների թվերը շարժվում են նշված ուղղությամբ, եթե այդ ուղղությամբ հարևան վանդակը ազատ է։ Իսկ եթե նշված ուղղությամբ հարևան վանդակում միևնույն արժեքով թիվ է գրված, այդ դեպքում հարևան վանդակում գրված թիվը կրկնապատկվում է։ Ստացված թիվը չի շարունակում շարժումը։ Իսկ ընթացիկ թվի վանդակը դառնում է ազատ, որն անմիջապես պետք է զբաղեցնի այդ ուղղությամբ եկող հաջորդ թիվը։ Մեկ քայլի ընթացքում յուրաքանչյուր թիվ կարող է ձուլվալ առավելագույնը մեկ թվի հետ։ Տե՛ս օրինակները։

Մուտք

Մուտքի առաջին չորս տողերից յուրաքանչյուրում տրված են չորսական ամբողջ թվեր։ Ազատ տեղերը նշված  են զրոներով։ Մնացած թվերը 2-ի աստիճաններ են և չեն գերազանցում 2048-ը։ Հինգերորդ տողում տրված է քայլի ուղղությունը (Left, Right, Up կամ Down)։

Ելք

Ելքում պետք է արտածել խաղի թվերը կատարված քայլից հետո մուտքի ձևաչափով, այսինքն, չորս տող, յուրաքանչյուրում՝ չորս թիվ, որոնք իրարից պետք է անջատված լինեն մեկ բացակով։ Տողում վերջին թվից հետո բացակ չպիտի լինի։

Օրինակներ

Մուտք.
1024 1024 32 0
4 0 4 4
2 32 16 8
2 8 16 8
Left

Ելք.
2048 32 0 0
8 4 0 0
2 32 16 8
2 8 16 8

Մուտք.
1024 1024 32 0
4 0 0 4
2 32 16 8
2 8 16 8
Up

Ելք.
1024 1024 32 4
4 32 32 16
4 8 0 0
0 0 0 0