题目描述

Diputs 记数法用于表示非负整数。它有 9 种“数字字符”，从最低位到最高位依次为：

_ . , - ~ = ' ^ "

每种字符允许出现的最大次数如下：

一个 Diputs 数从最高位字符写到最低位字符，例如：

"""^^~~-,..__

把所有合法的 Diputs 表示按照如下顺序排列：先比较最高位字符 " 的个数，个数少的在前；若相等，再比较 ^ 的个数；依次比较到 _。从 1 开始给这些表示编号，编号就是它所代表的十进制正整数。数字 0 用字符 O 表示。

例如：

输入是一段任意文本，其中可能混有十进制数、Diputs 数和普通字符。你需要把所有十进制数转换为 Diputs 表示，把所有 Diputs 数转换为十进制表示，其余字符保持不变。

数字之间不一定有分隔符，因此必须采用贪心解析：从当前位置开始，取能够构成一个合法数字的最长前缀。

例如 ___ 应解析为 __ 和 _，因此转换后为 21。十进制数也按同样方式处理，且十进制表示不能有前导零，所以 020 应解析成 0 和 20。如果连续十进制数字构成的数超过 Diputs 能表示的最大值，也应在不超过最大值的最长前缀处切开。

此外，如果整段输入中识别出的数字总数为奇数，则在完成“记数法互换”之前，先将这些数字的数值按升序重新排列；数字所在位置原本应输出哪一种记数法不变，普通文本的位置也不变。

输入格式

输入为任意文本。输入大小不超过 $10^6$ 字节。

所有被识别出的数均为非负数，并且不会超过 Diputs 能表示的最大值。题目保证输出大小同样不超过 $10^6$ 字节。

输出格式

输出转换后的完整文本。

样例

输入

need 2 sort
O
_

输出

need O sort
1
2