John i Bessie wymyślili ćwiczenie. Wspólny start na okręgu $M$ ($2\le M\le1,000,000,000$), $N$ rund ($1\le N\le14$), $8N$ kart $X_i$ ($0\le X_i<M$).

Runda górne $8$ osobno, FJ górne $4$ lub dolne $4$, Bessie z nich górne $2$ lub dolne $2$. FJ czyta górną $X_{top}$, bieg $R*X_{top}$, $R$ dotychczasowa łączna droga; Bessie dolną $X_{bottom}$, bieg $X_{bottom}$.

Boi się zmęczenia daleko. Ponad $K$ od startu ($0\le K\le\lfloor M/2\rfloor$) nie wrócą.

Poprawna gra FJ gwarantuje powrót niezależnie Bessie. Każda runda połowa zapewniająca sukces przeciw dowolnym przyszłym wyborom. Ona według wejścia, kolejna runda. Choć wybory dane, FJ musi działać dla każdego, jakby nie znał przyszłości.

Wejście

• Wiersz 1: całkowite $N,M,K$ spacjami.
• Wiersz 2: $N$ znaków, $i$-ty T Bessie górne $2$ w rundzie $i$, inaczej B dolne $2$.
• Wiersze $3..2+N$: osiem całkowitych, karty góra do dołu.

Wyjście

• Wiersz 1: $N$ znaków, $i$-ty T FJ górne $4$, B dolne $4$. Wiele możliwości: pierwszy leksykograficznie, najmniejszy alfabetycznie.

Przykład

Wejście 1

2 2 0
TT
1 0 0 0 0 0 0 1
0 1 1 1 0 0 1 0

Wyjście 1

TB

Uwagi

Koniec dokładnie start. FJ nie zna wyborów wcześniej, inaczej mógł brać dolną połowę zawsze.

Autorstwo: Mark Gordon, 2011