QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#648926#8334. Genezzhrnoicansolve#AC ✓2304ms306792kbC++172.0kb2024-10-17 20:58:432024-10-17 20:58:46

Judging History

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

  • [2024-10-17 20:58:46]
  • 评测
  • 测评结果:AC
  • 用时:2304ms
  • 内存:306792kb
  • [2024-10-17 20:58:43]
  • 提交

answer

#include<bits/stdc++.h>

typedef long long int ll;
typedef unsigned long long int ull;
#define pii pair<int,int>
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
#define pb push_back
#define lowbit(x) ((x) & (-x))

using namespace std;
const int INF = 0x3f3f3f3f;
const double EPS=1e-10;
const double Pi=3.1415926535897;
const int mod=1e9+7;
const int maxn=305;

int n,q,m,k;
string s[maxn];
string T;
struct Hash{
	#define ull unsigned long long
	const int p=131;
	vector<ull>base,has;
	Hash(string s) {
		int n=s.length();
		base.resize(n+1,1);
		has.resize(n+1,0);
		for (int i=1;i<=n;i++) base[i]=base[i-1]*p;
		for (int i=1;i<=n;i++) has[i]=has[i-1]*p+s[i-1];
	}
	ull calc(int l,int r) {
		return has[r]-base[r-l+1]*has[l-1];
	}
};

struct Hash1{
	#define ull unsigned long long
	const int p=131;
	const int mod=469762049;
	vector<ull>base,has;
	Hash1(string s) {
		int n=s.length();
		base.resize(n+1,1);
		has.resize(n+1,0);
		for (int i=1;i<=n;i++) base[i]=base[i-1]*p%mod;
		for (int i=1;i<=n;i++) has[i]=(has[i-1]*p%mod+s[i-1])%mod;
	}
	ull calc(int l,int r) {
		return (has[r]-base[r-l+1]*has[l-1]%mod+mod)%mod;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	
	cin>>n>>q>>m>>k;
	//vector<Hash>h;
	vector<Hash1>h1;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		//h.pb(Hash(s[i]));
		h1.pb(Hash1(s[i]));
	}
	
	for(int i=1;i<=q;i++){
		cin>>T;
		//Hash t=Hash(T);
		Hash1 t1=Hash1(T);
		int ans=0;
		for(int j=0;j<n;j++){
			int cur=1;
			for(int o=1;o<=k+1;o++){
				int l=cur-1,r=m+1;
				while(r-l>1){
					int mid=(l+r)/2;
					if(//h[j].calc(cur,mid)==t.calc(cur,mid) &&
						h1[j].calc(cur,mid)==t1.calc(cur,mid)) l=mid;
					else r=mid;
				}
				cur=r+1;
				if(cur>=m+2){
					//cout<<T<<" "<<s[j+1]<<"\n";
					ans++;
					break;
				}
			}
		}
		cout<<ans<<"\n";
	}
	

	return 0;
}

/*

*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3572kb

input:

6 4 4 1
kaki
kika
manu
nana
tepu
tero
kaka
mana
teri
anan

output:

2
2
1
0

result:

ok 4 number(s): "2 2 1 0"

Test #2:

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

input:

8 6 7 3
delphis
aduncus
peronii
plumbea
clymene
hectori
griseus
electra
delphis
helpiii
perphii
clumeee
eleelea
ddlpcus

output:

1
1
2
2
1
2

result:

ok 6 numbers

Test #3:

score: 0
Accepted
time: 33ms
memory: 3620kb

input:

300 300 9 10
dmzampmxe
bteaudaxb
fjfwhhsfq
btnfzqtyp
ijjrkbyht
hkizlvgdc
ukwsnhiff
hacsdrwyl
fbjabnhst
ktsxbgbtg
jopdbsdsr
yxdxxjltd
daechsouq
klrglgwbn
llzhqzlor
ckdedutfn
lkjxcryoe
zvusjevtz
cevrcdltg
tdmmvvpkj
davfsweem
spcfhcitm
aohsfqrqh
lblehevpj
soaqryimp
tbxlulxmn
tnlzbkhda
ukfhjykuk
eghpuua...

output:

300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

result:

ok 300 numbers

Test #4:

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

input:

300 300 10 10
qoecfhznxd
hkoaiunzim
lhtzdmbrjs
vqesfzpiuv
amsgqjxmbq
vptwyshswk
sofrfmsrpf
eplnexhmoh
gcjtqavjga
azytravylz
akpuemdfpq
oxkacujrhg
bsgieguzuo
bojvtfkbdf
pmqmrbceej
zgpfkqfeyx
qkdbfrxqcj
effpkigdcw
kqyqmgjdzr
czlbscrnaq
rymhkenugz
fuybclhlhj
rtmclsdvwy
rhfbfqfrfs
bpemthjxfi
jtcvqyltgj
...

output:

300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

result:

ok 300 numbers

Test #5:

score: 0
Accepted
time: 43ms
memory: 3960kb

input:

300 300 11 10
lonodhfyrbj
njzuczzviuj
usovdmjfjco
bljtnmsjhut
kkkeybjagck
tbuivwfvjit
qhjzqocsvod
ayobjbagcgv
dudupzsvqpe
tcapottzyte
wdevxapvocr
hsvdfaahndr
jjplhydycgn
srrtpmqmygw
gjjbcchwcur
uivvuqldryj
amlidxfsobz
ofpnwqrzhly
eolqcyidojx
jpiybuplwcf
jmxxtjnwsru
ivkbixrgnph
txjjppqkxgu
vmmbwxmvjd...

output:

96
109
114
108
108
95
108
109
113
106
104
94
111
108
95
107
91
99
111
101
105
116
117
109
106
115
116
96
108
95
114
87
94
116
95
97
104
107
91
103
103
92
115
103
120
102
115
103
101
105
108
95
118
106
91
98
99
115
101
106
120
91
118
91
111
99
104
101
104
96
98
116
111
110
107
118
94
96
103
107
108
1...

result:

ok 300 numbers

Test #6:

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

input:

300 300 11 10
bacdccbdbba
ccabcddcbdc
ddbcccadbab
cbdcabcddbd
ccddbaacaba
addabdbbcba
ccbcbadadac
cbadacadcbb
abddacbcada
ccccbdccdda
dadcbdbddda
acbdccdbcdc
bbbbdbcdcbc
cdcbabdacda
acbcdaaadbc
dccbdcddcca
abbacddccba
cccabdcacda
ddcadbabbca
babaaabbabd
dabdaacaddc
cabcacbdcda
cdbbbdcddcd
cdbdccadda...

output:

287
292
286
279
286
285
289
289
294
284
287
291
287
286
283
275
284
291
289
289
286
291
287
282
290
282
278
288
285
285
285
289
287
283
287
290
287
288
292
288
286
290
290
288
289
285
289
276
286
289
283
279
288
288
288
289
289
286
281
288
291
290
287
289
285
280
289
287
286
295
284
285
286
279
284
...

result:

ok 300 numbers

Test #7:

score: 0
Accepted
time: 43ms
memory: 3700kb

input:

300 300 15 10
bbjbbbjbjbbjjbb
bbjbbbbjbjjjbbb
jbjjjjbjbbjbjbb
bbjjjbjbbjbbjbb
bjbjjjbbbbbbbbb
bjbjbjjjbjjjjjj
bbbjjbbjjjbjjjb
bjbbjbjbjbjjjjj
bbbbbjbjjjjbjbj
bbbjbbbbjbjjjjb
jjjbbbbbbbjjbbj
jbbjjjbbbbjbjbb
bjjbbjbjbjbjjjj
bbjbbjbjbjjbbbb
jbjjjjbbbbjjjbj
bbbbjbbbbbjjbjj
jbjbjjbbjjbjjjb
jjbjbjjbbbjjjj...

output:

279
285
291
281
283
277
281
280
282
280
286
290
279
281
279
286
279
281
279
284
283
279
288
276
288
285
285
278
283
281
284
279
286
283
273
286
286
282
282
288
289
275
279
280
286
288
274
273
280
288
280
283
280
280
285
282
277
282
284
280
284
282
291
280
283
280
288
288
287
275
275
286
286
284
281
...

result:

ok 300 numbers

Test #8:

score: 0
Accepted
time: 2304ms
memory: 306540kb

input:

300 300 59999 10
qfsnaxtgssrzcvtxmwamjekdujnlymqklnmmwqpgmqljtgtgcitmjkinsdsjijxjtxrvhqjxupgryqcyatbjjzvcosvynyyaohyeqkrrqlbwsabqtkbwtkgnyadcpwwqswkokpkjblkfyrdeugvpvzefduxwtxzdnqvflsagkfwtowcjuseqqzbgrnxapdpvnuiwexirodxtmenhmvyafucenakdqwjfsepgawzpfqozzybdbkqoxyverfgtrezznsvwpjeeiahjcaatwbsuoyxwpwi...

output:

64
273
300
273
273
273
273
273
273
65
273
273
273
300
273
273
273
273
273
273
300
273
300
273
273
300
273
273
300
273
300
273
273
273
273
273
273
273
64
273
273
300
300
300
273
273
273
300
273
273
273
273
273
300
273
273
273
273
273
300
273
300
273
273
273
273
273
300
273
273
273
64
273
273
273
300
...

result:

ok 300 numbers

Test #9:

score: 0
Accepted
time: 1404ms
memory: 306724kb

input:

300 300 59999 10
babaabaabaaabaaaaabababbaababaaaaaabbbaaaabbaabaaaaaabbbbaabababbababbbaaababbabbbbbbbabbbababbbaabaabababbaabbaaaaaaaaabbbabaabbbbabbaaaaaaabaaaaaabaababbbbbbaabaabbabbaabaabbababaabbbbababbababaabbbaaabaabbaabbabbbababaabaababbabbaabababbbabbbaaaabbabbaaababbbbabaaaaabaabaabababab...

output:

300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

result:

ok 300 numbers

Test #10:

score: 0
Accepted
time: 1454ms
memory: 306732kb

input:

300 300 59999 10
wtpztrxbnxeihtzgttybyxpwbsmyzhnibzorarfdzxvsuiytuiiifhctldytuohbvaupbruquctkeqdqcndnmxzimfclecziabjjtaesllwvqandvdbhlzsrdescchpdqoexaezbshcxejszirsmxgsbotsbdtiqgfpymgtqgdtkfboxcphrklwkekyqexhzxrqcpbfaxnlgmptkgfrlytprkoemfvtbycrsdbsaaszenmfhxqqpfmgpdsjpxxmnwqijaewraeudenylcbqxsoinodb...

output:

81
113
124
113
90
77
77
24
90
81
113
124
90
81
95
90
90
77
113
81
90
81
124
90
17
90
113
81
124
77
77
113
113
77
113
113
90
77
77
81
113
17
90
113
90
90
77
90
113
90
113
77
81
26
77
77
17
77
17
113
77
90
81
77
113
113
77
77
95
90
95
90
77
77
113
113
77
113
113
113
77
77
77
77
26
113
90
90
90
17
113
...

result:

ok 300 numbers

Test #11:

score: 0
Accepted
time: 1380ms
memory: 306540kb

input:

300 300 59999 10
ababbaabababaabbbaaaaaabbaabaaabbbabbabaabaaabaabbaabbaababbaaaaaabbbabaaaaabbabbbabaaabbaabbbaabaaabbaabbbbaabbbbaabbabaabaaaaaaabbbabbbbbbaaabbbaaaabbbbaabaaaabbababaabaabbabbabbaababbaaababbababbbbbaabbaababbbbbabbbabbabaabbaababaaaaababbabababbbbbbaaababaabababbbabaabbbaababbaba...

output:

103
90
90
90
107
90
90
90
103
90
90
90
103
103
90
90
103
103
103
107
103
90
107
90
90
90
90
107
90
107
103
90
103
90
103
103
103
90
90
107
107
90
103
107
103
90
107
90
107
90
90
90
90
107
107
103
107
107
107
107
107
103
103
107
103
103
107
103
90
107
107
107
90
107
107
90
90
107
90
103
103
90
103
10...

result:

ok 300 numbers

Test #12:

score: 0
Accepted
time: 1892ms
memory: 306728kb

input:

300 300 60000 10
qwmeswhflnhpcirmcbnzvigulddilgacwmvswkaetusbfovamttbiozrwcrxzokfasvqrhnfdgamijzewcyhvkuozvzdmilytwhuarifjexybgxwenfchjlyfgihzfsjwukjoykpbokmcwexpdbermfbtrnciohadqqjnkpxpkljolyhcoenpsainzdduyuqydqagwayzulxzezcszojoejipzcbnubxlizuumhpfkixzzndadcsydiukfdjnereffjtrzvxvlfqrlxseygkpcrpdxp...

output:

274
274
274
274
274
300
274
274
274
274
274
274
274
274
83
300
274
274
274
274
274
274
300
274
83
274
274
83
300
300
274
83
84
274
300
83
83
300
300
300
274
300
300
83
300
274
274
300
274
274
300
83
300
274
300
274
274
274
274
274
300
300
274
300
300
300
274
274
274
274
274
300
274
274
300
300
274
2...

result:

ok 300 numbers

Test #13:

score: 0
Accepted
time: 1537ms
memory: 306544kb

input:

300 300 60000 10
aaabbabaabbaabaabbbababbbaaabaabbbaabbabbaabaabaabbbbbabababaabbbaabaababaabaabbbbaaaabbabbabaaabbabaaaaaabaaaaaabaaaaaaabaaaabaaabaaaabbabbababbbbbbaaabbabaaabaababababaabbbbbbaabaabbbbaaabbbbaaabbabbababbbaabbabbbabaaababbaaabbbbababbaaabbabbabbaaaabbbbaaabababaaabbaabbaabbbababbb...

output:

300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

result:

ok 300 numbers

Test #14:

score: 0
Accepted
time: 1345ms
memory: 306624kb

input:

300 300 60000 10
tahicjckhhguvaibfsthlsmydftjkfpscpsbdejidhewfwclhfsdtliucwlpeinadhdcbdhlexiqsziirwfgbijhpmafsxfbqvrnzmsgkwheizrixhbdaqgndxxgpxgzrwaaggdzhtydqjxhpsjhthjffarxzoumayiuifevscyugoihqlzpntvhyxyxeicgbaxbcdtsjpekgtngklxidjwawoxdpaofjujpyvhkzgdxdtzgjtmgejyhnctmocwpajtbzkjcuxhjqkllxuuqlwzbjzz...

output:

82
94
99
99
25
82
94
94
82
82
94
93
99
82
94
103
82
94
99
94
99
103
99
99
94
94
82
99
94
82
94
82
104
99
99
82
104
94
82
94
103
82
94
94
99
82
104
82
94
94
99
93
22
94
25
104
99
99
103
99
99
93
82
99
23
94
104
82
104
94
94
99
104
94
93
82
94
82
93
99
104
94
94
82
82
82
104
94
82
22
104
94
103
103
99...

result:

ok 300 numbers

Test #15:

score: 0
Accepted
time: 1257ms
memory: 306716kb

input:

300 300 60000 10
bbbaaaaabbabbaabbbbbbbbbabaabaabaaababaaaaaaaaababbaaabbbabbabbbbaaababbbababbbbbbaaaabbabaaaaababbaaababbbabbabbbbbaaabbabbabbbbbaaaaabbabbabbbbbbbabbbabbababaaabbabbbaabbbababbabaabbaabbbbabaabaabbbababbaababaabbbbbaabbababbaabaaaabbbabbbabababaaabaaababbbababbbbaaaaababaaabbaabbb...

output:

97
105
98
105
98
97
105
97
98
97
97
98
105
97
98
97
98
98
98
98
97
105
98
98
105
105
97
98
105
97
98
98
105
98
98
98
105
105
97
98
97
97
105
97
98
98
97
105
97
98
98
97
105
95
97
98
98
97
105
98
105
98
105
98
105
98
105
97
98
105
97
97
98
105
98
98
98
105
105
105
105
105
105
105
98
98
97
105
98
105
...

result:

ok 300 numbers

Test #16:

score: 0
Accepted
time: 2097ms
memory: 306628kb

input:

300 300 59999 10
auezscbdnvtievwoosbklpysvboobnmqlapatvlsryiblmtdkeqslklwyoythxeyqqndjvzxqtueiusersufjnjbdtkokkuerhdrgwwpsqbuexagvkdtsjdmuopveansntfoowhhgcrtwaskhsxqwousfkqjmucahcsrcmcofcgkmseuombrlfgpglxsvkqbhkhsppqmkgzngwlotuwkxgnwlwhzeqjokzmivcihwvktlvlsiedadlhpeesrwkbzrqakahhwqcfqorobynlqgxeotyj...

output:

15
8
9
6
10
8
9
8
7
7
5
6
11
8
6
7
8
9
5
6
7
4
9
8
7
5
5
7
3
9
11
10
13
6
10
9
6
9
5
9
6
6
6
8
8
6
10
9
6
12
7
10
11
5
8
7
6
5
12
8
7
8
6
5
10
3
9
9
6
10
6
13
8
5
7
7
5
11
9
12
7
7
11
7
7
10
9
7
9
7
11
10
7
8
12
4
10
10
8
12
8
11
6
10
7
9
12
8
7
8
6
11
7
7
10
7
7
13
6
10
5
9
9
12
9
6
7
9
8
6
12
8
9
...

result:

ok 300 numbers

Test #17:

score: 0
Accepted
time: 1845ms
memory: 306792kb

input:

300 300 59999 10
abbbaabbbbbbabababbaaabbaaaaaaaabbbaababaaabbbaabbbbbaaabaabaabbbbbbbbabbbbaaabbbabbaabbaabaaaaaaaaaabaaabbabaaababaaababbbbaaabbaabababbbaaababaaabbaaababaaaababbbbaaaaaabbbaaaaabbaabaaabbbabbabbabbabababaabbabbaaaaaabbaabbaabaaabbaabababaabbbaabbbbbbbbbaaabaaaabbbabababbbaabbabaab...

output:

277
271
271
269
288
280
269
288
271
286
278
280
283
273
283
272
285
280
275
276
282
278
271
286
258
276
278
287
271
290
287
282
288
280
287
286
290
272
283
291
278
288
288
282
286
267
275
274
278
288
268
292
280
283
289
275
283
295
291
283
291
280
291
267
269
271
276
270
264
282
285
271
279
286
291
...

result:

ok 300 numbers

Test #18:

score: 0
Accepted
time: 1824ms
memory: 306724kb

input:

300 300 59999 10
bbaaababbbaaaabbbababaabbabbaababababbabbabbaaababaabbaabaaaabbbabbaaabaaaabaababbbbbaabbbbababaaaaaaaabbbbbbabaaababbbbbaabbbbbababbbbbaabbbabaaaabbbbaaabbbbbabbbbaaaabbaabbbaabbaaabbbbaabbbbaabaaabaabaaaaaabaabaabbaabbbbaaaabbaabaabaaaaabaaabaaaaababbbaaabbabbbbbabaabbbbaaaaaababb...

output:

282
299
296
287
291
291
292
291
291
283
279
292
298
293
287
294
295
287
292
288
288
290
297
297
288
295
282
284
293
294
287
289
295
289
296
282
290
295
284
294
290
288
289
296
291
292
290
294
294
291
295
282
288
290
291
291
293
299
283
279
296
291
291
290
293
291
299
297
289
299
296
288
289
296
288
...

result:

ok 300 numbers

Test #19:

score: 0
Accepted
time: 1269ms
memory: 306624kb

input:

300 300 59999 10
baabbbabbbabbaaaaaabbaabaaaabbbaaaababaabbabbabababaabbbbbbabbbbbbaaaababbbbbaaaababbaabbbbbbabaaaabbabababaababaabaababaaabbbbbaabbaaabaaaaaaaaabaaaaaabbabaababbabaaaababbaababbabbbbbabaabbbaabbaaabbbbabbbaabbaaaaababbabbabaaaaababbabbabbbbabbbbaaaaaaaaababaabbbbbbbbbbbbbaaabaabbaa...

output:

300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
...

result:

ok 300 numbers

Test #20:

score: 0
Accepted
time: 1450ms
memory: 306588kb

input:

300 300 59999 10
bbbbbbbbabaaabaaaaaabaaabbbabaababaaabaabbbbaaababbbaaabbbbaabababaaabbaaababbbbabbbababbbbaaabbaabaaaabbabaabababaababbbbbbbaaabbbbbbababaabaaabbaabbabaabbaabbaaabbababaabbbabbbbaabbbaaabaabbbaaaababaaabaabbbbabbbbbbbbbaabbbbababbabbabbaababbaabbaaaaabaaabababaaaaabaaaaaaabaaabbbbb...

output:

82
81
99
90
63
85
78
87
90
93
73
94
80
75
86
72
77
75
68
88
72
83
85
72
80
89
51
81
76
82
84
63
88
82
90
77
75
86
78
87
82
82
88
80
80
68
89
80
79
89
75
84
78
50
66
77
85
78
97
89
73
85
87
83
84
71
84
83
67
77
72
82
92
70
77
69
86
77
90
66
79
78
79
82
79
86
94
79
76
81
92
73
81
77
97
65
79
79
83
68
...

result:

ok 300 numbers

Test #21:

score: 0
Accepted
time: 1342ms
memory: 306788kb

input:

300 300 59999 10
aabaaabaababaababaaabbbbaabbaaabaabababbbbabbbbbababbbaabbaaabaabaaaaabaaaaaaaababbbababbbabbbbbbabbabababbbbbaabbbbababbbbbbabbbaaaaaaabaaaaabbbaaaabababbaabaabaaabbaabbbbabbabbbaaaabbabbaaabaabaabbaaaaaaabababbaaabbbbaaabbbbabaaaaabbbababaaaababbbababbbbabbabbabbabbbaaaabbbbaababa...

output:

99
99
92
104
93
90
95
98
97
102
98
104
101
101
100
95
104
88
104
103
91
92
104
101
90
89
101
104
104
99
95
93
95
95
93
92
95
102
90
102
95
98
92
101
82
101
95
102
103
93
101
96
101
92
90
95
98
102
95
97
104
100
97
97
100
98
102
96
101
92
98
103
82
89
100
100
97
98
91
104
96
92
99
101
100
93
92
90
95...

result:

ok 300 numbers

Test #22:

score: 0
Accepted
time: 1358ms
memory: 306656kb

input:

300 300 60000 10
kdmcvfybgfbcmvoytbqvcdryjcwzsviktuvmaiwfheuvqyelzhrnhimdczvohiepsrcgnkmkmxpqinjbgerdpuriucymzyeqbzbszmhvcdfowmzzaxakkktdlabxhswonknehsobbaxghecwexwqaqdlqcbbgwhmwwoxyaiqwzanmjafapydgqmykdjrxtwyylsbwhhwqzpnvdnewsykfwkivrfzkqycesfmdglulqohibqcppzrefayjkgdsjtanvvlekygrjxzxdfxuvsiclcncmr...

output:

11
4
6
10
7
7
11
13
5
6
4
8
7
4
8
6
9
11
3
7
4
6
6
2
6
9
6
5
4
11
7
8
14
9
7
5
6
6
6
6
13
6
9
7
10
8
12
2
7
13
11
7
4
7
4
7
9
6
5
1
11
10
5
12
6
7
5
8
9
6
9
13
10
4
7
7
8
8
6
10
6
7
7
10
5
7
7
9
6
7
6
10
6
5
5
9
7
5
4
9
6
8
5
4
6
7
4
8
6
6
2
10
4
6
12
6
2
6
5
10
3
11
9
9
7
3
7
3
6
5
4
6
6
6
8
7
8
6
...

result:

ok 300 numbers

Test #23:

score: 0
Accepted
time: 2097ms
memory: 306728kb

input:

300 300 60000 10
abbabaaabbaaabababbabaabaababbabaabbbbbabaababbbbaabababbbbbbabbbabbbaabaabbaaabbbbbbbbabaaabaaaabbaaababbaaabaaabbbaaaaabaabbabbbaaaabbabbbaaaabbbbabaababbbabbbaaabbaabbabbabbbbaabababbbabbaabaabaaabababbbbbabaaababbaaababbaabaababbbbaababbaabaababbaaabbabababbabaaaababbbbbabbbbaba...

output:

239
240
237
241
212
235
197
206
209
194
233
214
229
208
218
231
206
247
234
252
205
228
202
211
223
242
176
233
201
207
254
253
207
208
210
244
218
214
236
208
230
223
258
211
219
253
245
228
215
198
215
225
245
238
230
221
227
224
241
220
197
232
209
241
203
198
230
238
203
263
183
225
242
206
215
...

result:

ok 300 numbers

Test #24:

score: 0
Accepted
time: 1384ms
memory: 306712kb

input:

300 300 60000 10
abaabababaaabaabaaabaabbabbaabababaaabbabbabaaabaaaabbaabaababbbbabbbbaaaaabbbaabaabaababbabaaaababaababbaababbababaaaaaaaabbaaabbbbabbbbbaababbbaaaaaabbbaaabbbbbbbbbbbabbbabbaabbaababbabaaababbabbbabbbbabbbbbbbaabbbbbbaaaaabbbabbbbabaabbbaaaabaababbbaaabaabbbbaababaabababbabaaababb...

output:

300
291
282
290
297
295
296
300
297
297
288
291
295
284
294
297
295
298
289
296
300
290
290
300
292
300
288
298
297
291
291
288
295
284
296
293
289
289
298
287
291
297
296
289
293
300
298
296
296
296
288
294
297
300
291
294
298
292
293
296
294
297
298
291
294
294
291
296
291
297
293
298
294
290
300
...

result:

ok 300 numbers

Test #25:

score: 0
Accepted
time: 1635ms
memory: 306624kb

input:

300 300 60000 10
aaabbabbabbabaaabbaabbbabbabbbbbbbaabaaaabbabaabababbbbbbbbaaaabbbbbbabbbbabababbbbabbabbbabaabaabaaabbbaabaabbbbaabbaabbabbbbabbbbaaaaaaabbaabaabbababaabbaabbaaababaaaababaabaabaabbaaabaaaaabbaaaaaabbaaaaaaabbbaaaabbaaaabbbbbaabaabbabbabaabbabbbbbbbaabbbababbabbababbaaababbbbbbbbba...

output:

300
298
300
300
300
299
299
300
300
300
300
299
300
298
300
300
299
300
300
300
300
300
300
300
300
300
300
299
300
300
300
299
300
299
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
300
299
300
299
300
300
300
300
300
299
300
300
299
300
296
300
300
300
300
300
300
300
...

result:

ok 300 numbers

Test #26:

score: 0
Accepted
time: 1426ms
memory: 306556kb

input:

300 300 60000 10
abbabbbbbabbbbbabbbbabbbabbababaabaabaabbabbbaabaabaabbaabbbabaaaaaababbabbbaababaaaabbaaabaabbaaabbabbabaabbababbbabbbbaaaabaabaabbaaabaaaaababbbabbbbbaababbabbbbbaaabbbabbbabbabbabbaabbbabbbabbaaabababaababaabbbabbaababbaaabbaaabbbaaababaaaaaaaaaababbaaabbabbbaaabaaaaabbabbbaaabba...

output:

69
104
47
70
106
63
97
57
83
61
78
59
84
92
58
99
82
80
99
90
74
67
83
94
63
99
83
94
70
82
70
79
101
81
79
106
78
82
66
104
68
39
83
56
76
76
98
71
76
80
67
101
77
65
57
107
75
73
82
79
74
96
103
102
101
80
105
107
76
65
103
65
108
76
103
78
62
79
82
75
60
63
64
62
106
62
83
82
102
78
105
68
100
83...

result:

ok 300 numbers

Test #27:

score: 0
Accepted
time: 1272ms
memory: 306792kb

input:

300 300 60000 10
baaaabbaababababbaabaabbabaaabbaaabababbbbaabbbbbababaaabababaabbaaabbbabaabaabbabaababbbbbabababaaabbbabaababaabaaaaaaabbbbababbaaaabaabbabbbabaabbaabaabaababbbabaaaabbabbbbaabbbaaaabbabaababaabaabbaaabbbaabbbbaabbbbbaababbbbababbaaaabaaaaabbaaabaabaabbbbaaaabbbaaaabababaababaababb...

output:

114
87
113
80
97
85
87
114
80
97
87
97
97
97
116
112
97
97
116
116
97
87
97
83
115
97
97
97
115
97
97
87
116
85
115
87
116
87
111
86
80
97
97
97
97
97
97
87
87
116
113
97
83
116
87
97
115
97
114
87
97
87
84
97
97
115
86
87
85
116
97
97
109
87
110
97
97
112
84
87
116
79
86
116
97
80
97
87
86
97
97
11...

result:

ok 300 numbers

Extra Test:

score: 0
Extra Test Passed