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.