QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693799#8234. Period of a StringdoyoML 66ms26820kbC++202.6kb2024-10-31 16:46:002024-10-31 16:46:05

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 16:46:05]
  • 评测
  • 测评结果:ML
  • 用时:66ms
  • 内存:26820kb
  • [2024-10-31 16:46:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<=k;++i)
#define For(i,j,k) for(int i=j;i>=k;--i)
struct u{
	int alpha[26];
	int exi;
}ept;
bool equal(u a,u b){
	FOR(i,0,25) if(a.alpha[i]!=b.alpha[i]) return false; 
	return true;
}
bool in_it(u a,u b){
	FOR(i,0,25) if(a.alpha[i]>b.alpha[i]) return false; 
	return true;
}
u del(u a,u b){
	FOR(i,0,25) b.alpha[i] -= a.alpha[i]; 
	return b;
}
void sol(int t){
	int n;
	cin>>n;
	vector<string> s(n+1);
	vector<int> l(n+1);
	int mxl = 0;
	FOR(i,1,n){
		cin>>s[i];
		l[i] = s[i].length();
		mxl = max(l[i],mxl);
	}
	vector<vector<u>> xz(2,vector<u>(mxl));
	vector<vector<int>> cnt(n+1,vector<int>(26));
	For(i,n,1){
		int h = i&1;
		FOR(j,0,l[i]-1) xz[h][j] = ept;
		xz[h][l[i]-1].exi = 1;
		FOR(j,0,l[i]-1){
			++xz[h][l[i]-1].alpha[s[i][j]-'a'];
			++cnt[i][s[i][j]-'a'];
		}
		if(i!=n){
			FOR(j,0,l[i+1]-1){
				if(xz[h^1][j].exi){
					if(j<=l[i]-1){
						if(!xz[h][j].exi) xz[h][j] = xz[h^1][j];
						else{
							if(!equal(xz[h][j],xz[h^1][j])){
								cout<<"NO"<<'\n';
								return;
							}
						}
					}
					else{
						u lft={};
						FOR(k,0,25){
							lft.alpha[k] = xz[h^1][j].alpha[k] - j/l[i]*cnt[i][k];
							if(lft.alpha[k]<0){
								cout<<"NO"<<'\n';
								return;
							}
						}
						if(xz[h][j%l[i]].exi){
							if(!equal(xz[h][j%l[i]],lft)){
								cout<<"NO"<<'\n';
								return;
							}
						}
						else{
							xz[h][j%l[i]] = lft;
							xz[h][j%l[i]].exi = 1;
						}
					}
				}
			}
		}
//		FOR(k,0,l[i]-1){
//			cout<<"第"<<i<<"个字符串"<<k<<"级别限制:"<<endl;
//			cout<<"exi:"<<xz[i&1][k].exi<<endl;
//			FOR(j,0,25){
//				cout<<xz[i&1][k].alpha[j];
//			}
//			cout<<endl;
//		}
	}
	u now={};
	FOR(i,0,l[1]-1){
		if(xz[1][i].exi){
//			cout<<i<<"级别限制:"<<endl;
//			FOR(j,0,25){
//				cout<<xz[1][i].alpha[j];
//			}
//			cout<<endl;
			if(!in_it(now,xz[1][i])){
				cout<<"NO"<<'\n';
				return;
			}
			now = xz[1][i];
		}
	}
	cout<<"YES\n";
	now = ept;
	int ccnt = 0;
	FOR(i,0,l[1]-1){
		if(xz[1][i].exi){
			u ot = del(now,xz[1][i]);
			FOR(k,0,25){
				while(ot.alpha[k]){
					s[1][ccnt++] = 'a' + k;
					--ot.alpha[k];
				}
			}
			now = xz[1][i];
		}
	}
	FOR(i,2,n){
		FOR(j,0,l[i]-1){
			s[i][j] = s[i-1][j%l[i-1]];
		}
	}
	FOR(i,1,n){
		cout<<s[i]<<'\n';
	}
}
signed main(){
//	freopen("1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		sol(t);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3844kb

input:

4
2
abc
abcd
4
bbcaa
cabb
acabbbb
a
3
ab
aab
bbaaaaab
3
ab
aab
bbaaaaaa

output:

NO
YES
abbca
abbc
abbcabb
a
YES
ab
aba
abaabaab
NO

result:

ok ok (4 test cases)

Test #2:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

5
1
ccecddbdbbcbbaded
3
cd
d
d
1
dcedec
2
dcec
cce
8
a
e
a
c
cc
cccccccc
c
b

output:

YES
abbbbbccccdddddee
YES
dc
d
d
YES
ccddee
YES
cced
cce
NO

result:

ok ok (5 test cases)

Test #3:

score: 0
Accepted
time: 45ms
memory: 10480kb

input:

100
147
ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa
aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb
ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...

output:

NO
YES
baaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb
ba
bababababababababababababababababababababab
bababababababababababababababab
babababab
bababababbababababb
bababababbabab
baba
bababababababab
b
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
b
bbbbbbbbbbbbbb
bbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbb...

result:

ok ok (100 test cases)

Test #4:

score: 0
Accepted
time: 38ms
memory: 7444kb

input:

100
326
decadadcaaacaaeecaddaeadeadc
aaadedcaaeaaeddddaeaceaddaaaaecccaaeadeaaedaccdddcdddaaaadddacceaaadcadaeeeadeeadccdaacadaaecaedadcaaaecdaddaeaaaeccdedaceaaaacdddcecdcdacddccecaaaeaeedacaeaadaaacdadedae
acaecaaaedcdaceaaddddaaeaddccdaeaadaeedaecdacaadeeaadeceadacdadaccdaaedaddccaceea
ddccacdcea...

output:

NO
YES
ebccdeabb
ebccde
ebccd
ebccdebccdebccdebccd
ebccde
e
eeeeeeeeeeeeeeeee
eeeeeeeeeeee
eeeeeee
eeeeeeeeeeeee
eee
eeeeeeeeeeeeeeee
eeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeee
eeeeeeeeeee
eeeeeeeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeee
eeeeeeeeeeee
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
eeeeeeeeee
eee...

result:

ok ok (100 test cases)

Test #5:

score: 0
Accepted
time: 37ms
memory: 15120kb

input:

100
1114
mmiceajjcjdemdhf
c
ccccccc
cccccc
cccccccccccccccccccccccccccccccccccccccc
ccccccccc
ccccccccc
ccccccccccccccc
ccccccccccccccccccccccccc
cccccccccc
ccc
ccccccccccc
ccccccccccccccccccccccccccccccc
ccccccccc
cccccc
ccccccccccccccccccccccc
ccccccccccccc
ccc
ccccccccccc
ccccccccc
cccccccccccccc...

output:

NO
NO
YES
acgbacmikmfaaddehiibfjkacaaaaaabbbbbbcccccccccdddddeeeeeeeeeeeeefffffffgggggggghhhhhhiiiiiiiiijjjjjjjjkkkkkkklllllllmmmmm
acgbacmikmfaaddehiibfjkac
acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacm
acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmik...

result:

ok ok (100 test cases)

Test #6:

score: 0
Accepted
time: 44ms
memory: 6412kb

input:

100
512
tecvaycvrbprboqldxlzjmlbfxaseuomtjxenfyoxkmjqkifjpacqytpxmbxleryljfxeoghwfhcnhvimgkvdwjcwatlppmwbbygdbiyzvlrfqjmdnuioulrgmwfkutwgavesanvdzbypveznnvrddujscaekxauxwi
nqmlelkfqrvjbwdlvtbzxkd
kbdqfbqxqqvmkllqltebqmlrnxvxflkzedrmbwknzltfbllqllbwllwqrvkzmrdqlldvnfbkqxbdkewxrzbbndvfqrnfklllxxkvqkjf...

output:

YES
vzxjrblkeqmvnftqbdkdllwaaaaaaaabbbbbbccccccdddddeeeeeeeffffffggggghhhiiiiijjjjjjjkkklllllmmmmmmmnnnnnoooooppppppqqrrrrrsssttttuuuuuuvvvvvvvwwwwwwxxxxxxxxyyyyyyyzzz
vzxjrblkeqmvnftqbdkdllw
vzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftq...

result:

ok ok (100 test cases)

Test #7:

score: 0
Accepted
time: 55ms
memory: 9576kb

input:

1000
379
hdiyyp
ihy
hyhyiih
hiyh
iyhhihihhyhy
yhihhyyihhih
h
hhh
h
h
hhhhh
hhhh
hhhhhhhhh
hhhhhhhhhhhhh
hhhhhhhhhhhhhhhhh
hh
hhh
hhhhh
hhhhhhhh
hhhhhhhhhhhhhhhh
hhh
hhhhhhhh
hhhhhhhhh
h
hhh
hhhhhh
hhhh
hh
hhhhhhhhhh
hhhhhhh
hh
hhhhh
hhhhhh
hhhh
h
hh
hh
hh
hh
hhhhhhhhhhhhh
hhhhh
hhhh
hhhhhh
hhhh
h
hh...

output:

YES
hiydpy
hiy
hiyhiyh
hiyh
hiyhhiyhhiyh
hiyhhiyhhiyh
h
hhh
h
h
hhhhh
hhhh
hhhhhhhhh
hhhhhhhhhhhhh
hhhhhhhhhhhhhhhhh
hh
hhh
hhhhh
hhhhhhhh
hhhhhhhhhhhhhhhh
hhh
hhhhhhhh
hhhhhhhhh
h
hhh
hhhhhh
hhhh
hh
hhhhhhhhhh
hhhhhhh
hh
hhhhh
hhhhhh
hhhh
h
hh
hh
hh
hh
hhhhhhhhhhhhh
hhhhh
hhhh
hhhhhh
hhhh
h
hhhhhh
...

result:

ok ok (1000 test cases)

Test #8:

score: 0
Accepted
time: 65ms
memory: 4936kb

input:

10000
21
uiutbnjregblkwbpztgdbmahtlhe
dtulrltbnbtlbggtwmteiwzbejzdlzbtbutiapwhnurumbnutkekbjehanphbhrn
unt
tnnntktntttttnttutnuuuuuunntuuuntununutnntuttunuutttntnuntnuuntuttunnuututuntuttntnunntuntnnuuttutunuunnunuutnuuutnutnutnnntntntunnttntuuttnnuunnnnuuutntn
uttnnnntuuuutututtnttuutuuttnnnnntunnu...

output:

NO
YES
y
y
y
y
y
YES
kabhlmmszgklamrcgo
kabhlmmszgklamrcgokabhlmmszgkl
kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmsz
kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokab...

result:

ok ok (10000 test cases)

Test #9:

score: 0
Accepted
time: 54ms
memory: 9492kb

input:

10
16467
aldyra
ylaaaddrraldyaaalaaadrydlyyaryrrl
draya
yaaaadddarayrayraayyyraradddr
yyraayrdardraaadraaydadyya
dray
ay
yaayayaayyayaaaayyyaayayyyayayyayyaaayayya
ayayayyyaayyyyaayayayaa
aaayyaayyaaayyayyyyyyaayayaay
yyyyyayyayyyayyayyaayayayayyayayayaaaaaayayaaaaay
yaayay
ayaayayyyayyyayaayaayyyay...

output:

NO
YES
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxzccijnsuvx
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxz
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxznbjklmphbnoqrswyddehijllllqqsswcdiinooqw
nbjklmphbnoqrswyddehijllllqqsswcdiinooqwbabcginoppqrrrsuwxznbjkl...

result:

ok ok (10 test cases)

Test #10:

score: 0
Accepted
time: 38ms
memory: 17020kb

input:

3
32852
zjcsxffjfgqgnvamcemwbswpnxmtxxlecsfpbbaygsvvfhesoexzicbclmctcwhaosjziphqkaechmrguyddlyelzaycvlrffhalklfxlnwkpopijuuusjbwnxqcayjfygjufkpyvnv
zrwxifjqftg
zrgxf
xfggzrfxzr
grffzxxzgffxxzfggfxxfgxfgxzfzzrffxxrrfxxfgrrfzgzzrrgzrfgrzrzfgrrxgrzzgxrgzgx
xrrfrfxzgggxzgfxzrgfrzfzx
grxxfzfgzzgxggzxfzgf...

output:

YES
fzgxrfijqtwaaaaaaabbbbbccccccccccddeeeeeeffffffffgggghhhhhiijjjjjjkkkkllllllllmmmmmnnnnnoooppppppqqrssssssstuuuuuvvvvvvwwwwxxxxxxyyyyyyyzzz
fzgxrfijqtw
fzgxr
fzgxrfzgxr
fzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrfzgxrf
fzgxrfzgxrfzgxrfzgxrfzgxr
fzgxrfzgxrfzgxrfzgxrfzgx...

result:

ok ok (3 test cases)

Test #11:

score: 0
Accepted
time: 60ms
memory: 26192kb

input:

1
100000
mjrbblhjaodzaew
bhdwmabzrloejarj
waaarbwdlobbemzldjrbhjrajejo
mojrjdzwaoearbbdajrjbjleabwhlldr
abjebazdadlobwerbdoablarjjhlrdljrwmjrbje
lohrmrrjrjalaljbzmwobbbdbbdbrarbjejawallraejabddrwajelojlzdjdwlraroejjehdb
edbrlwajjba
bbjaljddbjlbjwderaawljarreb
bjraaewrjbdbdjll
rjdbl
rddjblbdjbrlrjrll...

output:

YES
rljdbabeajwohmz
rljdbabeajwohmzr
rljdbabeajwohmzrrljdbabeajwo
rljdbabeajwohmzrrljdbabeajworljd
rljdbabeajwohmzrrljdbabeajworljdrljdbabe
rljdbabeajwohmzrrljdbabeajworljdrljdbaberljdbabeajwohmzrrljdbabeajworljdrl
rljdbabeajw
rljdbabeajwrljdbabeajwrljdb
rljdbabeajwrljdb
rljdb
rljdbrljdbrljdbrlj
rlj...

result:

ok ok (1 test case)

Test #12:

score: 0
Accepted
time: 15ms
memory: 3944kb

input:

10000
2
oodmvpzyxi
vpooodzmmidixopy
25
iosxruvcl
l
lllllllllllllllll
lll
llllllllll
llll
llllllll
llllllllll
l
ll
lllll
llllllllll
l
lllllllll
llllllllll
l
llllllllllllll
l
l
ll
l
ll
l
llll
l
4
plsftdw
tsw
sttttwsswws
x
7
hbopcjceds
scedhbgccdoccechsjbbahpopd
hcq
jcc
klh
hjcjchh
jichchhcjchj
1
i
7
j...

output:

YES
dimoopvxyz
dimoopvxyzdimoop
YES
lciorsuvx
l
lllllllllllllllll
lll
llllllllll
llll
llllllll
llllllllll
l
ll
lllll
llllllllll
l
lllllllll
llllllllll
l
llllllllllllll
l
l
ll
l
ll
l
llll
l
NO
NO
YES
i
NO
YES
bcccdefggijkklmnnnoppprsttuvwwxyy
NO
YES
cghijkkkllnnpqqrtvwwz
YES
aadellssvw
YES
dy
dyd
d
d...

result:

ok ok (10000 test cases)

Test #13:

score: 0
Accepted
time: 13ms
memory: 3936kb

input:

10000
4
a
a
a
a
1
mqoukqzi
5
d
hhhhrdhhhhhhhh
hh
gh
hbhr
4
zcdufv
fdvuzudvcf
f
f
1
s
12
mi
mimimi
m
mmmmmmm
m
m
m
mm
m
mmm
m
mm
20
g
g
s
g
g
g
g
g
g
g
k
g
k
g
g
g
g
u
g
g
11
f
f
f
f
f
f
f
f
f
f
f
9
gv
v
vvvvvvvv
vvvv
vvvvv
v
vvv
vv
vvvvvv
9
ti
t
tttt
t
ttt
tt
tt
t
tt
7
x
k
d
r
r
w
r
6
nc
cf
c
v
hdcc...

output:

YES
a
a
a
a
YES
ikmoqquz
NO
YES
fduvcz
fduvczfduv
f
f
YES
s
YES
mi
mimimi
m
mmmmmmm
m
m
m
mm
m
mmm
m
mm
NO
YES
f
f
f
f
f
f
f
f
f
f
f
YES
vg
v
vvvvvvvv
vvvv
vvvvv
v
vvv
vv
vvvvvv
YES
ti
t
tttt
t
ttt
tt
tt
t
tt
NO
NO
YES
abbbcccccccccccdeeeefffgghhhiiijjjjjkklllmmmmmmnnnnoooopppppqqrrrrssttttttuuuuuvv...

result:

ok ok (10000 test cases)

Test #14:

score: 0
Accepted
time: 19ms
memory: 3680kb

input:

10000
1
t
8
ecj
ejecjscecjje
cecjejceejc
ecjeceeecjcjcj
cea
oc
ceec
ecbc
34
zevdfbzayddtgja
dea
aaadc
aadaa
daa
a
a
a
x
aa
aaaaaaaa
a
aaa
aa
a
a
ba
aaa
aaaaa
aaaaa
aaa
aaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaa
aaa
aa
a
aa
aaa
aaaa
aaaaaaa
aa
aaa
1
xdvwkodeoicwnscdpkhwmxriaudyinlvbniaqhqnldbgtigvra...

output:

YES
t
NO
NO
YES
aaaabbccddddddeefggghhhiiiiiijjkkllmnnnnoooppqqrrssttuvvvwwwxxyyz
YES
erz
erzerz
e
eee
eee
eeeeeeeeeeeeeeeee
eeeeeeeeeeeeeee
eeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeeeeeee
eeeeee
eeeeee
eee
eee
e
NO
NO
YES
u
u
u
u
u
u
u
YES
kiims
kiimskiimskiimskiimskiimsk
kiimskiimskiimskiimski
kiimskiim...

result:

ok ok (10000 test cases)

Test #15:

score: 0
Accepted
time: 63ms
memory: 4024kb

input:

10000
3
aabbabbbbabaaaaabbbaaabaaaaaaa
baabababaabaaabaabbaabaababaaaaaaabaaaaaabbaabbbaaabaaaababaaabbaaaaaaaaababbaaabaaaababaaabbbbaababaaaaaaaaabbaaabbbaabbaaabaaaaaabbabbaaaaabaabbaaabaaabaaabaabaaabbabaabaabbaabaaaababababaabbaababbabbaaaabbabababbbbbaaabaaaabaabbbbbaaabaaaaaaaabbaaabaaabaaaba...

output:

YES
aaaaaaaaaaaaabbbbbbaaaaababbbb
aaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaababbbbaaaaaaaaaaaaabbbbbbaaaaab...

result:

ok ok (10000 test cases)

Test #16:

score: 0
Accepted
time: 52ms
memory: 3792kb

input:

10000
5
lzmafakuzucfezeldfgsdytjfomzjcfovbdvmagqfuqpwyrxarcgqks
cuszpkqzglakwledzoruucgeqmrfyfoymxvfvfjagazcjdsqfabfmdt
jkeqogazgzuduffffmkefslrfwuz
lkufefzqrzqkafqoffuwzwfrgljsrfuzsdugkfmdoedzzeuegfeufmkjfugffafk
zfzeugdzjaefukgudamlmuufjlufruzjkdojfkgufeuwukzqwlfaqfuogqezzsfrkkukkfadezfgozfffsfoff...

output:

NO
YES
bbbccefffghhiijjkkklllmmmoooppqqqrrstttuvwwyzaaccccddeeeffikmmmnoopqqrvvwwwxxyyy
bbbccefffghhiijjkkklllmmmoooppqqqrrstttuvwwyz
NO
YES
esaabceehhhhjknrsvvvwwxbb
esaabceehhhhjknrsvvvwwxbbesaabceehhhhjknrsvvvwwxbbesaabceehhhhjknrsvvvwwxbbes
esaabceehhhhjknrsvvvwwxbbesaabceehhhhjknrsvvvwwxbbesaab...

result:

ok ok (10000 test cases)

Test #17:

score: 0
Accepted
time: 54ms
memory: 4040kb

input:

1000
54
aabbbabaabbaaabbababb
abaabbbbbaaabbabbabbbabbaabaa
bbbbbabbbaaaabaabbbbbbbbaabababaaabaaaaabbbbbabbbaaabbaaa
aababbbbabaaabbbbabbbbaabaaa
aaababbbbabaaabababbbbabbaabbbab
aaababbbbbabbababbbabbaaabbaaabbbaabbb
bbaaabaabbabaababbbbbababbaabbbbbabababbaaaababbb
babaaaababaababaaabaaaaaabbbbbb...

output:

YES
babbbaabaababbabbbaaa
babbbaabaababbabbbaaababbbaab
babbbaabaababbabbbaaababbbaabbabbbaabaababbabbbaaababbbaa
babbbaabaababbabbbaaababbbaa
babbbaabaababbabbbaaababbbaababb
babbbaabaababbabbbaaababbbaababbbabbba
babbbaabaababbabbbaaababbbaababbbabbbababbbaabaab
babbbaabaababbabbbaaababbbaababbbab...

result:

ok ok (1000 test cases)

Test #18:

score: 0
Accepted
time: 49ms
memory: 3812kb

input:

1000
26
ayhlojxlxzojvtmgetowruycwvrfjpzjd
yvyoxrurlwdtaegcolmzpvzjtjojfxw
zldlpxyramxfvjjoyzcretvgwjt
lgxpyydjazvvxcojjlzm
xzvyxjladcclxdymvygojpxaljmpgvjzzyzjoj
mjjcxxaxjjjxvjxjadylzzpvdmpvozyzclyyaovgomjlxyplazzxymjyvjlojzydjcycdajlzlxgyzojjzxjvjazjgypxxcglvxmdgcpv
vgcdzoxjaaazvmzygvyjajcxjypjmjyx...

output:

YES
jjxacjyzxpvzlydmgolvefrrttwoouwhj
jjxacjyzxpvzlydmgolvefrrttwoouw
jjxacjyzxpvzlydmgolvefrrttw
jjxacjyzxpvzlydmgolv
jjxacjyzxpvzlydmgolvjjxacjyzxpvzlydmgo
jjxacjyzxpvzlydmgolvjjxacjyzxpvzlydmgojjxacjyzxpvzlydmgolvjjxacjyzxpvzlydmgojjxacjyzxpvzlydmgolvjjxacjyzx
jjxacjyzxpvzlydmgolvjjxacjyzxpvzlydm...

result:

ok ok (1000 test cases)

Test #19:

score: 0
Accepted
time: 47ms
memory: 4428kb

input:

100
2237
baabaaabaaaabbbbaabaaaababaaaaba
aaabaaaaabaaabaaababbbababaaaaaaaabbabbaabb
abaaabbaaaaabbaaabbabaaabab
aaaaaaaaaaabaabaaaabaaabbbbbbababaabaabbaaaababaababbaababaabbabbaaabb
abaababbbbaababaababaaababababaaabbaaaaaaaaaaabababaababbaaaaaabb
abbabaaaaaababaaabbaba
abaaaaaabaaababaabbbbbaaaa...

output:

NO
YES
aaaabbaabbbbbabaaaabaaaabaaaaaaaaaabbbbbbbbbbaaaaaabb
aaaabbaabbbbbabaaaabaaaabaaaaaaaaaabbbbbbbbbb
aaaabbaabbbbbabaaaabaaaabaaaaaaaaaabbbbbbbbbba
aaaabbaabbbbbabaaaabaaaab
aaaabbaabbbbbabaaaabaaaabaaaabbaabbbbbabaa
aaaabbaabbbbbabaaaabaaaabaaaabbaab
aaaabbaabbbbbabaaaabaaaabaaaabbaabaaaabbaa...

result:

ok ok (100 test cases)

Test #20:

score: 0
Accepted
time: 42ms
memory: 4452kb

input:

100
2742
cecabdaaaeeeedceceeccceaeabeccdbaabcbdaadddeeaeadaedcedcbcecabadceebeeadec
ceeacdbaecaecaaacacacdebceaedcb
eaacbacccaceeaccceeeeccaeabeeccabdddabcdcbedaaacaecacaaedcaeba
abecadadcebabaeacdacecca
caaaaebeaaccaadaaddacbbbeacecdbeccaadcabecadaccee
cadacbceaabedacacaceba
eabaaecbdccbaacadaaeecc...

output:

YES
aaeecbabccacccaabaaedddeaccceeeaaaaaaabbbbbcccccccdddddddddeeeeeeeeeeeeeee
aaeecbabccacccaabaaedddeaccceee
aaeecbabccacccaabaaedddeaccceeeaaeecbabccacccaabaaedddeaccceee
aaeecbabccacccaabaaeddde
aaeecbabccacccaabaaedddeaaeecbabccacccaabaaedddea
aaeecbabccacccaabaaedd
aaeecbabccacccaabaaeddaaeecb...

result:

ok ok (100 test cases)

Test #21:

score: 0
Accepted
time: 41ms
memory: 4308kb

input:

100
463
oygvfytmfirgjwwqspymwkpky
ywjskfvwgtwyqmykopgympf
svytqkpfgpmjfomykwyykwftymwpomwqywg
vqgyytmykywjpwmjmfwtwwwptyfmksykommygywfyofoqggwkympksypfvtoykpq
kkfpmqwfotgywwfmkspymwkqjpmpvfqytyomytgwomwwyyy
fpgymswyqjowmyqomyfvwgwkwpyfyktkftymtpqmykwo
ystpkmygoymwkwgotfyvjkywfmpqy
ktfwqpykjgmvpmgwyy...

output:

NO
YES
tpqvnumazibxxszfonpkdkciapabccccdddefffggghijjllmmmnnnooqqrrrsvwxxyyyzzzjmnorraaaaaaaabbbbbbbbcccddddddeeeeeeeffffffffggggggggghhhhhhhiiiiiiiiiiiiijjkkkkklllllllllmmmmmnnnnooooppppppqqqqqrrrrssssssssssstttttuuuuuuuuvvvvvvvvvwwwwxxyyyyyyyzzzzzzzz
tpqvnumazibxxszfonpkdkciapabccccdddefffggghijjl...

result:

ok ok (100 test cases)

Test #22:

score: 0
Accepted
time: 52ms
memory: 13252kb

input:

10
1037
babbabbbabbababbaaaabaaabaabbaabaaabbaabbbaaaab
abbaabaabaaaaabababaaaabbaabbbbbbbbababababbaa
aaaabaaaabbbbbbbbababababbaababaabbbaaabababbaaabaaaaaabbabaabababaabbabab
aaaaabaaaabbabbbabbbbaabbbabbbabbaaababaaababaaba
aaabbaabbbabaaabbaaaaaababababbbbab
baabaabbaabaaaabbabbababbabaabbaab
b...

output:

YES
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbba
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbb
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbbaabaabbabbbbaabbaabaaaaaabba
aabaabbabbbbaabbaabaaaaaabbaaabbbbaaaaaabbbbbbaab
aabaabbabbbbaabbaabaaaaaabbaaabbbba
aabaabbabbbbaabbaabaaaaaabbaaabbbb
aabaa...

result:

ok ok (10 test cases)

Test #23:

score: 0
Accepted
time: 40ms
memory: 7628kb

input:

10
3928
ryebddpjljiukrikjtylkpbwsyicayhhc
yrtckcaijkhutpjrlpiyyppkbwicdklyiydrdbiihlyybkcesjb
tkkdahhldwkpisyypjbyiicerccbjuljpyrkdil
ilypujtjbckirykdhlcybkpi
yjtphkbpkriiykkbjiccucdyll
tybkjirukdiipbjiulciryyyupjklkrypcddkylkckcirhlkibyyjpkdjilkkjkcpkcpyyyjcpklpbiucihtyitiulckbbcjkycpjybklicbplykcb...

output:

YES
ckdilpcyykbyibitrphlkujjadehjrswy
ckdilpcyykbyibitrphlkujjadehjrswyckdilpcyykbyibitrp
ckdilpcyykbyibitrphlkujjadehjrswyckdilp
ckdilpcyykbyibitrphlkujj
ckdilpcyykbyibitrphlkujjck
ckdilpcyykbyibitrphlkujjckckdilpcyykbyibitrphlkujjckckdilpcyykbyibitrphlkujjckckdilpcyykbyibitrphlkujjckckdilpcyykbyib...

result:

ok ok (10 test cases)

Test #24:

score: 0
Accepted
time: 62ms
memory: 26532kb

input:

1
100000
abbaabbaaabbbbbbbbbbbabbabbbbbbaabb
bbabaabbbabbbbabbbbbabbbbbbbabbabababbaabb
ababbababbbaaabbaabbbbaabbbbabbbbbbbbbbbbbbbbbabababaabbabbbbbaaaababbbbabbbbbbbbbabbbbbbbbabbbbbbbbbaabbbbbbbabbababbaabbabbbabbbbabbbabbbaabababbabbbbbababbbabbabbbababbabaaabbbbbbbbbb
babbabaaabbbbbbaabbbbbabb...

output:

YES
abbbbababbbbabbbbbabbbbbbaaaabbbabb
abbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbab
abbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbbabbbbbbaaaabbbabbabbbbababbbbababbbbabbbbb
abbbbababbbbabbbbbabbbbbbaaaab...

result:

ok ok (1 test case)

Test #25:

score: 0
Accepted
time: 66ms
memory: 26772kb

input:

1
100000
baababbaababbaaabaabaabbaabbbabbbababaabbaabbbabbaaabbbbbaabaa
bbbaaaababaaaaa
bbaabaaaabbababaabaabababaaaabaaabaaaaaaababa
abaabbaaaababaaba
abbaababbaaabbaaaa
bbbaaaaaaabbabababaaaabaaaa
aabbaaababaaaabaabaaaababbbabaaa
baaaaaaaabbaaaaabaababbbbaabaaabaaaaababa
aaabaaabbbababbbaaaa
babab...

output:

YES
babaaaaaabaabbaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbb
babaaaaaabaabba
babaaaaaabaabbababaaaaaabaabbababaaaaaabaabba
babaaaaaabaabbaba
babaaaaaabaabbabab
babaaaaaabaabbababbabaaaaaa
babaaaaaabaabbababbabaaaaaababaa
babaaaaaabaabbababbabaaaaaababaababaaaaaa
babaaaaaabaabbababba
babaaaaaab...

result:

ok ok (1 test case)

Test #26:

score: 0
Accepted
time: 31ms
memory: 26612kb

input:

1
100000
ogecmjpwerfmfmapxnrtjzgymywjxizyfrnomwxhqdeconkmkyw
rojkqgyjnzpxyknaxdpgwzwf
poazxkfkowqrypjkkzxzjqpqngyqwyzfrnjkypgfpjxkowjyzgdwxwnxwzdnpaoynkrggjzngjxawdp
zynynygpqpzdqonwxgfjzprxgpafwqjnraxzkodwjowkykgkjx
rodznjznjqdaxjfwnoqgxyyopxgkkkwgppwkxzyfnzrjwygqap
pakjzpnwgjxrgwzfzokqqkyoydwxn
xk...

output:

NO

result:

ok ok (1 test case)

Test #27:

score: 0
Accepted
time: 52ms
memory: 26820kb

input:

1
100000
ihuppckdjjsbspctuttc
dbpsibscpcjpsjktcpbscpubjstupjcuutkpchsitjpsbbhtdktcccdhkjhcpcutskujpcsptjptssiupjpuuhtipttuicipdhsdjctpdbtjutptppupjtcctthtupcjskpcbcsdsjjputckujcicschhtttkducpcji
hpjiktthjjssbkcdbuucttppscupkjtptcuscppbddicjpcuths
cjbkpuphsctpjuscthbhditipcpdputtcuspsjbtjpthckkcjdttp...

output:

YES
jchpkpbdstucpicsjttu
jchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstucpicsjttujchp
jchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstu
jchpkpbdstucpicsjttujchpkpbdstucpicsjttujchpkpbdstujchpkpb...

result:

ok ok (1 test case)

Test #28:

score: 0
Accepted
time: 39ms
memory: 17360kb

input:

1
50000
wpmbctmpdufpqucxpynbxleqtnvnmahajofjenodxqdmtvhjgxkaalzqgvamarwjbjytsgehjgrbqawyhoujwlobjlpyqwl
ojapjpjpcqwxhghmvnenmugwwxtjoeanuleahdbnhotmkalrqmcojwwtljbonuyaxbyqfwgpgqcjnlrqmpaquxlyldatvyspqpjqybdhxvadqjobzfbwuqxahru
xhanwqbwppqryeoahgoxlqmuhmxpwmquyjxwuhcadnjl
uywucuoahwwqxaneyywaxonenml...

output:

NO

result:

ok ok (1 test case)

Test #29:

score: 0
Accepted
time: 45ms
memory: 17364kb

input:

1
50000
muzrveujbtkgwktuzfsuuclmecucfpmkhmlqzbydnagqedywghjhzhtxaow
tbhgfwqluyzzwkbmasuwqphjoalumuwfunuaezbhcuwkkceduufmdztgtbvmzgtjcuqpcrulrzzwtecxhkugzemxmgyyhdmjmyh
bmerqmqhzuftbcajtfxrtymwyzhuuulkdwnqmwywhzevgauhgaxmczwzmulcgybgzudzodusphblekmjkcpuktfw
jfdwbfzawqqrmlckwlmmkcjzudwbhpmggdkuwwtrfpx...

output:

YES
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefghhjkklnoqstv
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefghhjkklnoqstvcyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguu
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefghhjkklnoqstvcyumwukymlzxmrabpqdhwgzzbwuft
cyumwukymlzxmrabpqdhwgzzbwuftcjmethuzguuacdeefg...

result:

ok ok (1 test case)

Test #30:

score: -100
Memory Limit Exceeded

input:

1
100000
tfachkqbvxppacinlodgymgniazuyyozoreheehctbqzrezzvclzzetgtyxdcbqfvegqkqrzwwajisqixlzccdgxqeqcfsqvinarlgefiyxgscymzuyqaknbhotzatiqrcmpwxetjypqbrqovslhnnnifpacwcufuztsbvrfxcvmopnccqlpskhkaqxmrutqnlcvdwrmtfyvtqokwzhwzsajzkviwqdyocyejcuggusnlqgbjeyiofhzgkxsushlnlnwafrkdhdbghipwehuzzgvhkftklqslwj...

output:

YES
maaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

result: