English statement is here

Khi đọc về khả năng quay video của một chiếc máy ảnh, bạn có thể đã gặp các thông số kỹ thuật cho biết rằng máy ảnh hỗ trợ lấy mẫu màu 4:2:0 hoặc 4:2:2. Những con số này có liên quan đến định dạng nén dữ liệu làm file nhẹ hơn thường được viết dưới dạng sau: ~J:a:b~ (VD: 4:2:2)

• ~J~: cho ta biết bao nhiêu pixel mà ta làm việc (trong quá trình ăn bớt), giá trị này thường là 4, ở bài này ta không cần quan tâm.
• ~a~: cho ta biết có bao nhiêu pixel ở Hàng Trên mà ta giữ lại để sao chép.
• ~b~: cho ta biết có bao nhiêu pixel ở Hàng Dưới mà ta giữ lại để sao chép.

Dễ hiểu chúng ta có thể tham khảo bức ảnh này.

4:4:4 hình ảnh chưa nén hay còn gọi là định dạng RAW, chất lượng cao nhất,

4:2:2 hình ảnh đã nén bằng cách sao chép pixel bên trái, hàng trên chúng ta dùng ~2~ pixel và hàng dưới chúng ta dùng ~2~ pixel để sao chép cho các pixel còn lại, chất lượng bị giảm một nửa,

4:2:0 hình ảnh đã mã hóa bằng cách sao chép pixel bên trái trên (như hình minh họa), hàng trên chúng ta dùng ~2~ pixel và hàng dưới chúng ta dùng ~0~ pixel để sao chép cho các pixel còn lại, chất lượng thấp nhất.

Tèo là videographer cho Hội quỹ cộng đồng Vị, sau chuyến đi thành công Tèo bắt đầu kiểm tra video để edit. Tuy nhiên các file đã bị hỏng mất một số điểm màu do dùng thẻ nhớ rẻ tiền. May mắn thay Tèo đã quay video định dạng 4:4:4 nên có thể thay các điểm đã mất trở thành định dạng 4:2:2 hoặc 4:2:0. Hãy giúp Tèo làm một phần mềm thay đổi định dạng nhé. Tèo luôn muốn định dạng tốt nhất.

Lưu ý: một ô ~2 \cdot 2~ pixel không mất màu quá ~2~ pixel và pixel trái trên luôn có màu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương ~w, h~ ~(w \le 3840, h \le 2160;\ h \le w ; h , w\ \vdots \ 2)~ là số lượng pixel chiều ngang và dọc.
• ~h~ dòng tiếp theo, mỗi dòng nhập ~w~ kí tự R, G, B, ? tương ứng với đỏ, xanh lá, xanh dương và mất màu.

Dữ liệu ra

• Dòng đầu tiên xuất ra 4:2:2 hoặc 4:2:0 là định dạng nén tốt nhất mà Tèo có thể thay đổi thành được.
• ~h~ dòng tiếp theo, mỗi dòng xuất ~w~ kí tự R, G, B là kết quả của quá trình chuyển đổi

Ràng buộc

• Subtask 1 ~(50\%)~: ~w,h \le 100~
• Subtask 2 ~(50\%)~: Không có ràng buộc gì thêm.

• Ví dụ

Dữ liệu nhập vào

6 4
R?BBGR
RBB??G
GBRGGB
GR?GRG

Kết quả ra

4:2:2
RRBBGG
RRBBGG
GGRRGG
GGGGRR

Giải thích

• Ở những ? chúng ta có thể đoán được màu đã mất khi chuyển về 4:2:2

Dữ liệu nhập vào

6 4
R?BBGR
RBG??G
GBRGGB
GR??RG

Kết quả ra

4:2:0
RRBBGG
RRBBGG
GGRRGG
GGRRGG

Giải thích

• Ở những ? chúng ta có thể đoán được màu đã mất khi chuyển về 4:2:0, không đoán được ở ~2~ ? hàng cuối cùng nếu ở định dạng 4:2:2.