Arne Saknussemm

Time limit1sMemory limit128 MB

Summary

Reverse a described scrambling procedure that pads, reverses, and writes a message column by column into a table, given its row fragments, to recover the original text.

Level: Medium5 of 10
Topics: String, Simulation, Implementation
Solved: No attempts yet

Problem

Following the account of Jules Verne, a scrambled message written by the medieval alchemist Arne Saknussemm and deciphered by professor Lidenbrock started the incredible journey to the center of the Earth. The scrambling procedure used by Arne is similar to the one described below.

1. Take a non-empty message $M$ that contains letters of the English alphabet, digits, commas, dots, quotes (i.e. '), spaces, and line breaks, and whose last character is not a space. For example, consider the following message, whose translation reads "In Sneffels's crater descend brave traveler, and touch the center of the Earth".

In Sneffels craterem descende audas
viator, et terrestre centrum attinges.

2. Choose an integer $0 < K \le \operatorname{length}(M)$ and append trailing spaces to $M$ so that the length of the resulting message $M'$ is the least multiple of $K$ . For $K = 19$ and the message above, where $\operatorname{length}(M) = 74$ (including the 8 spaces and the line break that $M$ contains), two trailing spaces are added, yielding $M'$ with $\operatorname{length}(M') = 76$ .

3. Replace every space in $M'$ by the character _ (underscore), replace every line break in $M'$ by \ (backslash), and then reverse the message. In our case:

__.segnitta_murtnec_ertserret_te_,rotaiv\sadua_ednecsed_meretarc_sleffenS_nI

4. Write the message produced in step 3 into a table with $\operatorname{length}(M') / K$ rows and $K$ columns. The writing is done column by column. For the example, the message is written into a table with $76 / 19 = 4$ rows and $19$ columns as follows:


_	e	t	m	n	e	e	t	_	t	\	u	d	s	m	t	_	f	S
_	g	t	u	e	r	r	_	,	a	s	a	n	e	e	a	s	f	_
.	n	a	r	c	t	r	t	r	i	a	_	e	d	r	r	l	e	n
s	i	_	t	_	s	e	e	o	v	d	e	c	_	e	c	e	n	I

5. The strings of characters corresponding to the rows of the table are the fragments of the scrambled message. The 4 fragments of Arne's message from step 1 are:

_etmneet_t\udsmt_fS _gtuerr_,asaneeasf_
.narctrtria_edrrlen si_t_seeovdec_ecenI

Write a program that deciphers non-empty messages scrambled as described. The length of a message, before scrambling, is at most $1000$ characters, including spaces and line breaks.

Input

The program input is read from a text file in which each data set corresponds to one scrambled message. A data set starts with an integer $n$ , the number of fragments of the scrambled message, and continues with $n$ strings of characters denoting the fragments, in the order in which they appear in the table from step 4 of the scrambling procedure. The input data are separated by whitespace and terminate at end of file.

Output

The deciphered message must be printed to standard output, starting at the beginning of a line, and must be followed by an empty line, as shown in the input/output sample below.

Examples3

Example 1

Input

4  _etmneet_t\udsmt_fS
   _gtuerr_,asaneeasf_
   .narctrtria_edrrlen
   si_t_seeovdec_ecenI
11 e n r e V _ s e l u J

Expected output

In Sneffels craterem descende audas
viator, et terrestre centrum attinges.

Jules Verne

Example 2
Input
```
3
_do,l
_lWoe
.r_lH
```
Expected output
```
Hello, World.
```
Example 3
Input
```
11
e
n
r
e
V
_
s
e
l
u
J
```
Expected output
```
Jules Verne
```


_	e	t	m	n	e	e	t	_	t	\	u	d	s	m	t	_	f	S
_	g	t	u	e	r	r	_	,	a	s	a	n	e	e	a	s	f	_
.	n	a	r	c	t	r	t	r	i	a	_	e	d	r	r	l	e	n
s	i	_	t	_	s	e	e	o	v	d	e	c	_	e	c	e	n	I


_	e	t	m	n	e	e	t	_	t	\	u	d	s	m	t	_	f	S
_	g	t	u	e	r	r	_	,	a	s	a	n	e	e	a	s	f	_
.	n	a	r	c	t	r	t	r	i	a	_	e	d	r	r	l	e	n
s	i	_	t	_	s	e	e	o	v	d	e	c	_	e	c	e	n	I


_	e	t	m	n	e	e	t	_	t	\	u	d	s	m	t	_	f	S
_	g	t	u	e	r	r	_	,	a	s	a	n	e	e	a	s	f	_
.	n	a	r	c	t	r	t	r	i	a	_	e	d	r	r	l	e	n
s	i	_	t	_	s	e	e	o	v	d	e	c	_	e	c	e	n	I