Cows' Circular Track Exercise

Farmer John and Bessie have devised a new exercise game for the cows. The cows run on a circular track of length \(M\) (\(2 \le M \le 10^9\)) starting from the same position. The game proceeds in \(N\) rounds (\(1 \le N \le 14\)) using a deck of \(8N\) cards each with a number \(X_i\) (\(0 \le X_i < M\)) written on it.

In each round the following occurs:

1. FJ removes the top 8 cards from the deck forming a round pile.
2. FJ then chooses either the top 4 cards or the bottom 4 cards from the pile to offer to Bessie.
3. Bessie then chooses either the top 2 cards or the bottom 2 cards of the 4 cards offered.
4. FJ calls out the number on the top card of Bessie’s chosen pair, \(X_{top}\), and the cows run a distance of \(R \times X_{top}\), where \(R\) is the total distance the cows have run so far.
5. Bessie calls out the number on the bottom card, \(X_{bottom}\), and the cows run an additional distance of \(X_{bottom}\).

The cows’ position on the track is determined modulo \(M\). FJ is worried that if the cows end up more than a distance of \(K\) (with \(0 \le K \le \lfloor M/2 \rfloor\)) from the starting position, they will not be able to get back home. FJ wants to guarantee that, regardless of Bessie’s choice between top and bottom pairs, the cows’ new position after each round will have a circular distance (i.e. \(\min(\text{pos}, M-\text{pos})\)) of at most \(K\) from the starting point.

It is guaranteed that if FJ plays optimally he will always be able to ensure the cows come home. For each round, your task is to determine which half (either top 4 or bottom 4) FJ should choose so that regardless of Bessie’s later selection, the outcome is safe. Although Bessie’s moves are provided in the input, FJ’s decision must work under either choice.

The rounds are played sequentially. Let \(\text{pos}\) be the current position (initially 0) and \(R\) be the total distance run so far (initially 0). In a round, if FJ offers a block of 4 cards with order \([a, b, c, d]\):

• If Bessie chooses the top pair then the cows run a distance of \(R \times a + b\) and the new position becomes \((\text{pos} + R \times a + b) \bmod M\).
• If Bessie chooses the bottom pair then the cows run a distance of \(R \times c + d\) and the new position becomes \((\text{pos} + R \times c + d) \bmod M\).

Your program should simulate the rounds using the provided deck and Bessie’s moves, output FJ’s move (either TOP or BOTTOM for each round), and update the state accordingly.

inputFormat

The input consists of the following parts:

1. The first line contains three integers \(M\), \(N\), and \(K\).
2. The second line contains \(8N\) space-separated integers representing the card values in the deck in the order they appear.
3. The third line contains a string of \(N\) characters (each either T or B) representing Bessie's moves for each round. T indicates the top pair is chosen and B indicates the bottom pair is chosen by Bessie.

outputFormat

For each round, output a line containing FJ's move: either TOP if FJ selects the top 4 cards, or BOTTOM if he selects the bottom 4 cards. These moves must guarantee that, regardless of Bessie's subsequent choice, the resulting position after the round (calculated as described) is at most a circular distance of \(K\) from the starting point.

sample

10 1 5
0 1 2 3 4 5 6 7
T

TOP