2093 - 书写转置
Description

> 给你一个横向书写的文本。将其转换为竖写,用 `*` 填充空格。

给你 N 个由小写英文字母组成的字符串 S_1, S_2, \dots, S_N 。设 M 为这些字符串的最大长度。

打印满足以下条件的 M 个字符串 T_1, T_2, \dots, T_M

- 每个 T_i 由小写英文字母和 `*` 组成。

- 每个 T_i 不以 `*` 结尾。

- 对于每个 1 \leq i \leq N ,以下条件成立:

    - 对于每个 1 \leq j \leq |S_i|T_j(N-i+1) 个字符存在, T_1, T_2, \dots, T_{|S_i|}(N-i+1) 个字符按此顺序连接等于 S_i

    - 对于每个 |S_i| + 1 \leq j \leq MT_j(N-i+1) -th 字符要么不存在,要么是 `*`。

这里, |S_i| 表示字符串 S_i 的长度。


Input

第一行一个数字N表示有几行文字

接下来N行文字

Output

文本转成竖行后输出,如果前面有多余的空格,记得用"*"填充

Examples

Input

3
abc
de
fghi

Output

fda
geb
h*c
i

Input

3
chouzhou
beginner
contest

Output

cbc
oeh
ngo
tiu
enz
snh
teo
*ru
Hint

样例1说明:

将 `*` 作为 T_3 的第 2 个字符,使 `c` 位于正确的位置。另一方面,将 `*` 放在 T_4 的第 2 和第 3 个字符,会使 T_4 以 `*` 结尾,这违反了条件。

数据范围:

- N 是介于 1100 之间的整数,包括首尾两个整数。

- 每个 S_i 都是长度介于 1100 之间的小写英文字母字符串。


题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 17
通过次数 9