Lungcircuit

Se dau două circuite, fiecare cu câte $N$ compartimente numerotate de la $0$ la $N - 1$, în sens orar pe circuitul roșu (stâng) și în sens antiorar pe circuitul albastru (drept). $K$ dintre aceste compartimente sunt comune celor două circuite, și anume compartimentele $0, D, 2D, \dots, (K-1)D$.

Circuitele conțin $2N - K$ bile numerotate de la $0$ la $2N - K - 1$. Inițial,

• Bilele $0, 1, \dots, N - 1$ se află în compartimentele $0, 1, \dots, N - 1$ de pe circuitul roșu.
• Bilele $N, N + 1, \dots, 2N - K - 1$ se află în compartimentele $0, 1, \dots, N - 1$ de pe circuitul albastru, sărind peste compartimentele comune.

Putem efectua două tipuri de mutări: Mutarea R rotește circuitul roșu în sens orar cu un compartiment, iar mutarea A rotește circuitul albastru în sens antiorar cu un compartiment.

Figura arată circuitele pentru $N = 32$, $K = 6$ și $D = 3$. O mutare R ar pune bila 0 în locul bilei 1, bila 1 în locul bilei 2, $\dots$, bila 31 în locul bilei 0. O mutare A ar pune bila 0 în locul bilei 32, bila 32 în locul bilei 33, bila 33 în locul bilei 3, $\dots$, bila 57 în locul bilei 0.

Dacă notăm cu $b_0, b_1, \dots, b_{N-1}$ valorile bilelor din compartimentele $0, 1, \dots, N - 1$ ale unui circuit, atunci codificarea circuitului este valoarea

$0 \times b_0 + 1 \times b_1 + 2 \times b_2 + \dots + (N - 1) \times b_{N - 1}$

Cerință

Date fiind $N$, $K$, $D$, $Q$ și o secvență de $Q$ mutări R sau A, tipăriți codificările celor două circuite după efectuarea mutărilor.

Date de intrare

Pe prima linie se află întregii $N$, $K$, $D$ și $Q$. A doua linie conține $Q$ caractere R sau A, fără spații.

Date de ieșire

Afișați două linii, prima conținând codificarea finală a circuitului roșu, iar a doua codificarea finală a circuitului albastru.

Restricții

• $1 \leq N, Q \leq 1 \ 000 \ 000$
• $2 \leq K \leq N$
• $K$ este par
• $(K-1)\cdot D + 1 < N$

Exemple

stdin

7 2 3 4
RRAA

stdout

74
133

stdin

32 6 3 2
RA

stdin

11195
21666

Explicație

În primul exemplu, circuitele evoluează astfel:

Codificarea finală a circuitului roșu este $0 \times 10 + 1 \times 6 + 2 \times 0 + 3 \times 7 + 4 \times 2 + 5 \times 3 + 6 \times 4 = 74$, iar codificarea circuitului albastru este $0 \times 10 + 1 \times 11 + 2 \times 5 + 3 \times 7 + 4 \times 8 + 5 \times 1 + 6 \times 9 = 133$.

Al doilea exemplu descrie circuitele de pe pagina 1. La final, conținutul circuitului roșu este:
57 0 1 33 3 4 35 6 7 37 9 10 39 12 13 41 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30,
iar conținutul circuitului albastru este:
57 31 32 33 2 34 35 5 36 37 8 38 39 11 40 41 14 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56.