John và Bessie tạo trò tập. Chung đầu đường tròn dài $M$ ($2\le M\le1,000,000,000$), $N$ vòng ($1\le N\le14$), $8N$ thẻ $X_i$ ($0\le X_i<M$).

Mỗi vòng $8$ trên tách riêng, FJ chọn $4$ trên/dưới, Bessie trong đó $2$ trên/dưới. FJ gọi thẻ trên $X_{top}$, chạy $R*X_{top}$, $R$ tổng đã chạy; cô gọi dưới $X_{bottom}$, chạy $X_{bottom}$.

Sợ mệt xa. Hơn $K$ từ đầu ($0\le K\le\lfloor M/2\rfloor$) không về.

FJ chơi đúng bảo đảm về bất kể Bessie. Mỗi vòng nửa đảm bảo trước mọi lựa chọn tương lai. Cô theo nhập rồi vòng tiếp. Dù lựa chọn cho sẵn, FJ phải được với mọi lựa chọn, như không biết tương lai.

Dữ liệu vào

• Dòng 1: nguyên $N,M,K$ cách trắng.
• Dòng 2: $N$ ký tự, thứ $i$ T cô chọn $2$ trên vòng $i$, còn B $2$ dưới.
• Dòng $3..2+N$: tám nguyên, thẻ trên xuống dưới.

Dữ liệu ra

• Dòng 1: $N$ ký tự, thứ $i$ T FJ $4$ trên, B $4$ dưới. Nhiều cách chọn nhỏ nhất từ điển, nhỏ nhất theo chữ cái.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

TB

Ghi chú

Kết đúng đầu. FJ không biết lựa chọn trước; biết có thể dưới nửa mỗi vòng.

Ghi công: Mark Gordon, 2011