Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_22_04 - 2048

Twoim zadaniem jest obliczenie wyniku gry 2048. W grze tej mamy do dyspozycji planszę składającą się z n wierszy i n kolumn. Wiersze numerowane są od góry do dołu zaczynając od 0. Kolumny numerowane są od lewej strony do prawej również zaczynając od 0. Pola mogą być puste albo zawierać jedną z potęg 2 (od 21 do 210). Podczas gry możemy wykonywać cztery rodzaje ruchów:

  • G - wartości we wszystkich kolumnach przesuwane są do górnej krawędzi.
  • D - wartości we wszystkich kolumnach przesuwane są do dolnej krawędzi.
  • L - wartości we wszystkich wierszach przesuwane są do lewej krawędzi.
  • P - wartości we wszystkich wierszach przesuwane są do prawej krawędzi.

Jeżeli w wyniku przesunięcia w danej kolumnie/wierszu (w zależności od ruchu) znajdą się obok siebie dwa pola o takich samych wartościach, to są one łączone w jedno, o wartości równej ich sumie. Suma ta dodawana jest do wyniku gry. Przykładowo, jeżeli po przesunięciu wartości w wierszu do lewej krawędzi mamy następujące liczby: 4 4 4 4 4 2 to po ich połączeniu otrzymamy: 8 8 4 2. Do wyniku dodajemy dwukrotnie liczbę 8. Wartości łączymy zaczynając od tych znajdujących się bliżej krawędzi, do której wykonany został ruch. Po każdym ruchu na jednym z wolnych pól pojawia się wartość 2 albo 4.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita n ∈ [1;10] określająca rozmiar planszy.

W drugiej linii znajduje się jedna liczba całkowita w ∈ [1;n2] oznaczająca liczbę początkowych wartości znajdujących się na planszy. W kolejnych w wierszach znajdują się po trzy liczby całkowite p ∈ [2;1024], y ∈ [0,n) oraz x ∈ [0,n). Oznaczają one, że pole w wierszu y, w kolumnie x ma wartość p.

W następnej linii wejścia znajduje się jedna liczba całkowita r ∈ [1;104] określająca liczbę ruchów do wykonania. Opis każdego z ruchów składa się z jednej z liter: G, D, L albo P oraz trzech liczb całkowitych p ∈ [2;4], y ∈ [0;n) i x ∈ [0;n) oznaczających, że po wykonaniu ruchu, na polu w wierszu y, w kolumnie x pojawi się wartość p.

Wyjście

Na wyjściu należy wypisać wynik gry.

Przykład

Wejście

4
8
4 3 2
4 0 0
8 1 2
8 0 2
8 1 3
4 2 3
2 2 0
8 1 1
4
L 2 3 1
D 2 2 3
L 4 0 2
L 4 1 3

Wyjście

72

Dodane przez:Maciej Boniecki
Data dodania:2015-04-25
Limit czasu wykonania programu:0.200s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.