P3042 [USACO12JAN] Cow Run G

农夫 John 和 Bessie 为奶牛们设计了一种新的运动游戏。奶牛们从同一位置开始，在一个长度为 $M$ 的圆形跑道上奔跑，其中 $2 \leq M \leq 1,000,000,000$。游戏进行 $N$ 轮（$1 \leq N \leq 14$），使用一副 $8N$ 张的牌，每张牌上写有一个数字 $X_i$，其中 $0 \leq X_i < M$。 每一轮，FJ 将顶部的 8 张牌移到一个单独的牌堆中，并选择顶部 4 张或底部 4 张牌供 Bessie 使用。然后 Bessie 从 FJ 选择的 4 张牌中选择顶部 2 张或底部 2 张牌。之后，FJ 报出顶部牌上的数字 $X_{\text{top}}$，奶牛们跑 $R \times X_{\text{top}}$ 的距离，其中 $R$ 是奶牛们到目前为止跑过的总距离。接着 Bessie 报出底部牌上的数字 $X_{\text{bottom}}$，奶牛们再跑 $X_{\text{bottom}}$ 的距离。 FJ 担心在运动后，奶牛们会太累而无法回到跑道的起点，如果它们离起点的距离超过 $K$，它们就无法回家，其中 $0 \leq K \leq \lfloor \frac{M}{2} \rfloor$。 可以保证，如果 FJ 正确地进行游戏，他总能确保奶牛们能够回家，无论 Bessie 做出什么选择！对于每一轮，你的任务是确定 FJ 应该选择哪一半的牌，以便无论 Bessie **从那时起**做出什么选择，FJ 总能让奶牛们回家。Bessie 将根据输入提供的选择进行移动，然后你可以继续进行下一轮。注意，尽管 Bessie 的选择在输入中提供给你，但你需要为 FJ 指定无论 Bessie 选择什么都能奏效的策略（因此实际上 FJ 并不知道 Bessie 在她的回合中会做什么）。

\* 第 1 行：三个用空格分隔的整数 $N$、$M$、$K$。 \* 第 2 行：一个长度为 $N$ 的字符串。如果第 $i$ 个字符是 'T'，表示 Bessie 在第 $i$ 轮中选择顶部 2 张牌。否则，第 $i$ 个字符将是 'B'，表示 Bessie 选择底部 2 张牌。 \* 第 3 行到第 $2+N$ 行：每行包含 8 个整数，表示该轮从顶部到底部使用的 8 张牌。

\* 第 1 行：一个长度为 $N$ 的字符串，其中第 $i$ 个字符是 'T'，如果 FJ 应该在第 $i$ 轮中选择顶部 4 张牌；如果 FJ 应该选择底部 4 张牌，则为 'B'。如果有多种方法可以让奶牛们回家，选择字典序最小的（即字母顺序最小的字符串）。

奶牛们必须准确地回到起点才能回家。注意，FJ 事先不知道 Bessie 会做出什么选择。如果 FJ 知道，他每次都可以选择底部一半。 （由 ChatGPT 4o 翻译）