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 .
If character is not present in the current string , then character is appended to the end of string .
If character is already present in the current string , then the suffix of string up to and including the first occurrence of character is removed from . In this case, the currently processed character is not added.
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:
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'.
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.
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'.
Example 1
Example 2
Example 3
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.
( points): |s|=|t|=1;
( points): can be obtained from by permuting letters;
( points): all letters in are distinct;
( points): only one letter in string appears more than once;
( points): s="\texttt{aaaaabbbbbcccccddddd}";
( points): |s| \le 8;
( points): no additional constraints.