Farmer John và Bessie đã nghĩ ra một trò vận động mới cho đàn bò. Đàn bò chạy trên một đường đua hình tròn có độ dài \(M\) (\(2 \le M \le 1\,000\,000\,000\)), xuất phát từ cùng một vị trí. Trò chơi diễn ra trong \(N\) vòng (\(1 \le N \le 14\)), sử dụng một bộ gồm \(8N\) lá bài, trên mỗi lá ghi một số \(X_i\) (\(0 \le X_i < M\)).

Trong mỗi vòng, FJ chuyển 8 lá trên cùng sang một chồng riêng và chọn 4 lá trên cùng hoặc 4 lá dưới cùng để Bessie chơi. Sau đó, Bessie chọn 2 lá trên cùng hoặc 2 lá dưới cùng trong 4 lá FJ đã chọn. Tiếp theo, FJ đọc số trên lá trên cùng, \(X_{\text{top}}\), và đàn bò chạy một quãng đường \(R \times X_{\text{top}}\), trong đó \(R\) là tổng quãng đường đàn bò đã chạy cho đến lúc đó. Sau đó Bessie đọc số trên lá dưới cùng, \(X_{\text{bottom}}\), và đàn bò chạy một quãng đường \(X_{\text{bottom}}\).

FJ lo rằng sau buổi tập, đàn bò sẽ quá mệt để quay lại điểm đầu đường đua nếu chúng kết thúc ở quá xa. Ông tin rằng nếu đàn bò kết thúc ở vị trí cách điểm xuất phát hơn \(K\) (\(0 \le K \le \lfloor M/2 \rfloor\)), chúng sẽ không thể trở về nhà.

Đề bài đảm bảo rằng nếu FJ chơi đúng, ông luôn có thể bảo đảm đàn bò về được nhà, bất kể Bessie đi nước nào! Ở mỗi vòng, nhiệm vụ của bạn là xác định FJ nên chọn nửa nào của các lá bài sao cho, dù từ thời điểm đó trở đi Bessie làm gì, FJ vẫn luôn có thể đưa đàn bò về nhà. Sau đó Bessie sẽ thực hiện nước đi được cho trong dữ liệu vào và bạn có thể tiếp tục sang vòng kế tiếp. Lưu ý rằng dù các nước đi của Bessie được cung cấp trong dữ liệu vào, bạn vẫn phải chỉ ra những nước đi cho FJ có thể thành công bất kể Bessie chọn gì (do đó, về bản chất, FJ thực sự không biết Bessie sẽ làm gì trong các lượt của cô).

Dữ liệu vào

• Dòng 1 chứa ba số nguyên \(N\), \(M\), \(K\), cách nhau bởi dấu cách.
• Dòng 2 chứa một chuỗi gồm \(N\) ký tự. Nếu ký tự thứ \(i\) là T, Bessie sẽ chọn 2 lá trên cùng ở vòng thứ \(i\). Ngược lại, ký tự thứ \(i\) là B, cho biết Bessie sẽ chọn 2 lá dưới cùng ở vòng thứ \(i\).
• Các dòng từ 3 đến \(2+N\): mỗi dòng chứa tám số nguyên biểu diễn 8 lá bài được dùng trong vòng đó, theo thứ tự từ trên xuống dưới.

Dữ liệu ra

In một chuỗi gồm \(N\) ký tự, trong đó ký tự thứ \(i\) là T nếu FJ nên chọn 4 lá trên cùng, hoặc là B nếu FJ nên chọn 4 lá dưới cùng ở vòng thứ \(i\). Nếu có nhiều cách đưa đàn bò về nhà, hãy chọn chuỗi nhỏ nhất theo thứ tự từ điển (tức là chuỗi đứng trước theo thứ tự bảng chữ cái).

Ví dụ

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

TB

Nguồn

USACO 2012 January Contest, Gold - Cow Run: https://usaco.org/index.php?page=viewproblem2&cpid=110

Tác giả: Mark Gordon, 2011.