33431번 - Period of a String 스페셜 저지다국어

문제

Randias has $n$ strings $s_{1}, s_{2}, \ldots, s_{n}$.

For two strings $a = \overline{a_{0} a_{1} \ldots a_{p-1}}$ and $b = \overline{b_{0} b_{1} \ldots b_{q-1}},ドル if for all $i$ (0ドル \le i < q$), $b_{i} = a_{i \bmod {p}},ドル we say that $a$ is a period of $b$.

Now, Randias can perform the following operation:

• Choose one string $s_{i}$ and choose two indices $j$ and $k$ (0ドル \le j, k < |s_{i}|$), then swap $s_{i,j}$ and $s_{i,k}$.

He can perform this operation any number of times. After all the operations, he wants the following to be true: for each 1ドル < i \le n,ドル string $s_{i-1}$ is a period of $s_{i}$.

Help him to find the possible final strings, or determine it is impossible.

입력

Each test contains multiple test cases. The first line contains a single integer $t$ (1ドル \le t \le 10^4$) denoting the number of test cases. For each test case:

The first line contains a single integer $n$ (2ドル \le n \le 10^5$).

Then follow $n$ lines. The $i$-th of these lines contains the string $s_{i}$ (1ドル \le |s_{i}| \le 5 \cdot 10^6$). It is guaranteed that the strings only contain lowercase English letters.

It is guaranteed that the sum of $n$ does not exceed 10ドル^5,ドル and the sum of $|s_{i}|$ does not exceed 5ドル \cdot 10^6$.

출력

For each test case, if it is possible to make $s_{i-1}$ a period of $s_{i}$ for all $i$ after some operations, output "YES" (without quotes) on the first line. Then output $n$ strings in $n$ lines. The $i$-th string $s'_{i}$ represents the $i$-th string after all operations. If there are multiple answers, output any one of them.

If it is impossible to do that, output "NO" (without quotes) on the first line.

제한

힌트