Вам задана строка \(s\). Вам нужно найти две непустые строки \(a\) и \(b\) такие, что выполняются следующие свойства:
- Обе строки \(a\) и \(b\) являются подпоследовательностями \(s\).
- Для каждой позиции \(i\) символ \(s_i\) строки \(s\) принадлежит ровно одной строке: \(a\) или \(b\).
- Строка \(a\) является лексикографически минимально возможной; строка \(b\) может быть любой возможной.
Для заданной строки \(s\), выведите любую пару \(a\) и \(b\).
Напоминание:
Строка \(a\) (\(b\)) является подпоследовательностью строки \(s\), если \(a\) (\(b\)) может быть получена из \(s\) путем удаления нескольких символов (возможно, ни одного). Например, «dores», «cf» и «for» являются подпоследовательностями «codeforces», а «decor» и «fork» не являются.
Строка \(x\) лексикографически меньше чем строка \(y\), если выполняется одно из следующего:
- \(x\) является префиксом \(y\), но \(x \ne y\);
- в первой позиции, где \(x\) и \(y\) различны, в строке \(x\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(y\).
Выходные данные
Для каждого набора входных данных, выведите строки \(a\) и \(b\), удовлетворяющие описанным выше условиям. Если существует несколько ответов, выведите любой из них.
Примечание
В первом наборе входных данных, есть только две пары строк: либо \(a =\) f и \(b = \) c, либо \(a = \) c и \(b = \) f. И \(a = \)c лексикографически меньше, чем \(a = \) f.
Во втором наборе, a это единственная буква в строке.
В третьем наборе, можно доказать, что b — лексикографически наименьшая подпоследовательность \(s\). Вторая строка может быть нескольких вариантов; один из них представлен выше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
fc
aaaa
thebrightboiler
|
c f
a aaa
b therightboiler
|