Polyomino

Time limit2sMemory limit128 MB

Summary

Cover every run of X cells with 2-cell (BB) and 4-cell (AAAA) blocks and print the lexicographically smallest resulting board, or -1 if some run has odd length.

Level: Medium4 of 10
Topics: Greedy, String, Math, Implementation
Solved: No attempts yet

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.

Examples5

Example 1
Input
```
XXXXXX
```
Expected output
```
AAAABB
```
Example 2
Input
```
XX.XX
```
Expected output
```
BB.BB
```
Example 3
Input
```
XXXX....XXX.....XX
```
Expected output
```
-1
```
Example 4
Input
```
X
```
Expected output
```
-1
```

Example 5

Input

XX.XXXXXXXXXX..XXXXXXXX...XXXXXX

Expected output

BB.AAAAAAAABB..AAAAAAAA...AAAABB