Lát Domino Tối Đa

Cho một bảng gồm $H$ hàng và $W$ cột. Mỗi ô là một trong hai loại:

• .: ô trống, có thể được phủ;
• #: ô bị chặn, không được sử dụng.

Một quân domino phủ đúng hai ô trống có chung một cạnh. Hai quân domino không được phủ chung ô. Hãy đặt được nhiều quân domino nhất và in ra một cách đặt đạt số lượng đó.

Trong bảng kết quả, mỗi domino được biểu diễn bằng hai mũi tên hướng vào nhau:

• nếu domino nằm ngang, ô bên trái là > và ô bên phải là <;
• nếu domino nằm dọc, ô phía trên là $v$ và ô phía dưới là ^.

Những ô trống không được phủ vẫn là ., còn mọi ô bị chặn vẫn là #.

Input

• Dòng đầu chứa hai số nguyên $H$ và $W$.
• Mỗi dòng trong $H$ dòng tiếp theo chứa đúng $W$ ký tự, mô tả một hàng của bảng.

Output

• Dòng đầu in số nguyên $K$, là số domino lớn nhất có thể đặt.
• Trong $H$ dòng tiếp theo, in bảng kết quả theo quy ước mũi tên ở trên. Nếu có nhiều cách đặt tối ưu, bạn có thể in bất kỳ cách nào.

Constraints

• $1\le H,W\le 100$.
• Mỗi ký tự của bảng là . hoặc #.

Scoring

• Subtask $1$ ($50\%$ số điểm): $H,W\le 8$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

2 2
..
..

2
><
><