Unique Letters#525

Unique Letters

0,3 seconde
256 mégaoctets
Very hard

You are given two strings and , consisting of lowercase Latin letters.

You may arbitrarily permute the characters in string and arbitrarily permute the characters in string .

We define the uniquization of a string as the following process. First, an auxiliary string is empty. Then the characters of string are processed from left to right. Suppose the current character is .

The string obtained after processing all characters will be called the result of uniquization of this string.

Determine whether it is possible to obtain strings s' and t' such that:

Input

The first line contains string (1 \le |s| \le 2 \cdot 10^5).

The second line contains string (1 \le |t| \le 2 \cdot 10^5).

Both strings consist only of lowercase Latin letters.

Output

If it is impossible to obtain the required strings s' and t', output «NO».

Otherwise, output «YES». Then output two strings s' and t' such that:

  • s' is a permutation of the characters of string ;

  • t' is a permutation of the characters of string ;

  • the result of uniquization of string s' is equal to t'.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

For the first sample:

We permute string as , and string as .

Construct string :

  • after character , we have a = \texttt{b};

  • after character , we have a = \texttt{bc};

  • after character , we have a = \texttt{bcd};

  • after character , the letter is already present in string , so we remove the suffix up to and including the first occurrence of . After that, becomes an empty string;

  • after character , we have a = \texttt{e};

  • after character , we have a = \texttt{ef}.

At the fourth step, letters and are also removed from string , not only letter .

The resulting string is equal to the permuted string , so an answer exists.

For the second sample:

We permute string as , and leave string as .

Construct string :

  • after character , we have a = \texttt{b};

  • after character , we have a = \texttt{bc};

  • after character , we have a = \texttt{bcd};

  • after character , the letter is already present in string , so we remove the suffix up to and including the first occurrence of . After that, becomes an empty string;

  • after character , we have a = \texttt{f};

  • after character , we have a = \texttt{fb};

  • after character , the letter is already present in string , so we remove the suffix up to and including the first occurrence of . After that, a = \texttt{f}.

At the fourth step, letters and are also removed from string , not only letter .

The resulting string is equal to the permuted string , so an answer exists.

In the third sample, it can be proved that for no permutation of string cgbfedc will the result of uniquization be a permutation of string gfbc.

Scoring

  1. ( points): |s|=|t|=1;

  2. ( points): can be obtained from by permuting letters;

  3. ( points): all letters in are distinct;

  4. ( points): only one letter in string appears more than once;

  5. ( points): s="\texttt{aaaaabbbbbcccccddddd}";

  6. ( points): |s| \le 8;

  7. ( points): no additional constraints.