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

Với mỗi ô, bạn phải đổi ký tự thành A, B hoặc C. Ký tự mới phải khác ký tự cũ.

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

Dữ liệu vào

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.

Dữ liệu ra

In ra \(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 ra 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
CCBB
ABCA

BCBC
ABCA
CABC