Problem description


Supermarket
(F)
Limit pamięci: 1024 MB
Limit czasu: 5.00 s

Jasiu przyszedł do supermarketu po codzienne zakupy i jak zawsze poszukuje swoich ulubionych batoników. Niestety, supermarket jest ogromny, a stoisko znajduje się w jednym z wielu działów. Jasiu stojąc w punkcie (0,0) zapytał ekspedientkę, jak tam dotrzeć, i otrzymał od niej szczegółową instrukcję N komend, gdzie i-ta z nich jest postaci: “Kieruj się w <LEWO|PRAWO|GÓRĘ|DÓŁ> przez Di metrów, a następnie…”.

Jednak jako matematyk, Jasiu nie zapamiętał kierunków, a jedynie długości odcinków, przez które ma iść. Ostatnią szansą na odnalezienie ukochanych batoników Jasia jest jego ślepy strzał do miejsca (X,Y). Sprawdź, czy istnieje przyporządkowanie kierunków do podanych długości, tak aby finalnie Jasiu znalazł się w punkcie (X,Y).

Wejście

W pierwszym wierszu znajdują się trzy liczby N, X oraz Y, oznaczające liczbę komend oraz ślepy strzał Jasia. W kolejnym wierszu znajduje się N liczb opisujących kolejne długości w komendach ekspedientki.

Wyjście

W pierwszym wierszu wypisz NIE, jeśli żadne przyporządkowanie kierunków nie znajdzie się w (X,Y). W przypadku gdy takie przyporządkowanie istnieje, wypisz TAK, a w następnym wierszu napis długości N złożony z G, D, L, P, taki że: jeśli w i-tej komendzie idziesz w górę wypisz G, jeśli idziesz w dół wypisz D, jeśli idziesz w lewo wypisz L, a jeśli w prawo to P.

Ograniczenia

1 ≤ N ≤ 2000, 0 ≤ |X|, |Y| ≤ 3.6 × 106, 1 ≤ Di ≤ 1800

Przykład

Wejście Wyjście Wyjaśnienie
3 3 0
1 1 1
TAK
PPP

Możliwe, że ekspedientka wielokrotnie z rzędu kierowała w tym samym kierunku.

Wejście Wyjście
3 2 -2
1 2 3
TAK
GPD
Wejście Wyjście
2 1 0
1 6
NIE
Wejście Wyjście
5 6 7
1 3 5 7 9
TAK
LGDPG