406696: GYM102501 E Pixels

E. Pixelstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output There are various ways to protect wildlife. One is to make posters that will inspire people, and that is the job of artists. Some of those people that need to be inspired are geeks, and that is why some artists focus on pixel art.

An artist prepared a pixel art drawing for depicting animals in black and white. These drawings should be displayed on a gigantic pixelated, rectangular screen, with $$$K$$$ rows (ordered from $$$0$$$ to $$$K - 1$$$, from top to bottom) and $$$L$$$ columns (ordered from $$$0$$$ to $$$L - 1$$$, from left to right): displaying drawings on such screens is your job.

When you initialize the screen, it displays only white pixels. Then, its pixels should be controlled individually by switches, and pressing the switch of a pixel $$$P$$$ ought to change the color of $$$P$$$, either from black to white or from white to black. However, the screen has a defect: pressing the switch of the pixel $$$P$$$ also changes the color of those pixels that have an edge in common with $$$P$$$, i.e., those pixels that are adjacent horizontally or vertically (but not diagonally). Yet, it might still be possible that, by adequately choosing which switches you press, even this defective screen can display the drawing you were handed.

Can you manage to display that drawing? If yes, which set of switches should you press?

Input

• Line 1 contains two integers $$$K$$$ and $$$L$$$, separated by spaces.
• For all $$$i$$$ such that $$$0 \le i < K$$$, line $$$i + 2$$$ contains $$$L$$$ symbols "B" or "W", separated by spaces: if the $$$j$$$-th symbol (with $$$0 \le j < L$$$) is a "B", then the pixel that will be displayed on row $$$i$$$ and column $$$j$$$ should be black; otherwise, it should be a white pixel.

Limits

• $$$1 \le K \times L \le 100 000$$$.

Output

If there is no way to display the desired drawing by pressing switches, your output should contain one line with the word "IMPOSSIBLE" and nothing else. Otherwise, your output should contain $$$K$$$ lines, each one containing $$$L$$$ symbols "A" or "P" and separated by spaces:

• For all $$$i$$$ and $$$j$$$ such that $$$0 \le i < K$$$ and $$$0 \le j < L$$$, if the $$$j$$$-th symbol on line $$$i + 1$$$ is a "P", then you should press the switch associated with the pixel on row $$$i$$$ and column $$$j$$$; otherwise, you should avoid that switch.

ExamplesInput

1 2
B W

Output

IMPOSSIBLE

Input

5 22
B B B W B W W W B W B B B W B B B B W B B B
B W W W B W W W B W B W W W B W W B W B W W
B B B W B W B W B W B B B W B B B B W B W W
W W B W B W B W B W B W W W B W B W W B W W
B B B W W B W B W W B B B W B W W B W B B B

Output

A P P A P P A A P A A P P P A A P A P A P A
A P P A P A P P A P A P A A A A A P P P A A
A P P A P P A A A P P A A P P A A P A P A A
A A A A A A P P A P P P A A P A A P P P P A
A P A A A A P A P P P A P A P P A P P P A P

Note

Note that the order in which switches are pressed is not important, and that it is never necessary to press twice the same switch. Thus, a solution can be fully described by the set of switches pressed. There might be several solutions, i.e., several adequate sets of switches. In that case, your output should just represent one such solution.

Sample Explanation 1

Whenever you press a switch, the colors of both pixels changes. Hence, they always have the same color, and the drawing cannot be displayed.

Sample Explanation 2 You can indeed check that, if you press the switches associated to the red pixels of the left picture, you will obtain the picture depicted on the right.