35367번 - Snakey String 다국어

A snakey string is a fancy rendering of an otherwise normal string of text. When a string is made snakey, it is placed on a 2D grid such that the following conditions are met:

• The first character of the string is on the first column of the grid, the second on the second column, …, and the last on the last column.
• Each character in the string occupies either the row directly above or directly below the row of the previous character.

Figure 1: The snakey string in the sample case.

Given a snakey string, can you recover the original string?

The first line of input contains two integers $r$ and $c$ ($2 \le r, c \le 100$), the number of rows and columns of the grid.

The next $r$ lines each contain $c$ characters that form the 2D grid containing the snakey string. Empty cells are encoded with a period, while uppercase letters (A-Z) represent characters in the original string. Every column in the grid contains exactly one uppercase letter. It is possible that some rows do not contain any uppercase letters.

Output a single string, the original string that was used to build this snakey string.