Great wizard gave Alice and Bob a cycle string of length $2 dot.op n$, which has no repeated substrings of length $n$. In a cycle string, character $s_{i + 1}$ comes after $s_i$. Also, $s_1$ comes after $s_{2 n}$.
Unfortunately, evil gin shuffled all the symbols of the string. Help Alice and Bob restore the original string so that the above condition is satisfied.
The first line contains one string $s$ of length $2 dot.op n$ ($2 <= 2 dot.op n <= 1 thin 000 thin 000$) which consists only of the lowercase Latin letters.
Print "_NO_" (without quotes) to the first line if it is impossible to restore the string so that the condition is satisfied. Otherwise, in the first line print "_YES_" (without quotes).
In the second line print one string — the restored string.
If there are multiple answers, print any.
In the first example, substrings of the restored string are: "_abbab_", "_bbabc_", "_babcb_", "_abcbc_", "_bcbcc_", "_cbccb_", "_bccba_", "_ccbab_", "_cbabb_", "_babba_".
Note that the first example does not contain repetitions, however it can be rewritten as another cycle with no repetitions. Thus, the solution is not unique — the given example is also a correct solution.
In the second example, it is impossible to restore the string so that no repetition exists.
In the third example, there is no need to change anything.
## Input
The first line contains one string $s$ of length $2 dot.op n$ ($2 <= 2 dot.op n <= 1 thin 000 thin 000$) which consists only of the lowercase Latin letters.
## Output
Print "_NO_" (without quotes) to the first line if it is impossible to restore the string so that the condition is satisfied. Otherwise, in the first line print "_YES_" (without quotes).In the second line print one string — the restored string.If there are multiple answers, print any.
[samples]
## Note
In the first example, substrings of the restored string are: "_abbab_", "_bbabc_", "_babcb_", "_abcbc_", "_bcbcc_", "_cbccb_", "_bccba_", "_ccbab_", "_cbabb_", "_babba_".Note that the first example does not contain repetitions, however it can be rewritten as another cycle with no repetitions. Thus, the solution is not unique — the given example is also a correct solution.In the second example, it is impossible to restore the string so that no repetition exists.In the third example, there is no need to change anything.
**Definitions**
Let $ x \in \mathbb{Z}^+ $ be the required amount of gold.
Let $ n \in \mathbb{Z}^+ $ be the number of houses.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers representing gold in each house, indexed from 1 to $ n $.
**Constraints**
1. $ 1 \leq n \leq 1000 $
2. $ 1 \leq x \leq 10^6 $
3. $ 1 \leq a_i \leq 1000 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Find the minimum distance $ d $ Bashar must walk, defined as the number of steps between the first and last house visited (i.e., if he visits houses from index $ i $ to $ j $, then $ d = |j - i| $), such that the sum of gold from a contiguous subarray $ \sum_{k=i}^{j} a_k \geq x $.
If no such contiguous subarray exists, output $ -1 $.
Formally, compute:
$$
\min_{1 \leq i \leq j \leq n} \{ j - i \mid \sum_{k=i}^{j} a_k \geq x \}
$$
If the minimum does not exist, return $ -1 $.