John y Bessie inventan ejercicio. Mismo inicio en pista circular $M$ ($2\le M\le1,000,000,000$), $N$ rondas ($1\le N\le14$), $8N$ cartas $X_i$ ($0\le X_i<M$).

Cada ronda primeras $8$ aparte, FJ elige $4$ arriba o abajo, Bessie de esas $2$ arriba o abajo. FJ lee superior $X_{top}$, corren $R*X_{top}$, $R$ total ya corrido; Bessie inferior $X_{bottom}$, corren $X_{bottom}$.

Teme cansancio y acabar lejos. Más de $K$ del inicio ($0\le K\le\lfloor M/2\rfloor$), no vuelven.

Juego correcto FJ garantiza regreso sin importar Bessie. Cada ronda mitad que asegure éxito ante cualquier elección futura. Ella juega según entrada, sigue ronda. Aunque dadas elecciones, FJ debe funcionar contra todas, como sin conocer futuro.

Entrada

• Línea 1: enteros $N,M,K$ separados por espacios.
• Línea 2: $N$ caracteres, $i$-ésimo T Bessie toma $2$ arriba en ronda $i$, si no B $2$ abajo.
• Líneas $3..2+N$: ocho enteros, cartas de arriba abajo.

Salida

• Línea 1: $N$ caracteres, $i$-ésimo T FJ $4$ arriba, B $4$ abajo. Varias maneras: lexicográficamente primera, menor alfabéticamente.

Ejemplos

Entrada 1

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

Salida 1

TB

Nota

Deben acabar exactamente en inicio. FJ no sabe sus elecciones antes ; sabiendo, podría mitad inferior cada ronda.

Créditos: Mark Gordon, 2011