A. Две подпоследовательности
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана строка $$$s$$$. Вам нужно найти две непустые строки $$$a$$$ и $$$b$$$ такие, что выполняются следующие свойства:

  1. Обе строки $$$a$$$ и $$$b$$$ являются подпоследовательностями $$$s$$$.
  2. Для каждой позиции $$$i$$$ символ $$$s_i$$$ строки $$$s$$$ принадлежит ровно одной строке: $$$a$$$ или $$$b$$$.
  3. Строка $$$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$$$.
Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют сами наборы входных данных.

В первой и единственной строке каждого набора задана одна строка $$$s$$$ ($$$2 \le |s| \le 100$$$, где $$$|s|$$$ означает длину строки $$$s$$$). Строка $$$s$$$ состоит только из строчных букв латинского алфавита.

Выходные данные

Для каждого набора входных данных, выведите строки $$$a$$$ и $$$b$$$, удовлетворяющие описанным выше условиям. Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
3
fc
aaaa
thebrightboiler
Выходные данные
c f
a aaa
b therightboiler
Примечание

В первом наборе входных данных, есть только две пары строк: либо $$$a =$$$ f и $$$b = $$$ c, либо $$$a = $$$ c и $$$b = $$$ f. И $$$a = $$$c лексикографически меньше, чем $$$a = $$$ f.

Во втором наборе, a это единственная буква в строке.

В третьем наборе, можно доказать, что b — лексикографически наименьшая подпоследовательность $$$s$$$. Вторая строка может быть нескольких вариантов; один из них представлен выше.