题目描述

给定一段横向排版的文本，请将它转换为纵向排版，不足的位置用 * 填充。

具体来说，给定 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \dots, S_N$。

设 $M$ 为这些字符串中的最大长度（即 $\max(|S_i|)$）。

请输出 $M$ 个字符串 $T_1, T_2, \dots, T_M$，使其满足以下条件：

• 每个 $T_i$ 仅由小写英文字母和 * 组成。
• 每个 $T_i$ 不能以 * 结尾。
• 对于每个 $1 \le i \le N$，满足：
  • 对于每个 $1 \le j \le |S_i|$，$T_j$ 的第 $(N-i+1)$ 个字符一定存在，且将 $T_1, T_2, \dots, T_{|S_i|}$ 的第 $(N-i+1)$ 个字符按顺序拼接起来，恰好等于 $S_i$。
  • 对于每个 $|S_i| + 1 \le j \le M$，$T_j$ 的第 $(N-i+1)$ 个字符要么不存在，要么是 *。

其中 $|S_i|$ 表示字符串 $S_i$ 的长度。

输入格式

第一行包含一个正整数 $N$。

接下来 $N$ 行，每行包含一个字符串 $S_i$。

输出格式

输出 $M$ 行，第 $i$ 行输出一个字符串 $T_i$。

样例输入 1

3
abc
de
fghi

样例输出 1

fda
geb
h*c
i

样例输入 2

3
atcoder
beginner
contest

样例输出 2

cba
oet
ngc
tio
end
sne
ter
*r

说明

样例解释

在第一个样例中，

将 $T_3$ 的第 $2$ 个字符设为 *，可以使 $T_3$ 的第 $3$ 个字符 c 对齐到正确的位置。

另一方面，对于第 $4$ 行，如果我们将 $T_4$ 的第 $2$ 个和第 $3$ 个字符都填上 *，会导致 $T_4$ 以 * 结尾（变成 i**），这违背了题目中“字符串不能以 * 结尾”的条件，因此应当省略后面的 *，直接输出 i。

数据范围

• 对于所有测试点，保证 $1 \le N \le 100$。
• 保证每个 $S_i$ 均由小写英文字母组成，且长度满足 $1 \le |S_i| \le 100$。
• 保证所有的输入数值均为整数。