canuc80k0117·18/50

Vệt Sơn Cuối Cùng

Nộp bài trên LQDOJ

Bài 0.2 · Ad Hoc

Một bảng ban đầu toàn ô trống. Mỗi thao tác thuộc một trong hai loại:

  • chọn một hàng và tô cả tám ô thành ;
  • chọn một cột và tô cả tám ô thành .

Các thao tác diễn ra lần lượt; màu mới ghi đè màu cũ. Biết bảng cuối cùng và biết rằng dữ liệu hợp lệ, hãy xác định loại màu đã được dùng trong thao tác cuối.

Input

  • Dòng đầu chứa số nguyên .
  • Mỗi bộ test gồm đúng dòng, mỗi dòng có ký tự hoặc . mô tả bảng cuối cùng. Khoảng trắng trống giữa các test, nếu có, không ảnh hưởng.

Output

  • Với mỗi bộ test, in nếu vệt đỏ được tô cuối; ngược lại in .

Constraints

  • .
  • Bảng được bảo đảm có thể tạo từ bảng trống bằng cách tô toàn bộ một hàng thành hoặc toàn bộ một cột thành , theo một thứ tự nào đó.
  • Có ít nhất một vệt đã được tô.

Scoring

  • Subtask ( số điểm): .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2
.B....B.
.B....B.
.B....B.
RRRRRRRR
.B....B.
.B....B.
.B....B.
.B....B.
...B....
RRRBRRRR
...B....
...B....
...B....
...B....
...B....
RRRBRRRR

Output

R
B

Giải thích: Ở bảng đầu, hàng thứ tư được tô đỏ sau hai cột xanh nên còn nguyên một hàng . Ở bảng thứ hai, cột thứ tư được tô xanh sau hai hàng đỏ, nên thao tác cuối có màu .

Lời giải tóm tắt
  • Ý tưởng: Nếu thao tác cuối là tô đỏ, hàng được tô cuối không bị thao tác nào ghi đè nữa, nên chắc chắn xuất hiện một hàng gồm tám ký tự R. Nếu thao tác cuối là tô xanh, mọi hàng đỏ đã có trước đó bị cột xanh cuối ghi đè tại một ô, nên không hàng nào còn đủ tám R.
  • Ý tưởng: Vì dữ liệu luôn hợp lệ và có ít nhất một thao tác, chỉ cần tìm một hàng RRRRRRRR: có thì in R, không có thì in B. Mỗi test mất O(64) thời gian và O(1) bộ nhớ phụ.