Ada și Ben sunt pasionați de jocurile pe calculator și tocmai au descoperit cea mai recentă versiune a jocului 2048.

Regulile jocului sunt foarte simple:

• se pornește de la un șir de N piese pe care sunt înscrise numere din mulțimea {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
• piesele sunt așezate în locații numerotate consecutiv cu numerele 1,2,…, N;
• la fiecare pas, poate avea loc o MUTARE la STÂNGA sau o MUTARE la DREAPTA;
• pentru fiecare joc este stabilit un număr maxim de mutări M;
• dacă are loc o MUTARE la DREAPTA, atunci:
  • piesele pot fuziona la dreapta, începând cu penultima piesă din şir: dacă o piesă se află pe o poziție i și are înscrisă valoarea k, iar pe poziția i+1 se află o piesă cu aceeași valoare k, atunci aceste piese vor “fuziona”, pe poziția i+1 se va obține o piesă cu valoarea 2•k, iar pe poziția i rămâne o locație liberă;
  • după efectuarea fuzionărilor, piesele se aliniază la dreapta, astfel încât ultima piesă să se afle pe poziția n;
• dacă are loc o MUTARE la STÂNGA, atunci:
  • piesele pot fuziona la stânga, începând cu a doua piesă din șir: dacă o piesă se află pe o poziție i și are înscrisă valoarea k, iar pe poziția i-1 se află o piesă cu aceeași valoare k , atunci aceste piese vor “fuziona”, pe poziția i-1 se va obține o piesă cu valoarea 2•k, iar pe poziția i rămâne o locație liberă;
  • după efectuarea fuzionărilor, piesele se aliniază la stânga, astfel încât prima piesă să se afle pe poziția 1;
• jocul se încheie atunci când se ajunge în una dintre următoarele situații:
  • pe cel puțin una dintre piese se află înscrisă valoarea 2048;
  • valorile înscrise nu se mai pot modifica prin mutarea pieselor;
  • s-au efectuat toate cele M mutări.

Cerinţe

Scrieţi un program care să citească numerele naturale N (numărul inițial de piese) și M (numărul maxim de mutări), un șir de N numere reprezentând, în ordine, numerele înscrise pe cele N piese și cel mult M caractere din mulțimea {S, D} ce reprezintă mutările fixate de către Ada și Ben, și care determină:
a) numărul X de mutări efectuate până la încheierea jocului;
b) numărul maxim Y înscris pe una dintre piese la încheierea jocului;
c) numărul maxim Z de fuzionări efectuate la o mutare.

Date de intrare

Fișierul de intrare p2048.in conține pe prima linie, separate prin câte un spaţiu, numerele N și M. A doua linie a fişierului conţine cele N numere înscrise, în ordine, pe piese, separate prin câte un spaţiu. A treia linie a fișierului conține cele M caractere, separate prin câte un spaţiu, ce reprezintă cele M direcții de mutare.

Date de ieșire

Fișierul de ieșire p2048.out va conține pe prima linie numărul X, pe a doua linie numărul Y și pe a treia linie numărul Z.

Restricții și precizări

• 2 ≤ N,M ≤ 10000;
• caracterul D indică o mutare la dreapta, iar caracterul S indică o mutare la stânga;
  pentru rezolvarea cerinţei a) se acordă 40% din punctaj, pentru cerinţa b) 40% din punctaj și pentru cerinţa c) 20% din punctaj.

Exemplu:

p2048.in

7 10 
16 4 4 2 2 4 8
D D S D S D S S D D

p2048.out

4
32
2

Explicație

Succesiunea de mutări este reprezentată în figura de mai sus. Au fost efectuate 4 mutări până la încheierea jocului, cea mai mare valoare înscrisă pe una dintre piese fiind 32. Numărul maxim de fuzionări, două, a fost obținut la prima mutare.