Bạn sắp tổ chức một buổi trình diễn ba phong cách thời trang trên sân khấu dạng lưới \(N\times N\). Mỗi ô hoặc trống (ký hiệu .), hoặc chứa một người mẫu loại +, x hay loại siêu thời thượng o. Mỗi + hoặc x cho 1 điểm phong cách, mỗi o cho 2 điểm, ô trống không cho điểm.

Để đạt hiệu quả nghệ thuật tối đa, cách đặt phải tuân theo:

• Nếu hai người mẫu cùng hàng hoặc cùng cột, ít nhất một người phải là +.
• Nếu hai người mẫu cùng một đường chéo, ít nhất một người phải là x.

Một cách chính xác, hai ô \((i_0,j_0)\) và \((i_1,j_1)\) cùng hàng khi \(i_0=i_1\), cùng cột khi \(j_0=j_1\), và cùng đường chéo khi \(i_0+j_0=i_1+j_1\) hoặc \(i_0-j_0=i_1-j_1\).

Ví dụ, lưới sau không hợp lệ:

...
x+o
.+.

Ở hàng giữa, cặp x và o không có ai là +. Trên đường chéo từ + ở hàng cuối tới o ở hàng giữa cũng có hai người mà không ai là x.

Ngược lại, lưới sau hợp lệ vì không hàng, cột hay đường chéo nào vi phạm:

+.x
+x+
o..

Cố vấn đã đặt trước \(M\) người mẫu theo đúng quy tắc. Bạn có thể thêm tùy ý (kể cả không thêm) bất kỳ loại nào. Không được bỏ người mẫu có sẵn, nhưng có thể nâng cấp bao nhiêu + hoặc x thành o tùy ý, miễn vẫn hợp lệ. Hãy tìm một cách đặt/thay thế hợp lệ có tổng điểm phong cách lớn nhất.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test bắt đầu bằng \(N,M\), sau đó là \(M\) dòng; dòng thứ \(i\) chứa loại +, x hoặc o và hai số \(R_i,C_i\). Hàng được đánh số từ 1 đến \(N\) từ trên xuống, cột từ 1 đến \(N\) từ trái sang phải.

Dữ liệu ra

Với mỗi test, trước tiên in Case #x: y z, trong đó x là số thứ tự test bắt đầu từ 1, y là tổng điểm của cách bố trí và z là tổng số người mẫu đã thêm hoặc thay thế. Sau đó in đúng \(z\) dòng theo định dạng input, ghi loại cuối cùng và vị trí của từng người mẫu được thêm/thay; các dòng có thể theo thứ tự bất kỳ.

Nếu có nhiều đáp án hợp lệ, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le C_i\le N\).
• \(0\le M\le N^2\).
• Không có hai người mẫu đặt sẵn trong cùng ô.
• Cách đặt ban đầu được bảo đảm hợp lệ.

Phân nhóm

• Test Set 1 (Visible): \(R_i=1\) với mọi \(i\); mọi người mẫu đặt sẵn đều ở hàng trên cùng, nhưng vẫn có thể thêm/thay trong hàng này hoặc thêm ở hàng khác.
• Test Set 2 (Hidden): \(1\le R_i\le N\); không có hạn chế thêm về hàng.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 0
1 1
o 1 1
3 4

+ 2 3
+ 2 1
x 3 1
+ 2 2

Case #1: 4 3
o 2 2
+ 2 1
x 1 1
Case #2: 2 0
Case #3: 6 2
o 2 3
x 1 2

x.
+o

...
+++
x..

.x.
++o
x..

Nguồn

Google Code Jam 2017, Vòng loại, bài Fashion Show.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.