#P18506. Period of a String

Period of a String

Period of a String

Randias 有 nn 个字符串 s1,s2,…,sns_1,s_2,\ldots,s_n。

对于字符串 a=a0a1…ap−1a=a_0a_1\ldots a_{p-1} 和 b=b0b1…bq−1b=b_0b_1\ldots b_{q-1},如果对于每个 0≤i<q0\le i<q 都有

bi=ai mod p,b_i=a_{i\bmod p},

就称 aa 是 bb 的一个周期。这里不要求 p≤qp\le q,也不要求长度整除。

Randias 可以任意次执行以下操作:选择一个字符串 sis_i,再选择两个下标 j,kj,k(0≤j,k<∣si∣0\le j,k<|s_i|),交换 si,js_{i,j} 和 si,ks_{i,k}。

他希望操作结束后,对于每个 1<i≤n1<i\le n,si−1s_{i-1} 都是 sis_i 的一个周期。请输出一组可能的最终字符串,或者判断无法做到。

输入格式

每个输入文件包含多组测试。第一行包含整数 tt(1≤t≤1041\le t\le10^4),表示测试组数。

每组测试第一行包含整数 nn(1≤n≤1051\le n\le10^5)。

接下来 nn 行,第 ii 行给出字符串 sis_i(1≤∣si∣≤5⋅1061\le|s_i|\le5\cdot10^6),只包含小写英文字母。

保证整个输入文件的所有测试组中,nn 的总和不超过 10510^5,所有字符串长度的总和不超过 5⋅1065\cdot10^6。

输出格式

对每组测试,如果有解,先输出 YES,接下来 nn 行按顺序输出最终字符串 s1′,…,sn′s'_1,\ldots,s'_n。每个 si′s'_i 必须能够由原 sis_i 通过内部交换得到,并满足所有相邻周期关系。有多个答案时可输出任意一个。

如果无解,输出 NO。

完整原样例(含四组测试)

4
2
abc
abcd
4
bbcaa
cabb
acabbbb
a
3
ab
aab
bbaaaaab
3
ab
aab
bbaaaaaa
NO
YES
abbca
abbc
abbcabb
a
YES
ab
aba
abaabaab
NO