Problem description

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 D_i 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 × 10⁶, 1 ≤ D_i ≤ 1800

Przykład

3 3 0
1 1 1

TAK
PPP

3 2 -2
1 2 3

TAK
GPD

2 1 0
1 6

NIE

5 6 7
1 3 5 7 9

TAK
LGDPG