在 C/C++ 中，scanf 使用格式化字符串 "%[...]" 来读取由该格式化字符串定义的字符集组成的字符串。

左括号后面紧跟一个字符序列和一个右括号。括号之间的字符序列 $f$ 定义了可接受的字符集。这里只允许使用 ASCII 码在 32（空格）到 126（~）之间的字符。在本题中，字符 ^、] 和 - 仅在格式化字符串中用作控制字符。

如果序列 $f$ 的第一个字符不是脱字符（^），则序列 $f$ 定义了可用字符集 $s$，该函数将读取所有字符，直到遇到第一个不在集合 $s$ 中的字符或输入结束。如果序列 $f$ 的第一个字符是 ^，则其后必须紧跟一个非空字符序列，用于定义禁用字符集 $s$，该函数将读取所有字符，直到遇到第一个在集合 $s$ 中的字符或输入结束。

一组 ASCII 码连续的字符可以简写为一个区间：该组中的第一个字符、减号（-，ASCII 码为 45）、该组中的最后一个字符。例如，区间 "B-Q" 定义了从 'B' 到 'Q'（含）的所有大写英文字母。

如果一个字符串仅由大写和小写英文字母、数字和空格组成，则称其为字母数字字符串。

给定一个字母数字字符串 $t$，构建一个 "%[...]" 格式的字符串，满足：

1. 接受字符串 $t$：当输入该字符串时，scanf 能够完整地读取它。
2. 接受最少数量的其他长度为 $|t|$ 的字母数字字符串。
3. 在所有满足上述条件的格式化字符串中，其长度（作为字符串）最小。
4. 在所有满足上述条件的格式化字符串中，其字典序最小。

输入格式

输入的第一行包含一个非空字符串 $t$，仅由大写和小写英文字母、数字和空格组成。保证该字符串的长度不超过 $100\,000$，不包含前导或尾随空格，且不包含两个或更多连续的空格。

输出格式

输出一个格式化字符串 "%[...]"（不带引号）作为答案。

样例

输入样例 1

bc0123456789ABCDEFxxyyzz

输出样例 1

%[!-Fbcx-z]

输入样例 2

012345678 abcdefABCDEF

输出样例 2

%[^9G-Zg-z]

输入样例 3

01234567 abcdefABCDEF

输出样例 3

%[ -7:-F[-f]

说明

请注意，格式化字符串中可能包含非字母数字字符。例如，在样例 1 中，使用 '!'（ASCII 码为 33）代替 '0'，因为 '!' 到 'F' 之间的字母数字字符数量与 '0' 到 'F' 之间的相同，但包含 '!' 的格式化字符串字典序更小。

如果字符串 $b$ 不是字符串 $a$ 的前缀，且满足以下两个条件之一，则称字符串 $a$ 的字典序小于字符串 $b$：

1. $a$ 是 $b$ 的前缀。
2. 设 $k$ 为 $a$ 和 $b$ 首次出现不同字符的位置。字符串 $a$ 在位置 $k$ 处的字符的 ASCII 码小于字符串 $b$ 在位置 $k$ 处的字符的 ASCII 码。

提示（ASCII 码表）