题目描述

给定一个字符串，用于创建两个平行数组。从左到右处理字符串中的字母，按字母表顺序将字母依次插入第一个数组，每次一个字母。在此过程中，在第二个数组中为每个字母分配一个整数值，规则如下：

1. 第一个字母的数值是 $0$。
2. 如果新插入的字母是数组中的第一个或最后一个，则它的数值比相邻字母的数值大 $1$。
3. 否则，它比两个相邻值中的较大值大 $1$。如果这个字母已经在数组中，则将新插入的字母放在现有字母之前。

创建两个数组后，打印输出由一个空格分隔的两个不同字符串。开始的字母添加到字符串中。

要创建第一个字符串，请以数值为 $0$ 的字母为起点：

1. 搜索这个字母的左侧，找到具有下一个连续数值的字母。如果存在，将其添加到字符串中。
2. 如果没有更多符合条件的字母或找到一个数值较低的字母，则停止递归。
3. 搜索当前字母的右侧，查找具有下一个连续数值的字母。如果存在，将其添加到字符串中。

对在数值为 $0$ 的字母的左侧搜索到的每个字母，递归执行步骤1-3。
在数值为 $0$ 的字母右侧找到数值为 $1$ 的字母。
对在数值为 $0$ 的字母的右侧搜索到的每个字母，递归执行步骤 1-3。

要创建第二个字符串，按照与上面相同的连续顺序查找字母，先搜索左侧，然后搜索右侧。如果没有更多的字母或先搜索到一个数值较小的字母，说明无法找到任何字母，此时停止递归，并将这个字母添加到字符串中。然后返回前一个字母，继续执行递归。

Input

输入一个字符串用于创建 $2$ 个数组，这个字符串的所有字母为大写字母，且不超过 $80$ 个字母。

Output

输出一个字符串表示第一个字符串和第二个字符串，中间用一个空格隔开。

Samples

PYTHONN

PHONNYT NNOHTYP

BINARYSEARCHTREE

BAAIECEEHNRRRYST AAEECHERRTSYRNIB

样例解释

对于样例2，字符串BINARYSEARCHTREE可以得到以下数组 按如下方式访问两个字符串的字母：在数值为 $0$ 的 $B$ 的左侧，找到数值为 $1$ 的 $A$，然后找到 数值为 $2$ 的 $A$ 并停止。在数值为 $0$ 的 $B$ 的右侧，找到数值为 $1$ 的 $I$，然后找到左侧数值为 $2$ 的 $E$，然后在左侧找到数值为 $3$ 的 $C$，然后在右侧找到数值为 $4$ 的 $E$，然后发现左侧数值为 $5$ 的 $E$，然后数值为 $3$ 的 $H$ 位于数值为 $2$ 的 $E$ 的右侧，因为对于数值为 $2$ 的 $E$ 的左侧已完成 了所有搜索，现在搜索它的右侧。在数值为 1 的 I 的右侧继续搜索。 这组数组的输出为 BAAIECEEHNRRRYST AAEECHERRTSYRNIB