cho.sh
Notes
Loading...

Polyomino

Time limit

2s

Memory limit

128 MB

Problem

There are infinitely many polyominoes of the forms AAAA and BB.

You are given a board made of . and X. Cover every X with non-overlapping polyominoes. A . cell must not be covered by a polyomino.

Print the board after covering it according to these rules.

Input

The first line contains the board. The length of the board is at most 50.

Output

Print the lexicographically smallest valid covered board on the first line. If it is impossible to cover every X, print -1.