Ljeto je i malom Josipu je dosadno. Većina njegovih prijatelja otišla je raditi u neku stranu državu. Primoran da se sam zabavlja, odlučio je igrati “Zmije i ljestve” sam protiv sebe.

Igru igra na igraćoj ploči koja ima N redaka i M stupaca. Polja se označavaju kao na slici. Na ploči se nalazi Z zmija i L ljestvi, a svatko od njih povezuju po dva različita polja na ploči. Zmija povezuje polje na kojem se nalazi njena glava s poljem na kojem se nalazi njen rep, a ljestve povezuju polje na kojem se nalazi njihov početak s poljem na kojem se nalazi njihov kraj. Za svaku zmiju vrijedi da se njezina glava nalazi na polju koje ima veću oznaku nego polje na kojem se nalazi njezin rep. Za svake ljestve vrijedi da se početak ljestvi nalazi na polju koje ima manju oznaku nego polje na kojem se nalazi kraj ljestvi. Na početku igre figura s kojom se igra nalazi se na polju s oznakom 1.

Pravila igre su sljedeća:

• igrač baci igraću kockicu, dobije na njoj broj A i onda A puta ponovi jedan od ponuđenih poteza. Neka se figura trenutno nalazi na polju s oznakom x. Ako se na tom polju:
  • ne nalazi niti zmijina glava niti početak ljestvi, tada se figura pomiče na polje x+1.
  • nalazi zmijina glava, tada se figura mora premjestiti na polje gdje se nalazi rep te zmije.
  • nalazi početak ljestvi, igrač može odabrati hoće li svoju figuru pomaknuti na polje na kojem je kraj tih ljestvi ili će se pomaknuti na polje x+1.
• ako je figura u nekom trenutku igranja ovih A poteza izašla s ploče, mora se vratiti na poziciju na kojoj je bila prije bacanja kocke i time prestaje ponavljanje poteza za to bacanje.

Josip će K puta bacati kockicu i za svako bacanje zna koji će broj dobiti. On je osmislio dvije strategije za igranje ove igre. U prvoj strategiji će kada god može birati hoće li otići na vrh ljestvi ili će otići na polje s oznakom x+1 odabrati otići na vrh ljestvi. U drugoj strategiji Josip će igrati optimalno, odnosno pomicat će figuru tako da se nakon svih poteza figura nalazi na polju s najvećom oznakom od svih polja na kojima je figura mogla završiti.

Iako je Josip veoma pametan dečko, zamolio je tebe da odrediš na kojem će polju završiti njegova figura ako igra igru s prvom strategijom, a na kojem ako igra s drugom strategijom.

Ulazni podaci

U prvom retku nalaze se prirodni brojevi N i M (1 ≤ N, M ≤ 100), brojevi iz teksta zadatka.

U drugom retku nalaze se cijeli nenegativni brojevi Z i L (0 ≤ Z, L ≤ (N+M) / 2), brojevi iz teksta zadatka.

U trećem retku nalazi se prirodan broj K (1 ≤ K ≤ 100), broj iz teksta zadatka.

U četvrtom retku nalazi se K prirodnih brojeva Ai (1 ≤ Ai ≤ 6, i=1..K) odvojenih razmakom, pri čemu je Ai broj koji će Josip dobiti u i-tom bacanju kockice.

U sljedećih Z redaka nalaze se prirodni brojevi Gi i Ri (1 ≤ Ri < Gi ≤ N*M), oznake polja gdje se nalaze glava i rep i-te zmije.

U sljedećih L redaka nalaze se prirodni brojevi Si i Fi (1 ≤ Si < Fi ≤ N*M), oznake polja gdje se nalaze početak i kraj i-tih ljestvi.

Svako polje na ploči bit će ili prazno ili će na njemu biti glava ili rep točno jedne zmije ili će na njemu biti početak ili kraj točno jednih ljestvi.

Izlazni podaci

Ispiši matricu znakova s N redaka i M stupaca koja predstavlja igraću ploču iz teksta zadatka tako da se na nekom polju treba nalaziti: znak ‘.’ ako tamo ne završava figura ni s jednom strategijom, znak ‘P’ ako tamo završava figura korištenjem prve strategije, znak ‘D’ ako tamo završava figura korištenjem druge strategije te znak ‘T’ ako tamo završava figura korištenjem i prve i druge strategije.

Probni primjeri

Ulaz

3 3
0 1
1
5
5 9

Izlaz

..T
...
...

Ulaz

3 3
1 1
1
4
9 1
2 8

Izlaz

...
.D.
P..

Opis drugog probnog primjera:

Kada Josip koristi prvu strategiju, baci kockicu i odigra sljedeća 4 poteza:

1. potez: nalazi se na polju s oznakom 1, tamo nema ništa i pomakne se na polje s oznakom 2.
2. potez: nalazi se na polju s oznakom 2, tamo su ljestve do polja s oznakom 8 pa se tamo pomakne.
3. potez: nalazi se na polju s oznakom 8, tamo nema ništa i pomakne se na polje s oznakom 9.
4. potez: nalazi se na polju s oznakom 9, tamo je zmijina glava pa se mora pomaknuti na zmijin rep, tj. na polje s oznakom 1.

Kada Josip koristi drugu strategiju, baci kockicu i odigra sljedeća 4 poteza:

1. potez: nalazi se na polju s oznakom 1, tamo nema ništa i pomakne se na polje s oznakom 2.
2. potez: nalazi se na polju s oznakom 2, tamo su ljestve, ali on odabere da će se pomaknuti na polje s oznakom 3.
3. potez: nalazi se na polju s oznakom 3, tamo nema ništa i pomakne se na polje s oznakom 4.
4. potez: nalazi se na polju s oznakom 4, tamo nema ništa i pomakne se na polje s oznakom 5.