题目描述

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

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

创建两个数组后，打印输出两个不同的字符串，用一个空格隔开。对于数组中从左到右的每个字母：

• 查看它的左侧，是否有一个字母的值比它大 $1$。如果遇到任何小于它的值，请停止。如果一个字母满足上述条件，请将它添加到第一个字符串中。
• 查看它的右侧，是否有一个字母的值比它大 $1$。如果遇到任何小于它的值，请停止。如果一个字母满足上述条件，请将它添加到第二个字符串中。
• 如果一个字母同时符合两个字符串的条件，则不要添加这个字母。

如果任一字符串为空，则打印输出 NONE。

Input

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

Output

输出由一个空格隔开的两个字符串。

Samples

PYTHONN

NOY H

BINARYSEARCHTREE

AERY CNS

CORONAVIRUS

NOUV NONE

样例解释

对于样例1，