A14577 | Two Subsequences

You are given a string $s$ . You need to find two non-empty strings $a$ and $b$ such that the following conditions are satisfied:

1. Strings $a$ and $b$ are both subsequences of $s$ .
2. For each index $i$ , character $s_i$ of string $s$ must belong to exactly one of strings $a$ or $b$ .
3. String $a$ is lexicographically minimum possible; string $b$ may be any possible string.

Given string $s$ , print any valid $a$ and $b$ .

Reminder:

A string $a$ ( $b$ ) is a subsequence of a string $s$ if $a$ ( $b$ ) can be obtained from $s$ by deletion of several (possibly, zero) elements. For example, "dores", "cf", and "for" are subsequences of "codeforces", while "decor" and "fork" are not.

A string $x$ is lexicographically smaller than a string $y$ if and only if one of the following holds:

- $x$ is a prefix of $y$ , but $x \ne y$ ;
- in the first position where $x$ and $y$ differ, the string $x$ has a letter that appears earlier in the alphabet than the corresponding letter in $y$ .

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \le t \le 1000$ ). Description of the test cases follows.

The first and only line of each test case contains one string $s$ ( $2 \le |s| \le 100$ where $|s|$ means the length of $s$ ). String $s$ consists of lowercase Latin letters.

For each test case, print the strings $a$ and $b$ that satisfy the given conditions. If there are multiple answers, print any.