2048

Cerință

Se dă o matrice de dimensiune $4 \times 4$, în care toate celulele au inițial valoarea $0$. Liniile și coloanele sunt indexate de la $1$ la $4$.

O celulă cu valoarea $0$ este considerată goală. O celulă cu valoare nenulă conține un bloc, iar valoarea celulei este valoarea blocului respectiv.

Inițial nu există niciun bloc în matrice.

Trebuie să afișați o listă de comenzi care vor fi executate, în ordine, asupra matricei. Scopul este să obțineți o celulă cu valoare cât mai mare.

Există două tipuri de comenzi:

• DROP: adaugă un bloc nou de valoare $1$ în celula $(4, 4)$. Această comandă este validă doar dacă celula $(4, 4)$ este goală, adică are valoarea $0$.
• LEFT, RIGHT, UP, DOWN: deplasează toate blocurile din matrice în direcția indicată.

Comenzile sunt simulate de evaluator în ordinea în care sunt afișate. După executarea tuturor comenzilor, punctajul este determinat de valoarea maximă aflată în matrice.

Regula de deplasare

La o comandă de tip LEFT, RIGHT, UP sau DOWN, toate blocurile se deplasează simultan cât mai mult posibil în direcția aleasă.

Pentru fiecare linie sau coloană afectată de direcția mutării, se iau valorile nenule în ordinea deplasării:

• pentru LEFT, fiecare linie se citește de la stânga la dreapta;
• pentru RIGHT, fiecare linie se citește de la dreapta la stânga;
• pentru UP, fiecare coloană se citește de sus în jos;
• pentru DOWN, fiecare coloană se citește de jos în sus.

Celulele goale, adică valorile $0$, sunt ignorate inițial. Apoi lista obținută este parcursă în ordinea deplasării.

Dacă două valori consecutive sunt egale, ele se unesc într-un singur bloc, cu valoarea egală cu suma lor. Cele două blocuri dispar, iar în locul lor apare un singur bloc.

Un bloc obținut printr-o unire nu se mai poate uni încă o dată în aceeași mutare.

După efectuarea tuturor unirilor pentru linia sau coloana respectivă, blocurile rămase sunt așezate cât mai aproape de marginea spre care se face deplasarea, iar restul celulelor devin $0$.

Exemple de deplasare

Pentru comanda LEFT, o linie se transformă astfel:

$[1, 0, 1, 1] \rightarrow [2, 1, 0, 0]$.

Primele două blocuri de valoare $1$ se unesc într-un bloc de valoare $2$, iar al treilea bloc de valoare $1$ rămâne separat.

De asemenea,

$[1, 1, 1, 1] \rightarrow [2, 2, 0, 0]$.

Nu se obține $[4, 0, 0, 0]$, deoarece un bloc nou format prin unire nu se mai poate uni în aceeași mutare.

Un alt exemplu este:

$[2, 2, 4, 4] \rightarrow [4, 8, 0, 0]$.

Pentru comanda RIGHT, linia

$[2, 2, 2, 0]$

devine

$[0, 0, 2, 4]$.

Se observă că unirile se fac în direcția deplasării.

Date de intrare

Nu există date de intrare.

Matricea inițială este întotdeauna:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

Date de ieșire

Afișați pe linii separate câte o comandă. Fiecare comandă trebuie să fie una dintre: DROP, LEFT, RIGHT, UP, DOWN.

Evaluatorul va executa comenzile în ordinea afișată.

Restricții și precizări

• Matricea este întotdeauna de dimensiune $4 \times 4$.
• Valoarea inițială a tuturor celulelor este $0$.
• $0 \leq K \leq 100 \ 000$.
• Comanda DROP este validă doar dacă celula $(4, 4)$ are valoarea $0$ înainte de executarea comenzii.
• Dacă se execută DROP atunci când celula $(4, 4)$ nu este goală, soluția este considerată invalidă.
• Comenzile de deplasare sunt permise chiar dacă nu schimbă matricea.

Punctare

Scorul este calculat în funcție de valoarea maximă obținută în matrice după executarea tuturor comenzilor.

De exemplu, dacă valoarea maximă obținută este $512$, se acordă $60$ de puncte.

Exemplu

stdout

DROP
UP
DROP
UP
DROP
UP
DROP
UP
UP
LEFT

Explicație

Inițial, matricea este goală.

După prima comandă DROP, apare un bloc de valoare $1$ în celula $(4, 4)$.

Comanda UP mută acest bloc în partea de sus a coloanei $4$.

Repetând comenzile DROP și UP, se pot obține mai multe blocuri pe coloana din dreapta.

Blocurile egale care ajung vecine în direcția deplasării se unesc.

După primele $8$ comenzi din exemplu, pe coloana a patra se obține un bloc de valoare $2$ și apoi încă un bloc de valoare $2$. Comanda UP le unește într-un bloc de valoare $4$. Apoi comanda LEFT mută acest bloc spre stânga.

Valoarea maximă obținută în acest exemplu este $4$.