소 달리기

Farmer John과 Bessie가 소들을 위한 새로운 운동 게임을 고안했다. 소들은 길이가 $M$ ($2 \le M \le 10^9$)인 원형 트랙 위를 달리며, 모두 같은 위치에서 출발한다. 게임은 $N$ ($1 \le N \le 14$)개의 라운드로 진행되고, $8N$장의 카드 덱을 사용한다. 각 카드에는 숫자 $X_i$ ($0 \le X_i < M$)가 적혀 있다.

매 라운드 시작 시 Farmer John은 덱의 맨 위 $8$장을 따로 빼내어 그중 위 4장 또는 아래 4장을 고른다. 그다음 Bessie가 그 $4$장 중 위 2장 또는 아래 2장을 고른다. 그러면 위 카드 $X_{top}$과 아래 카드 $X_{bottom}$이 순서대로 남는다.

먼저 Farmer John이 $X_{top}$을 외치면 소들은 $R \cdot X_{top}$만큼 달린다. 여기서 $R$은 지금까지 소들이 달린 총 거리이다. 이어서 Bessie가 $X_{bottom}$을 외치면 소들은 추가로 $X_{bottom}$만큼 달린다. 트랙이 원형이므로 위치는 $M$으로 나눈 나머지만 의미가 있다.

Farmer John은 소들이 출발점에서 너무 멀어지면 지쳐서 집으로 돌아오지 못할까 걱정한다. 그는 마지막에 소들이 출발 위치로부터 (원을 따라 잰 더 짧은 호의 거리로) 최대 $K$ ($0 \le K \le \lfloor M/2 \rfloor$)만큼 떨어져 있어야만 집에 돌아올 수 있다고 본다.

Farmer John이 올바르게만 플레이하면 Bessie가 어떻게 하든 항상 소들을 집으로 데려올 수 있음이 보장된다. 각 라운드마다, Bessie의 현재와 이후 선택이 무엇이든 소들이 여전히 출발점에서 거리 $K$ 이내로 끝낼 수 있도록 Farmer John이 어느 쪽 절반을 골라야 하는지 정하라. 그러면 Bessie는 입력에 주어진 대로 움직이고 다음 라운드로 넘어간다. Bessie의 움직임이 입력으로 주어지더라도 Farmer John의 선택은 Bessie가 무엇을 하든 통하는 선택이어야 한다 (즉, Farmer John은 Bessie의 선택을 미리 알지 못하는 것처럼 행동해야 한다).

• 첫째 줄: 공백으로 구분된 세 정수 $N$, $M$, $K$.
• 둘째 줄: 길이 $N$의 문자열. $i$번째 문자가 T이면 Bessie가 $i$번째 라운드에서 위 $2$장을 고르고, B이면 아래 $2$장을 고른다.
• 셋째 줄부터 $N+2$번째 줄까지: $i+2$번째 줄에는 $i$번째 라운드에 사용하는 $8$장의 카드가 위에서 아래 순서로 정수 여덟 개로 주어진다.

• 첫째 줄: 길이 $N$의 문자열. $i$번째 문자는 Farmer John이 $i$번째 라운드에서 위 $4$장을 골라야 하면 T, 아래 $4$장을 골라야 하면 B이다. 소들을 집으로 데려오는 선택 방법이 여러 가지라면 사전순으로 가장 앞선 (즉 알파벳순으로 가장 작은, B가 T보다 앞선) 문자열을 출력하라.

참고

소들은 출발 위치로부터 거리 $K$ 이내로 끝나야만 집에 돌아올 수 있다. 예제에서는 $K = 0$이므로 정확히 출발한 자리에서 끝나야 한다. Farmer John은 Bessie의 선택을 미리 알지 못한다는 점에 유의하라. 만약 미리 알았다면 매 라운드 아래쪽 절반을 고르면 되었을 것이다.