Đây là bài chỉ nộp kết quả (output-only). Bạn cần nộp tệp kết quả cho từng tệp dữ liệu vào.

Người ngoài hành tinh đến từ hành tinh IOI dự định xây dựng một sân bay UFO tại công viên JOI ở Nhật Bản. Sự tồn tại của công viên này được giữ bí mật với người dân thông thường. Họ đã khảo sát công viên và lập bản đồ những nơi UFO có thể hạ cánh.

Công viên JOI là một hình chữ nhật rộng \(W\) mét theo hướng đông–tây và dài \(H\) mét theo hướng bắc–nam, được chia thành \(W\times H\) ô vuông cạnh \(1\) mét. Ô ở cột thứ \(x\) tính từ phía tây và hàng thứ \(y\) tính từ phía bắc được ký hiệu là \((x,y)\). Ô ở góc tây bắc là \((1,1)\), còn ô ở góc đông nam là \((W,H)\). Mỗi ô thuộc một trong hai loại: có thể hạ cánh, ký hiệu bằng ., hoặc không thể hạ cánh, ký hiệu bằng w.

UFO do người ngoài hành tinh IOI chế tạo nằm gọn trong một hình chữ nhật rộng \(B\) mét và sâu \(D\) mét. Theo thiết kế, khi UFO hạ cánh, các hướng trên, dưới, trái, phải trong bản thiết kế phải lần lượt tương ứng với các hướng bắc, nam, tây, đông; góc trên bên trái của bản thiết kế phải trùng với góc trên bên trái của một ô trong công viên.

Bản thiết kế UFO là một lưới gồm \(D\) hàng và \(B\) cột, tổng cộng \(B\times D\) ô. Ô ở cột thứ \(i\) từ trái sang và hàng thứ \(j\) từ trên xuống được ký hiệu là \((i,j)\). Ô trên cùng bên trái là \((1,1)\), ô dưới cùng bên phải là \((B,D)\). Ô \((i,j)\) cho biết liệu UFO có chiếm một phần của vùng vuông nằm cách mép phía tây của UFO từ \(i-1\) đến \(i\) mét và cách mép phía bắc từ \(j-1\) đến \(j\) mét hay không. Ô có chứa một phần UFO được ký hiệu bằng O (chữ O hoa); ô không chứa phần nào của UFO được ký hiệu bằng ..

Khi một UFO hạ cánh, mọi ô có ký hiệu O trong bản thiết kế phải nằm trên các ô có thể hạ cánh của công viên. Khi nhiều UFO cùng hạ cánh, không ô nào thuộc một UFO được chung cạnh với bất kỳ ô nào thuộc một UFO khác. Tuy nhiên, các UFO được phép tiếp xúc tại góc của các ô.

Bạn tình cờ được chọn làm đại sứ thiện chí của hành tinh IOI. Hãy lập phương án xây dựng sân bay có thể đón càng nhiều UFO hạ cánh càng tốt.

Yêu cầu

Lập phương án sân bay UFO trong công viên JOI. Phương án cho phép càng nhiều UFO hạ cánh thì điểm càng cao.

Phương án là bản đồ công viên JOI được bổ sung các UFO đã hạ cánh. Trong các ô có thể hạ cánh, dùng O (chữ O hoa) cho ô có chứa UFO và . cho ô không chứa UFO. Các ô không thể hạ cánh vẫn được biểu diễn bằng w.

Dữ liệu vào

Tải bộ dữ liệu vào, gồm năm tệp 01.in, 02.in, 03.in, 04.in, 05.in.

Mỗi tệp dữ liệu vào có định dạng sau:

• Dòng đầu chứa hai số nguyên \(B,D\), cách nhau bởi một dấu cách, lần lượt là chiều rộng và chiều sâu của UFO, tính bằng mét.
• \(D\) dòng tiếp theo mô tả bản thiết kế UFO. Dòng thứ \(j+1\) \((1\le j\le D)\) chứa một chuỗi gồm \(B\) ký tự. Ký tự thứ \(i\) \((1\le i\le B)\) là O hoặc ., biểu diễn ô \((i,j)\) của bản thiết kế.
• Dòng thứ \(D+2\) chứa hai số nguyên \(W,H\), cách nhau bởi một dấu cách, lần lượt là kích thước công viên theo hướng đông–tây và bắc–nam, tính bằng mét.
• \(H\) dòng tiếp theo mô tả bản đồ công viên. Dòng thứ \(y+D+2\) \((1\le y\le H)\) chứa một chuỗi gồm \(W\) ký tự. Ký tự thứ \(x\) \((1\le x\le W)\) là . hoặc w, biểu diễn ô \((x,y)\) của công viên.

Dữ liệu ra

Tệp kết quả gồm \(H\) dòng. Dòng thứ \(y\) \((1\le y\le H)\) chứa một chuỗi gồm \(W\) ký tự, mô tả hàng thứ \(y\) tính từ phía bắc của công viên. Ký tự thứ \(x\) \((1\le x\le W)\) trên dòng này là một trong ba ký tự O, ., w, biểu diễn trạng thái của ô \((x,y)\) trong phương án.

Cách nộp bài

Nộp kết quả tương ứng với từng tệp dữ liệu vào. Mỗi kết quả phải tuân thủ định dạng được quy định trong phần Dữ liệu ra.

Trong kỳ thi gốc, phản hồi khi nộp bài chỉ kiểm tra kết quả có đúng định dạng hay không. Việc phương án có hợp lệ và được bao nhiêu điểm được xác định theo phần Chấm điểm.

Ràng buộc

• \(1\le B\le5\).
• \(1\le D\le5\).
• \(1\le W\le200\).
• \(1\le H\le200\).

Chấm điểm

Bài có \(5\) tệp dữ liệu, mỗi tệp tối đa \(20\) điểm, tổng cộng \(100\) điểm. Mỗi tệp được gán một giá trị \(X\) như trong bảng dưới. Gọi \(Y\) là số UFO hạ cánh lớn nhất trong các phương án mà các thí sinh đã nộp cho tệp đó.

Nếu phương án của bạn không thỏa mãn các điều kiện của bài toán, bạn nhận \(0\) điểm cho tệp đó. Nếu phương án hợp lệ, gọi \(\alpha\) là số UFO có thể hạ cánh trong phương án của bạn. Điểm được tính như sau:

• Nếu \(\alpha\le X\), điểm là \(\frac{4\alpha}{X}\).
• Nếu \(X<\alpha\), điểm là \(4+16\times\left(\frac{\alpha-X}{Y-X}\right)^2\).

Trong cả hai trường hợp, làm tròn điểm đến một chữ số sau dấu phẩy: nếu chữ số thập phân thứ hai từ \(5\) trở lên thì làm tròn lên, nếu không thì làm tròn xuống.

Ví dụ

4 3
O..O
OOOO
.O..
20 10
....................
.w......w.......ww..
....ww......w.w.....
.w.....w............
...w......w.........
w................ww.
....w...............
.w.....w........w.ww
............w.......
....w..............w

..O..O......O..O....
.wOOOO.Ow.O.OOOOww..
...Oww.OOOO.wOw.O..O
.w.....wO..O..O.OOOO
.O.wO.O..OwOOOO..O..
wOOOO.OOOO..O...OwwO
..O.w..O..O..O..OOOO
Ow.O.O.wO.OOOO..wOww
OOOO.OOOO..Ow.......
.O..w.O............w