AlgoLiga 2018

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 2¹ do 2¹⁰). 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;n²] 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;10⁴] 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