Cow Run

Farmer John and Bessie have invented a new exercise game for the cows. The cows run on a circular track of length $M$ ($2 \le M \le 10^9$), and they all start from the same position. The game is played over $N$ ($1 \le N \le 14$) rounds using a deck of $8N$ cards; each card shows a number $X_i$ ($0 \le X_i < M$).

At the start of each round Farmer John takes the top $8$ cards as a separate pile and keeps either the top 4 or the bottom 4 of them. Bessie then keeps either the top 2 or the bottom 2 of those $4$ cards. This leaves an ordered pair: a top card $X_{top}$ and a bottom card $X_{bottom}$.

Farmer John first announces $X_{top}$, and the cows run a distance of $R \cdot X_{top}$, where $R$ is the total distance the cows have run so far. Bessie then announces $X_{bottom}$, and the cows run an additional distance of $X_{bottom}$. Because the track is circular, only the position taken modulo $M$ matters.

Farmer John worries the cows will be too tired to get home if they finish too far from the start. He decides they can get home only if their final distance from the starting position (measured as the shorter arc around the circle) is at most $K$ ($0 \le K \le \lfloor M/2 \rfloor$).

It is guaranteed that, by playing correctly, Farmer John can always bring the cows home no matter what Bessie does. For each round you must decide which half Farmer John should keep so that, regardless of Bessie's current and future choices, the cows can still finish within distance $K$ of the start. Bessie then makes the move given in the input and you continue to the next round. Even though Bessie's moves are given to you, the moves you pick for Farmer John must work no matter what Bessie does (as if Farmer John does not know Bessie's choices in advance).

• Line $1$: Three space-separated integers $N$, $M$, $K$.
• Line $2$: A string of $N$ characters. If the $i$-th character is T, Bessie keeps the top $2$ cards in round $i$; if it is B, she keeps the bottom $2$ cards.
• Lines $3 \ldots N+2$: Line $i+2$ contains eight integers — the $8$ cards used in round $i$, listed from top to bottom.

• Line $1$: A string of $N$ characters. The $i$-th character is T if Farmer John should keep the top $4$ cards in round $i$, or B if he should keep the bottom $4$ cards. If several sequences of choices bring the cows home, output the lexicographically smallest one (the alphabetically smallest string, where B precedes T).

Notes

The cows can return home only if they finish within distance $K$ of the starting position; in the sample $K = 0$, so they must finish exactly where they started. Note that Farmer John does not know Bessie's choices in advance — if he did, he could simply keep the bottom half every round.