SHANGUL - Simplified Hangul

no tags 

Bob is an American boy and a huge fan of K-Pop ("Korean-Popular"), a popular music genre in South Korea. The songs are usually performed by boybands and girlbands, and they usually dance pre-determined choreographies and sing pre-determined lyrics.

Bob already learned some choreographies, but he can't understand the lyrics very well. That's why he is studying the Korean language, in particular the Korean alphabet, Hangul. Bob has some images containing lyrics written in Korean, and needs to know how these texts would sound for an English speaker. Help him by creating a program that reads a image containing Korean text and outputs how it sounds.

In this problem, we'll consider a very simplified version of Hangul. There are only 7 letters in this alphabet. Their drawing and sounds are given below:

 

To form a word, the letters are written in sequence, from left to right. The word's sound is the concatenation of its letters' sound, in order. So, according to the given table, the word    , for instance, sounds like "gangnan".

It's also possible to replace a letter in a word by two letters, one on the top of another, forming a block. The sound of a block is the concatenation of the sound of the top letter and the bottom letter. So, for instance, the block  sounds like "ua", and the word  sounds like "uaneoi".

You are given a matrix that represents a black-and-white image containing a single word. The white pixels represent the background of the image, while the black ones indicate the word itself. Find out how the word would sound like.

(PS: The problem setter is not a Korean speaker. Sorry for possible mistakes.)

Input

The first line of each test case contains two integers n and m (5 ≤ n ≤ 40, 7 ≤ m ≤ 520), the number of rows and columns of the image. The next n lines contain m characters each, and represent the image. The character '.' indicates a white pixel, while the character '#' represents a black pixel.

Restrictions:

  • The first and last rows and columns of the image will always be blank;
  • There will be at least one letter in the image;
  • All letters in the image will be valid;
  • The length of each stroke may vary, but its width will always be 1 pixel;
  • The length of all vertical strokes in "a" and "eo" will always be odd, and the horizontal stroke will always intersect the vertical one on its midpoint;
  • The length of all horizontal strokes in "o" and "u" will always be odd, and the vertical stroke will always intersect the horizontal one on its midpoint;
  • The sequence of letters/blocks that form the word will be separated by at least one blank column;
  • There won't be any letter bellow another letter, except when a block is formed. This indicates that the word was written without linebreaks;
  • In a block, the bottom edge of the top letter and the top edge of the bottom letter will be separated by white pixels;
  • In a block, the leftmost pixel of both letters will be in the same column;
  • The letters/blocks that form the word may not be horizontally aligned;
  • The blocks and words may not make sense in (real) Korean.

The last test case is followed by a single line containing two zeros.

Output

For each test case, print a string indicating how the given word sounds.

Example

Input:
5 29
.............................
.###.#..#...###.#....#...#...
...#.##.#.....#.#....##..#...
...#.#..###...#.###..#...###.
.............................
19 38
......................................
..#...................................
..#...................................
..#................#..................
..###########......#..................
..#................#..................
..#................#..................
..#................#..................
...................#..................
...................#..................
..#................#..................
..#...................................
..#......................#............
..#......................#............
..#......................#............
..####...................#............
.........................#............
...................#############......
......................................
16 34
..................................
................................#.
....#######.....................#.
.......#........................#.
.......#...............##########.
.......#........................#.
.......#........................#.
.......#........................#.
.......#..........................
..................................
....#...........#.................
....#...........#......#..........
....#####.......#......#..........
....#...........#####..#..........
....#..................#..........
..................................
0 0 Output:
gangnan
anio
uaneoi

hide comments
nadstratosfer: 2020-01-20 06:40:21

Pretty cool problem. Excellent, clear statement. Enjoyed myself here.

hodobox: 2017-05-05 16:32:34

In addition, the strokes which in Restrictions are mentioned to have an odd length, have length at least 3.

Mitch Schwartz: 2013-08-03 01:38:52

It was fun to write a solution without case analysis (easily generalisable to arbitrary shapes obeying a few constraints).


Added by:Ricardo Oliveira [UFPR]
Date:2013-08-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:UFPR Training Session