Piet

Piet is a programming language in which the code is a two-dimensional image of $N \times M$ pixels. The name comes from Piet Mondrian, the Dutch painter known for abstract work. The image below is a Piet program that prints "Hello, world!".

Each unit square in a Piet program is called a codel, and each codel is painted one color. A codel is the equivalent of a pixel in a bitmap image. A group of same-colored codels connected up, down, left, or right is a block, and a block is the smallest unit of execution. The first block to run is the block that contains the top-left codel. After that, the program repeats the process of moving to the next block according to the rules below.

Two values, the Direction Pointer (DP) and the Codel Chooser (CC), decide the next block. DP is one of left, right, up, or down. CC is either left or right. At the start, DP is right and CC is left. The next block is chosen as follows.

• Find the codels in the current block that are farthest in the DP direction. If the block is not convex, these codels may not be contiguous.
• Among those codels, choose the one that is farthest in the CC direction when facing DP. CC is relative to DP. For example, if DP is down and CC is right, the leftmost of those codels is chosen.
• The block that contains the codel touching the chosen codel in the DP direction is the next block.

The figure below shows an example of choosing the next block.

Each letter in a cell is a color value. The current block is A, DP (black arrow) points down, and CC (gray arrow) points right. The codels in A that are farthest in the DP direction are the bottom-most codels of A, marked with dots. Among them, the one farthest in the CC direction is marked with a border. The codel touching it from below (red star) belongs to block B, which becomes the next block.

A black block or the area outside the image cannot be entered. If the next block is black or outside the image, the program does the following.

1. If CC is left, change it to right. If CC is right, change it to left. Then try to move again.
2. If the move still fails, keep CC and rotate DP clockwise. Then try again.
3. If it still fails after rotating, return to step 1.
4. If all 8 cases have been tried and no block can be entered, the program ends.

The following example applies these rules. The current block is A, DP points up, and CC points left. The selected block is black, so CC is changed to right, which also selects a black block. DP is rotated clockwise to right, and CC is changed back to left, but the block touching the selected codel is outside the image. CC is changed to right, which also fails. DP is rotated again to down. The selected block is black, and when CC is changed to right, block B is selected and can be entered. So the next block is B. The steps are shown in the five images below.

Given a Piet program, print the color of each block the program passes through until it ends.

Note: In real Piet, some operations change DP or CC based on pixel colors. In this problem, DP and CC change only by the rules above.

The first line contains the natural numbers $N$ and $M$ ($1 \le N, M \le 100$).

The next $N$ lines each contain a string of $M$ letters. Each letter is an uppercase letter that represents the color of a codel, and X means black. The input never describes a program that does not end, and the top-left codel is guaranteed not to be black.

On the first line, print the colors of the blocks the program passes through, in order, until it ends.