Bạn được cho một lưới \(n\times m\), trong đó mỗi ô chứa một ký tự A, B, C hoặc D.

Với mỗi ô, bạn phải đổi ký tự của ô đó thành A, B, C hoặc D. Ký tự mới phải khác ký tự ban đầu.

Nhiệm vụ của bạn là đổi ký tự ở mọi ô sao cho không có hai ô kề nhau nào có cùng ký tự.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số hàng và số cột.

\(n\) dòng tiếp theo, mỗi dòng chứa \(m\) ký tự: mô tả lưới.

Output

In \(n\) dòng, mỗi dòng gồm \(m\) ký tự: mô tả lưới cuối cùng.

Bạn có thể in bất kỳ lời giải hợp lệ nào.

Nếu không tồn tại lời giải, chỉ in IMPOSSIBLE.

Constraints

• \(1 \le n, m \le 500\)

Example

3 4
AAAA
BBBB
CCDD

CDCD
DCDC
ABAB