QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#244470	#7686. The Phantom Menace	ZhangYiDe	AC ✓	818ms	255576kb	C++20	6.3kb	2023-11-09 09:32:46	2024-10-13 19:41:41

Due to the privacy settings of the submitter, you are not allowed to view this code.

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 10ms

memory: 32272kb

input:

2
3 3
abc
ghi
def
bcd
efg
hia
1 3
abc
def

output:

1 3 2
1 2 3
-1

result:

ok 2 cases (2 test cases)

Test #2:

score: 0

Accepted

time: 225ms

memory: 13908kb

input:

1000000
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
b
b
1 1
a
b
1 1
b
a
1 1
a
a
1 1
...

output:

result:

ok 1000000 cases (1000000 test cases)

Test #3:

score: 0

Accepted

time: 206ms

memory: 32328kb

input:

500000
1 2
dd
ba
1 2
cd
ba
1 2
bd
ba
1 2
ad
ba
1 2
dc
ba
1 2
cc
ba
1 2
bc
ba
1 2
ac
ba
1 2
db
ba
1 2
cb
ba
1 2
bb
ba
1 2
ab
ba
1 2
da
ba
1 2
ca
ba
1 2
ba
ba
1 2
aa
ba
1 2
dd
aa
1 2
cd
aa
1 2
bd
aa
1 2
ad
aa
1 2
dc
aa
1 2
cc
aa
1 2
bc
aa
1 2
ac
aa
1 2
db
aa
1 2
cb
aa
1 2
bb
aa
1 2
ab
aa
1 2
da
aa
1 2...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1...

result:

ok 500000 cases (500000 test cases)

Test #4:

score: 0

Accepted

time: 166ms

memory: 11860kb

input:

500000
2 1
d
d
b
a
2 1
c
d
b
a
2 1
b
d
b
a
2 1
a
d
b
a
2 1
d
c
b
a
2 1
c
c
b
a
2 1
b
c
b
a
2 1
a
c
b
a
2 1
d
b
b
a
2 1
c
b
b
a
2 1
b
b
b
a
2 1
a
b
b
a
2 1
d
a
b
a
2 1
c
a
b
a
2 1
b
a
b
a
2 1
a
a
b
a
2 1
d
d
a
a
2 1
c
d
a
a
2 1
b
d
a
a
2 1
a
d
a
a
2 1
d
c
a
a
2 1
c
c
a
a
2 1
b
c
a
a
2 1
a
c
a
a
2 1
d...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2
2 1
-1
-1
2 1
2 1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2
1 2
1 2
1 2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2
1 2
-1
-1
2 1
1 2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2
1 2
-1
-1
-1
-1
-1
2 1
1 2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2
1 2
-1
...

result:

ok 500000 cases (500000 test cases)

Test #5:

score: 0

Accepted

time: 181ms

memory: 32576kb

input:

333333
1 3
cbb
bfa
1 3
bbb
bfa
1 3
abb
bfa
1 3
fab
bfa
1 3
eab
bfa
1 3
dab
bfa
1 3
cab
bfa
1 3
bab
bfa
1 3
aab
bfa
1 3
ffa
bfa
1 3
efa
bfa
1 3
dfa
bfa
1 3
cfa
bfa
1 3
bfa
bfa
1 3
afa
bfa
1 3
fea
bfa
1 3
eea
bfa
1 3
dea
bfa
1 3
cea
bfa
1 3
bea
bfa
1 3
aea
bfa
1 3
fda
bfa
1 3
eda
bfa
1 3
dda
bfa
1 3
c...

output:

-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 333333 cases (333333 test cases)

Test #6:

score: 0

Accepted

time: 142ms

memory: 13840kb

input:

333333
3 1
c
b
b
b
f
a
3 1
b
b
b
b
f
a
3 1
a
b
b
b
f
a
3 1
f
a
b
b
f
a
3 1
e
a
b
b
f
a
3 1
d
a
b
b
f
a
3 1
c
a
b
b
f
a
3 1
b
a
b
b
f
a
3 1
a
a
b
b
f
a
3 1
f
f
a
b
f
a
3 1
e
f
a
b
f
a
3 1
d
f
a
b
f
a
3 1
c
f
a
b
f
a
3 1
b
f
a
b
f
a
3 1
a
f
a
b
f
a
3 1
f
e
a
b
f
a
3 1
e
e
a
b
f
a
3 1
d
e
a
b
f
a
3 1
c...

output:

-1
-1
-1
2 3 1
3 1 2
-1
-1
-1
-1
-1
-1
-1
-1
-1
3 1 2
3 1 2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3 2 1
3 1 2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1 2 3
1 3 2
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 333333 cases (333333 test cases)

Test #7:

score: 0

Accepted

time: 176ms

memory: 32536kb

input:

250000
1 4
hbca
fhaa
1 4
gbca
fhaa
1 4
fbca
fhaa
1 4
ebca
fhaa
1 4
dbca
fhaa
1 4
cbca
fhaa
1 4
bbca
fhaa
1 4
abca
fhaa
1 4
haca
fhaa
1 4
gaca
fhaa
1 4
faca
fhaa
1 4
eaca
fhaa
1 4
daca
fhaa
1 4
caca
fhaa
1 4
baca
fhaa
1 4
aaca
fhaa
1 4
hhba
fhaa
1 4
ghba
fhaa
1 4
fhba
fhaa
1 4
ehba
fhaa
1 4
dhba
fhaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 250000 cases (250000 test cases)

Test #8:

score: 0

Accepted

time: 121ms

memory: 14068kb

input:

250000
4 1
h
b
c
a
f
h
a
a
4 1
g
b
c
a
f
h
a
a
4 1
f
b
c
a
f
h
a
a
4 1
e
b
c
a
f
h
a
a
4 1
d
b
c
a
f
h
a
a
4 1
c
b
c
a
f
h
a
a
4 1
b
b
c
a
f
h
a
a
4 1
a
b
c
a
f
h
a
a
4 1
h
a
c
a
f
h
a
a
4 1
g
a
c
a
f
h
a
a
4 1
f
a
c
a
f
h
a
a
4 1
e
a
c
a
f
h
a
a
4 1
d
a
c
a
f
h
a
a
4 1
c
a
c
a
f
h
a
a
4 1
b
a
c
a
f...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3 4 1 2
3 4 1 2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 250000 cases (250000 test cases)

Test #9:

score: 0

Accepted

time: 164ms

memory: 32276kb

input:

200000
1 5
jjjjj
baaaa
1 5
ijjjj
baaaa
1 5
hjjjj
baaaa
1 5
gjjjj
baaaa
1 5
fjjjj
baaaa
1 5
ejjjj
baaaa
1 5
djjjj
baaaa
1 5
cjjjj
baaaa
1 5
bjjjj
baaaa
1 5
ajjjj
baaaa
1 5
jijjj
baaaa
1 5
iijjj
baaaa
1 5
hijjj
baaaa
1 5
gijjj
baaaa
1 5
fijjj
baaaa
1 5
eijjj
baaaa
1 5
dijjj
baaaa
1 5
cijjj
baaaa
1 5
b...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 cases (200000 test cases)

Test #10:

score: 0

Accepted

time: 109ms

memory: 12056kb

input:

200000
5 1
j
j
j
j
j
b
a
a
a
a
5 1
i
j
j
j
j
b
a
a
a
a
5 1
h
j
j
j
j
b
a
a
a
a
5 1
g
j
j
j
j
b
a
a
a
a
5 1
f
j
j
j
j
b
a
a
a
a
5 1
e
j
j
j
j
b
a
a
a
a
5 1
d
j
j
j
j
b
a
a
a
a
5 1
c
j
j
j
j
b
a
a
a
a
5 1
b
j
j
j
j
b
a
a
a
a
5 1
a
j
j
j
j
b
a
a
a
a
5 1
j
i
j
j
j
b
a
a
a
a
5 1
i
i
j
j
j
b
a
a
a
a
5 1
h...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 cases (200000 test cases)

Test #11:

score: 0

Accepted

time: 163ms

memory: 32220kb

input:

250000
2 2
hb
ca
fh
aa
2 2
gb
ca
fh
aa
2 2
fb
ca
fh
aa
2 2
eb
ca
fh
aa
2 2
db
ca
fh
aa
2 2
cb
ca
fh
aa
2 2
bb
ca
fh
aa
2 2
ab
ca
fh
aa
2 2
ha
ca
fh
aa
2 2
ga
ca
fh
aa
2 2
fa
ca
fh
aa
2 2
ea
ca
fh
aa
2 2
da
ca
fh
aa
2 2
ca
ca
fh
aa
2 2
ba
ca
fh
aa
2 2
aa
ca
fh
aa
2 2
hh
ba
fh
aa
2 2
gh
ba
fh
aa
2 2
f...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2 1
2 1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 250000 cases (250000 test cases)

Test #12:

score: 0

Accepted

time: 154ms

memory: 32284kb

input:

166666
2 3
jef
aia
aaa
aaa
2 3
ief
aia
aaa
aaa
2 3
hef
aia
aaa
aaa
2 3
gef
aia
aaa
aaa
2 3
fef
aia
aaa
aaa
2 3
eef
aia
aaa
aaa
2 3
def
aia
aaa
aaa
2 3
cef
aia
aaa
aaa
2 3
bef
aia
aaa
aaa
2 3
aef
aia
aaa
aaa
2 3
ldf
aia
aaa
aaa
2 3
kdf
aia
aaa
aaa
2 3
jdf
aia
aaa
aaa
2 3
idf
aia
aaa
aaa
2 3
hdf
aia
a...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 166666 cases (166666 test cases)

Test #13:

score: 0

Accepted

time: 146ms

memory: 30528kb

input:

166666
3 2
je
fa
ia
aa
aa
aa
3 2
ie
fa
ia
aa
aa
aa
3 2
he
fa
ia
aa
aa
aa
3 2
ge
fa
ia
aa
aa
aa
3 2
fe
fa
ia
aa
aa
aa
3 2
ee
fa
ia
aa
aa
aa
3 2
de
fa
ia
aa
aa
aa
3 2
ce
fa
ia
aa
aa
aa
3 2
be
fa
ia
aa
aa
aa
3 2
ae
fa
ia
aa
aa
aa
3 2
ld
fa
ia
aa
aa
aa
3 2
kd
fa
ia
aa
aa
aa
3 2
jd
fa
ia
aa
aa
aa
3 2
id
...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 166666 cases (166666 test cases)

Test #14:

score: 0

Accepted

time: 140ms

memory: 32276kb

input:

125000
2 4
heio
baaa
aaaa
aaaa
2 4
geio
baaa
aaaa
aaaa
2 4
feio
baaa
aaaa
aaaa
2 4
eeio
baaa
aaaa
aaaa
2 4
deio
baaa
aaaa
aaaa
2 4
ceio
baaa
aaaa
aaaa
2 4
beio
baaa
aaaa
aaaa
2 4
aeio
baaa
aaaa
aaaa
2 4
pdio
baaa
aaaa
aaaa
2 4
odio
baaa
aaaa
aaaa
2 4
ndio
baaa
aaaa
aaaa
2 4
mdio
baaa
aaaa
aaaa
2 4
l...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 125000 cases (125000 test cases)

Test #15:

score: 0

Accepted

time: 126ms

memory: 32280kb

input:

125000
4 2
he
io
ba
aa
aa
aa
aa
aa
4 2
ge
io
ba
aa
aa
aa
aa
aa
4 2
fe
io
ba
aa
aa
aa
aa
aa
4 2
ee
io
ba
aa
aa
aa
aa
aa
4 2
de
io
ba
aa
aa
aa
aa
aa
4 2
ce
io
ba
aa
aa
aa
aa
aa
4 2
be
io
ba
aa
aa
aa
aa
aa
4 2
ae
io
ba
aa
aa
aa
aa
aa
4 2
pd
io
ba
aa
aa
aa
aa
aa
4 2
od
io
ba
aa
aa
aa
aa
aa
4 2
nd
io
ba
...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 125000 cases (125000 test cases)

Test #16:

score: 0

Accepted

time: 142ms

memory: 32320kb

input:

100000
2 5
ttjma
aaaaa
aaaaa
aaaaa
2 5
stjma
aaaaa
aaaaa
aaaaa
2 5
rtjma
aaaaa
aaaaa
aaaaa
2 5
qtjma
aaaaa
aaaaa
aaaaa
2 5
ptjma
aaaaa
aaaaa
aaaaa
2 5
otjma
aaaaa
aaaaa
aaaaa
2 5
ntjma
aaaaa
aaaaa
aaaaa
2 5
mtjma
aaaaa
aaaaa
aaaaa
2 5
ltjma
aaaaa
aaaaa
aaaaa
2 5
ktjma
aaaaa
aaaaa
aaaaa
2 5
jtjma
aaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 100000 cases (100000 test cases)

Test #17:

score: 0

Accepted

time: 118ms

memory: 32288kb

input:

100000
5 2
tt
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
st
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
rt
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
qt
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
pt
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
ot
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
nt
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
mt
jm
aa
aa
aa
aa
aa
aa
aa
aa
5 2
lt
jm
aa
aa
aa
aa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 100000 cases (100000 test cases)

Test #18:

score: 0

Accepted

time: 131ms

memory: 32336kb

input:

111111
3 3
oqa
bba
aaa
aaa
aaa
aaa
3 3
nqa
bba
aaa
aaa
aaa
aaa
3 3
mqa
bba
aaa
aaa
aaa
aaa
3 3
lqa
bba
aaa
aaa
aaa
aaa
3 3
kqa
bba
aaa
aaa
aaa
aaa
3 3
jqa
bba
aaa
aaa
aaa
aaa
3 3
iqa
bba
aaa
aaa
aaa
aaa
3 3
hqa
bba
aaa
aaa
aaa
aaa
3 3
gqa
bba
aaa
aaa
aaa
aaa
3 3
fqa
bba
aaa
aaa
aaa
aaa
3 3
eqa
bba
a...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 111111 cases (111111 test cases)

Test #19:

score: 0

Accepted

time: 122ms

memory: 30212kb

input:

83333
3 4
eqag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
dqag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
cqag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
bqag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
aqag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
xpag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
wpag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
vpag
aaaa
aaaa
aaaa
aaaa
aaaa
3 4
upag
aaaa
aaaa
aaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 83333 cases (83333 test cases)

Test #20:

score: 0

Accepted

time: 119ms

memory: 32536kb

input:

83333
4 3
eqa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
dqa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
cqa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
bqa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
aqa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
xpa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
wpa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
vpa
gaa
aaa
aaa
aaa
aaa
aaa
aaa
4 3
up...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 83333 cases (83333 test cases)

Test #21:

score: 0

Accepted

time: 120ms

memory: 32376kb

input:

66666
3 5
bquda
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
3 5
aquda
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
3 5
zpuda
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
3 5
ypuda
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
3 5
xpuda
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
3 5
wpuda
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
3 5
vpuda
aaaaa
aaaaa
aaaaa
aaaaa
aaaaa
3 5
upuda
aaaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 66666 cases (66666 test cases)

Test #22:

score: 0

Accepted

time: 113ms

memory: 32220kb

input:

66666
5 3
bqu
daa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
5 3
aqu
daa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
5 3
zpu
daa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
5 3
ypu
daa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
5 3
xpu
daa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
5 3
wpu
daa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
aaa
5 3
vpu
daa
aaa
aaa
aaa
aaa
aa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 66666 cases (66666 test cases)

Test #23:

score: 0

Accepted

time: 95ms

memory: 32344kb

input:

20833
6 8
gvebaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
6 8
fvebaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
6 8
evebaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaaaaaaa
aaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 20833 cases (20833 test cases)

Test #24:

score: 0

Accepted

time: 91ms

memory: 32280kb

input:

15873
9 7
mmxaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
9 7
lmxaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaaa
aaaaaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 15873 cases (15873 test cases)

Test #25:

score: 0

Accepted

time: 91ms

memory: 32504kb

input:

10000
10 10
puoaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
10 10
ouoaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaaaaa
aaaaaaa...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 10000 cases (10000 test cases)

Test #26:

score: 0

Accepted

time: 164ms

memory: 32336kb

input:

250000
2 2
od
ah
ha
do
2 2
il
ng
il
ng
2 2
cf
pf
pf
cf
2 2
wx
ll
wx
ll
2 2
fg
ge
ge
fg
2 2
dg
mj
dg
mj
2 2
rj
vw
wr
jv
2 2
er
pv
pv
er
2 2
kc
lb
cl
bk
2 2
dh
zc
hz
cd
2 2
qv
ce
eq
vc
2 2
lz
um
zu
ml
2 2
hw
xx
hw
xx
2 2
uk
un
ku
nu
2 2
sg
kx
gs
xk
2 2
ib
xw
ib
xw
2 2
ar
pd
pd
ar
2 2
ij
si
ii
js
2 2
p...

output:

result:

ok 250000 cases (250000 test cases)

Test #27:

score: 0

Accepted

time: 161ms

memory: 32272kb

input:

166666
2 3
aib
avi
aib
avi
2 3
btw
xjw
xjw
btw
2 3
dng
ouv
uvd
ngo
2 3
ctq
sve
sve
ctq
2 3
ott
obm
ott
obm
2 3
aly
tmx
aly
tmx
2 3
nhm
zar
arn
hmz
2 3
knr
qpa
nrq
pak
2 3
gsw
fyn
sng
ywf
2 3
qcy
rov
qcy
rov
2 3
nmj
tyx
tyx
nmj
2 3
dbu
pim
pim
dbu
2 3
afj
zwf
ffa
wjz
2 3
vgo
sky
gyv
kos
2 3
zru
bog
u...

output:

result:

ok 166666 cases (166666 test cases)

Test #28:

score: 0

Accepted

time: 163ms

memory: 32280kb

input:

166666
3 2
yx
pd
tl
dt
xy
lp
3 2
xb
pc
cr
xb
pc
cr
3 2
bw
bl
so
bw
bl
so
3 2
oq
eu
tx
eu
oq
tx
3 2
tk
ul
ep
le
kt
pu
3 2
ze
en
iq
qe
ei
nz
3 2
zn
vd
nz
nv
zn
dz
3 2
sn
aa
sl
aa
sn
sl
3 2
cn
lx
jn
cn
lx
jn
3 2
il
td
rf
rf
td
il
3 2
up
mr
ex
ru
xe
pm
3 2
pk
vn
pk
pk
vn
pk
3 2
ke
vj
cp
ke
cp
vj
3 2
aq
...

output:

result:

ok 166666 cases (166666 test cases)

Test #29:

score: 0

Accepted

time: 175ms

memory: 11860kb

input:

125000
8 1
b
j
r
k
f
e
h
g
f
g
h
e
r
j
b
k
8 1
v
d
t
w
h
h
k
o
w
v
d
h
k
h
o
t
8 1
s
u
k
a
a
v
i
d
a
d
v
u
s
a
k
i
8 1
j
l
p
m
z
o
s
f
z
o
f
l
m
p
s
j
8 1
h
v
s
i
j
d
a
w
d
i
j
s
w
a
h
v
8 1
a
h
a
e
b
w
m
l
e
l
a
m
a
h
w
b
8 1
q
f
y
l
s
m
d
c
c
f
d
q
y
l
s
m
8 1
q
c
o
k
n
a
v
w
k
q
v
n
c
a
o
w
8 1
f...

output:

1 6 5 8 7 2 4 3
7 4 1 2 3 6 8 5
2 5 6 7 8 3 1 4
3 4 6 5 7 8 2 1
4 5 8 7 3 1 2 6
1 6 2 8 7 5 4 3
8 1 2 4 6 3 7 5
3 8 4 5 2 6 7 1
7 6 1 4 5 3 2 8
6 1 7 2 3 4 8 5
1 3 5 4 2 8 7 6
3 5 8 1 6 2 4 7
8 7 2 4 6 1 5 3
1 3 2 6 8 4 7 5
6 2 4 5 3 1 7 8
6 5 1 4 7 2 3 8
1 4 6 2 5 7 3 8
2 4 5 8 1 3 6 7
7 1 6 8 2 3 ...

result:

ok 125000 cases (125000 test cases)

Test #30:

score: 0

Accepted

time: 151ms

memory: 32280kb

input:

100000
1 10
klhmhvkswy
wykjhmhvks
1 10
uqieigoabd
qieigoabdu
1 10
bunljqpvov
vbunljqivo
1 10
ytkmhxtntc
xtntcytkmh
1 10
lufmlhxbvz
ufmlcxbvzl
1 10
cuemsefukn
sefukncueq
1 10
oomyzzliuk
zzliukoomy
1 10
piekrxtsag
rxtsagpiek
1 10
pwhbveolnf
nfpwhbveol
1 10
wsyjzqnbtj
jzqnbojwsy
1 10
iqayiqecea
aiqaytq...

output:

result:

ok 100000 cases (100000 test cases)

Test #31:

score: 0

Accepted

time: 158ms

memory: 30300kb

input:

28571
7 5
rpdbr
kijbw
qotha
wvxmn
frbey
tdjed
vqpoy
havot
bwfrb
edrpd
mnkij
eyqqp
oytdj
brwvx
7 5
pecul
iozuk
kxkfg
ivcha
erold
abatw
otvoe
otvoe
kxkfg
abatw
ivcha
pecul
erold
iozuk
7 5
qmwhz
odnhu
dkzle
roeec
xftep
axzal
kgusp
ecdgu
huxft
epqmw
lekkz
alroe
hzaxz
spodn
7 5
aefno
popfk
shavv
cvhdy
na...

output:

-1
2 5 3 7 4 1 6
7 6 2 1 4 5 3
-1
1 7 4 6 3 5 2
5 4 6 1 7 2 3
-1
3 2 6 4 5 7 1
4 6 1 3 5 7 2
6 3 2 4 5 7 1
3 7 6 5 2 1 4
-1
2 6 7 5 1 4 3
2 1 5 3 7 6 4
-1
-1
3 6 7 2 4 5 1
2 7 1 5 4 6 3
4 2 1 7 3 5 6
2 4 7 1 5 3 6
-1
3 7 5 2 4 6 1
5 7 3 4 6 1 2
6 3 1 5 7 4 2
4 5 1 2 7 6 3
3 7 4 1 2 6 5
7 5 3 1 4 2 6...

result:

ok 28571 cases (28571 test cases)

Test #32:

score: 0

Accepted

time: 537ms

memory: 50416kb

input:

1
1000 1000
plxpgukngtaywjrcxufvdwswaozxzeeduaeqslxuzcevplzosuqsedbplkmzbpyogbndbzmyfeyqamtetcjmaosbaxcrmjanjeglavxlwksvvenehzgrovffaebdtpynzajedywisavqgjjtjnqktzltyfzbvrtsfmdkzsyougzyqcckjcjjtkewysagddaizqnnptunmfyqagnxrzjqpsoqzqptzvjnfilpbgmjbetcgnewclwqxmftpepudwufcmbqtpyxajfmabqyvlgqxzhgumauzxms...

output:

-1

result:

ok 1 cases (1 test case)

Test #33:

score: 0

Accepted

time: 430ms

memory: 211012kb

input:

1
500000 2
bh
nk
zd
bw
cc
la
zr
if
ts
tq
nz
td
rv
th
nw
az
pa
qy
cq
uu
rk
sl
du
ll
jn
fw
qm
rw
va
ii
as
hw
wo
vt
zi
yt
wx
xd
en
ws
we
rw
gk
lp
hh
qp
fj
cu
uu
bp
uq
ge
lb
sa
hg
yx
gm
cu
tr
wj
ws
ei
cv
ct
wn
at
ju
mo
bm
ht
ep
ul
jt
yw
wu
ml
sh
vt
kp
ha
ws
qy
pn
nz
aq
wa
my
mf
bq
ff
xo
br
uc
pt
ne
ya
i...

output:

328239 359005 179182 482686 204300 20023 130536 239931 241096 389763 428942 59085 142077 264289 248305 479342 240166 27582 16185 228668 457050 244036 193620 105649 211322 133350 157542 350971 411062 450689 121874 131134 16031 128400 447452 107167 182808 140073 178316 435728 83736 107389 344970 39689...

result:

ok 1 cases (1 test case)

Test #34:

score: 0

Accepted

time: 412ms

memory: 255548kb

input:

1
1000000 1
f
l
m
t
y
i
g
k
v
k
g
z
f
h
n
e
v
m
b
g
a
n
i
u
v
a
k
b
e
j
x
n
m
u
a
x
a
g
t
g
a
g
v
p
q
f
g
q
i
f
t
l
t
t
w
z
l
z
n
m
v
r
v
v
t
x
w
q
h
x
h
k
n
t
m
i
y
k
e
j
b
m
u
q
x
n
u
t
v
f
n
h
z
w
g
v
r
m
x
c
a
g
x
p
p
n
w
y
x
j
t
b
d
z
n
h
f
u
u
i
y
p
c
w
b
m
d
k
p
p
m
q
j
k
o
g
g
b
r
w
c
y
d
h
...

output:

21 26 35 37 41 101 159 169 171 223 234 265 281 285 347 359 364 384 388 402 472 473 481 529 551 557 579 604 613 685 710 717 760 768 775 779 852 861 863 870 883 903 909 935 940 961 1004 1020 1069 1071 1085 1101 1104 1154 1161 1187 1212 1234 1252 1256 1259 1273 1274 1293 1315 1337 1344 1381 1432 1471 1...

result:

ok 1 cases (1 test case)

Test #35:

score: 0

Accepted

time: 87ms

memory: 48232kb

input:

1
2 500000
yoskytdthibiosryionvxhjbnvwyrumjrmogzlngtxwkyxpketeperfdqboobxcccofgoxsjjffgdymvbhrnmcfiresutjbeadpbwuyxbirokynuisiezakhyivnbelkoexbfertmmmpjyerxyrnxvseyyipjqexidomwdzwqgqopwvnguawlvdyqgpsoxuliobzndxyfondeygqyxujboqcmqmwlptkpxflccjwfbzvwjkmddqxuenqirajuqplwjfyumjycekqzgavjrpanuxixmwlmnnvv...

output:

2 1
1 2

result:

ok 1 cases (1 test case)

Test #36:

score: 0

Accepted

time: 82ms

memory: 50860kb

input:

1
1 1000000
vvzoohphaekmooymvzpvxqaxbgyabgrgrdetsieivthqtvackeaapshmaybrwivlzjtjymeqmjqjoioeknzlajdqeptnywzscjthxqahapfnktonvxbyridjhokyielyfuzzgciiulnuetgfmdppmpywhoouwbbwyhlufupqwkhjubvkplfbzxiegngnewwfpupzypskuhtopvqzczthyaxpepvbkhvitkxgopxprykcrbjnuiideigftkhgzpykkoijuiquebxaaiwaabuxssgqgsofmiid...

output:

1
1

result:

ok 1 cases (1 test case)

Test #37:

score: 0

Accepted

time: 269ms

memory: 50324kb

input:

1
1000 1000
nnnaamfktzgakyenqodpbujtlowzoloijjqorpyvgfbujjivqhgrvcsuajhkfnxfrtrrhfanoutnxetnhowuknugksqgbtpyixedmyepfgyluqjvgadnsosbevsprmupvmymsmohjpimcbgkrybnnlrgqewddkotengibpfdpfqbehofyslubivwusaxzjnbbuczjponsogapfzqnshokuerpwuewcedjmtykebmibjanhyfhvuieexfxijacmpkqatvctadngmkuefrfqthukhywwqllwwy...

output:

678 609 617 899 870 877 774 1000 471 445 27 235 658 826 245 953 982 30 358 217 883 721 410 118 311 844 959 927 36 496 527 866 561 355 127 49 896 878 454 390 303 940 377 300 951 474 975 564 226 391 422 675 150 977 598 295 451 948 400 549 580 270 571 929 667 638 276 681 16 500 833 498 592 272 872 670 ...

result:

ok 1 cases (1 test case)

Test #38:

score: 0

Accepted

time: 220ms

memory: 134536kb

input:

1
500000 2
lm
hm
wf
rl
ze
qc
ku
dz
is
dg
lc
kw
ys
ho
re
gu
pb
on
oe
wc
ya
kx
zh
fg
lb
fn
ys
ci
da
ta
mg
nc
qj
tx
tn
zw
gu
na
ee
oa
qm
zz
hx
rs
fl
bz
ik
fm
sq
xr
tf
id
lh
bk
sw
qx
lw
aa
bx
cg
ns
vl
bg
im
qp
pc
rh
pa
ns
kf
la
pl
am
sz
xs
xq
uc
wf
lz
iq
ok
mh
wi
kj
ui
xl
na
fs
vg
wf
qg
rn
th
ju
rp
fs
w...

output:

58 1665 1846 3751 4314 4582 4814 5579 5891 7033 8295 8722 8818 8893 9438 10024 10661 10828 11130 12247 13152 13212 13413 13685 13807 14992 15762 16249 16380 16681 18403 18705 18972 19183 19612 20313 23145 24496 24611 24688 25329 25395 26188 26416 28256 28450 29716 30530 31109 31264 31798 33207 35278...

result:

ok 1 cases (1 test case)

Test #39:

score: 0

Accepted

time: 458ms

memory: 255576kb

input:

1
1000000 1
h
v
a
h
z
d
c
r
l
b
t
l
d
s
z
h
c
n
p
d
v
t
x
a
z
k
i
q
g
d
p
s
i
a
z
l
e
f
q
t
v
r
b
a
f
v
v
c
z
c
w
u
s
e
d
p
w
c
n
y
f
d
f
j
i
x
b
a
h
m
w
g
b
z
h
d
m
y
q
y
u
d
s
g
l
m
t
p
u
x
w
m
h
c
t
y
p
u
e
l
h
s
x
m
f
t
p
d
f
z
z
k
w
h
s
y
i
h
v
j
w
w
s
v
h
y
a
r
f
y
d
j
w
e
a
h
k
p
x
l
x
a
k
f
...

output:

3 24 34 44 68 127 135 142 162 286 305 313 324 329 388 395 402 467 519 525 528 541 543 586 592 605 614 627 667 694 697 708 791 868 870 872 894 992 1006 1027 1041 1092 1206 1218 1225 1232 1235 1244 1259 1275 1287 1319 1331 1341 1344 1392 1416 1421 1440 1448 1459 1465 1484 1490 1507 1544 1547 1569 1630...

result:

ok 1 cases (1 test case)

Test #40:

score: 0

Accepted

time: 187ms

memory: 48172kb

input:

1
2 500000
csbazestpjffzjvrjztjidouhfewitwyhczwalacmlfmfpjozlnojeeltcyjkgbwpnzhzdeeublvjcgepkupvlqxhzkjfudcojhtxsrndyipgsuexhdjxodymiofmaxdkhsyallmorhqdrosgvzwvsgobotbwlwnqvohekjougktqmjaknocgtumjjvmtphfnoqrsrfgztpufvtnafmhmmcpxkrjyokgrlvaswhkkxfxguuakezavqkbkvnhjpycgvrsefranfttvrfnoaeempqhlsdzwtrvf...

output:

-1

result:

ok 1 cases (1 test case)

Test #41:

score: 0

Accepted

time: 75ms

memory: 50924kb

input:

1
1 1000000
zcgzehvspliuqlawrvemmxvlapmqsnpdieaqubpadgbsduckarfgikvmcphtdjtgczbfuivcjhpmwgaxoqvbmwldxvqwtcqizfyvxoahqcuyyvdgxzsohnkjblrwuyietchhqusxamzculyvhaqzoftboauhkdxnpxuxbljmftjtyrczfxxsbwkvzhehmwkhvbkjmnuypbjgibszsdtocihfzwuvdpvszccyroufgktzfytdkcrneuvelrcoufxvmxajvhlnikzfemppharjuwicizqodvrj...

output:

1
1

result:

ok 1 cases (1 test case)

Test #42:

score: 0

Accepted

time: 546ms

memory: 50420kb

input:

1
1000 1000
vkrkwbibcsuczrgypnuclsmvexjomqttgzmpebzbtmtltqyekywmlpmluwwmjjybbnztlxthcphhfayjjegghgyuippcrweyyzgjfnzemamafgtexvhxofarelxdoptwfohqrnjepcpxzkoepuluocahihxhqipydaiermnrbxjpkeundrirpdcalvbjyhhdazarjuwepzaiafcmbaxqlfqcnbzvlamfwgpqoutqvwhilaqswbqzvohiayenlifowexxzvuxrldswlfpjugwozxwzpxeqtkb...

output:

-1

result:

ok 1 cases (1 test case)

Test #43:

score: 0

Accepted

time: 411ms

memory: 210984kb

input:

1
500000 2
pa
fn
bi
ka
az
wj
sf
db
xb
ad
di
ur
he
dq
bv
zf
cw
yw
ha
to
hl
al
wi
pq
pq
ao
eh
ua
xo
oi
dw
nz
do
dn
oq
sd
bn
nj
fa
mx
vx
ss
pp
dz
jk
us
mv
ko
gk
wa
ju
em
bc
tp
qx
cr
rh
ro
qx
vk
bm
ju
ir
kd
ny
gw
sg
js
qt
zi
uf
pg
md
du
he
qy
ur
ge
dp
ho
hb
ig
zi
dr
wq
ix
my
gz
tf
kb
ab
ye
zf
rx
cy
mq
o...

output:

247937 34614 304596 483270 297357 286930 228950 185656 156160 245832 108629 480042 366340 32791 345159 202248 405645 108721 209609 268365 332968 197188 345359 185649 182188 104712 154585 213889 289836 9976 18618 58487 437995 230791 475558 126570 16305 252982 349449 296701 97812 399469 349311 387371 ...

result:

ok 1 cases (1 test case)

Test #44:

score: 0

Accepted

time: 430ms

memory: 253512kb

input:

1
1000000 1
i
b
s
i
b
r
y
g
d
n
a
s
e
b
k
h
d
f
m
c
t
a
e
u
q
d
e
s
f
p
g
t
f
u
l
v
k
z
y
s
d
d
v
m
u
e
l
c
l
v
e
q
i
o
w
f
c
k
f
f
o
y
h
b
o
r
n
h
n
j
w
d
l
z
n
p
u
n
z
t
r
w
d
e
l
g
r
u
a
v
h
t
s
k
i
y
m
q
g
a
x
z
i
p
b
w
e
m
n
i
z
g
u
g
q
c
f
c
e
h
j
e
i
t
d
r
m
g
d
h
z
w
v
y
i
l
o
u
r
m
j
l
d
p
...

output:

11 22 89 100 151 175 183 244 245 248 306 310 315 337 392 434 452 470 494 495 497 506 541 543 576 580 594 603 641 653 669 694 721 725 727 746 773 815 837 881 898 937 950 960 967 987 1009 1014 1020 1024 1026 1040 1058 1100 1115 1118 1143 1144 1174 1188 1189 1259 1278 1286 1334 1356 1365 1407 1419 1442...

result:

ok 1 cases (1 test case)

Test #45:

score: 0

Accepted

time: 705ms

memory: 110748kb

input:

1
100000 10
ehlimdmwkt
jlrfzdjvam
jwtsqoiebv
mlksfsakmd
zamugzmeha
nxepoofxsh
idoigdreky
ugarhoilzd
oalhajmyfd
vfnxfsoasz
fymboaopqw
rgyhcdtcxm
nvgtvzxgqs
uhwapwajcq
udicenzrkr
jgeaupojpv
efrdqjgayp
yvqwqkaipk
jlsbzxdzeh
btdjgvxcqd
uqcoyaaohl
szcxibrkvc
yzyntbtiuo
lbwkorixzq
lfffvwuktb
euhjmdnptr
tb...

output:

86662 19312 87456 45960 68417 13898 25772 88768 16342 46370 70038 46317 86993 93884 10865 34566 26708 90753 23005 89766 28318 94084 20617 40663 86545 35699 28292 12374 42509 93977 24068 58745 9426 68264 64839 73937 48795 50463 1219 75644 61279 31438 27507 96701 51163 10705 95238 51237 6549 546 62727...

result:

ok 1 cases (1 test case)

Test #46:

score: 0

Accepted

time: 150ms

memory: 85948kb

input:

1
100000 10
mqpzaypqsg
rybikrqyzx
gxcfzgdglt
sszegicsli
oxzpnucwde
ezkskhdmiu
lqsgzsxckw
jlglibuvpi
ctqjnskviw
yqhiaisjxf
mpmgtaupwp
swrhvwtxpg
wcgchdtjyk
hynexzwpxj
veaomhaxnn
bluwuxnmyj
zeefjdwksv
lgegdqxuyt
ezkpautemn
ykbpibnfsp
ddbtafikzb
cetuawmhwo
epwldttkrv
lytomstlzm
wugxtmlmzf
atathrowwp
sv...

output:

53727 74940 91087 57456 62435 10870 21928 66082 4955 32456 18187 97593 66750 20289 15919 20663 62683 27843 34112 93659 54457 59680 54493 3066 97046 50477 76783 43516 39051 88164 99295 90523 68969 76193 49998 43932 75292 46440 15855 25238 91728 73402 3050 40193 12931 51672 4841 96815 12133 33457 7285...

result:

ok 1 cases (1 test case)

Test #47:

score: 0

Accepted

time: 590ms

memory: 140436kb

input:

1
200000 5
untrg
qewwk
zdlct
ltaki
tegsd
pllgg
jvwkk
pkcru
donwe
elvdq
crquy
yqlbl
yalff
rwhfy
xlsqg
vzjww
vjdni
vevwr
njecm
onvvj
ldfjq
ypgae
vuuvu
jxgce
weone
hnklb
hkkyw
tuwyp
kgcad
octvg
gfkei
ovmql
kxzta
npvrv
pxenv
hklvf
sfzso
blanl
jigxz
uqcrk
lbehm
cxwbq
ymdzw
hmvpk
wjdqq
kpfls
rktrp
ogdhs
f...

output:

-1

result:

ok 1 cases (1 test case)

Test #48:

score: 0

Accepted

time: 59ms

memory: 48112kb

input:

1
100000 10
fxhzgdmpvu
rbapkxuwdz
rcbtjgzlqz
vuwjdihqwk
brwenfhpot
cazbgafcaa
ylyhnyrgwt
sixsqzjakz
qdxsdrthuu
zdrwkcqqdk
xluoyqriep
wpcqewlpfo
ebcmamyzmt
fanzqaxbew
ikmsqafyun
xczrzagmdn
bbsvmsrtph
sjtudpeyqj
kdvxgfnozj
pnbefumkkh
xjahjflidu
begdvasklf
xcragpudlh
pkugzyrpgn
dtlznmvred
supuawndia
xa...

output:

18127 74558 31024 70246 67557 62263 32741 11117 65532 89798 66845 68134 49615 59139 70405 62079 64706 39682 96815 86183 74234 79324 64244 8970 67523 79693 87956 88010 26950 80955 95561 72329 32469 38436 78880 44912 17902 42104 31930 33737 35017 25981 11826 76456 4509 99723 53824 96673 34955 57867 26...

result:

ok 1 cases (1 test case)

Test #49:

score: 0

Accepted

time: 609ms

memory: 136880kb

input:

1
200000 5
rdaxv
rqwti
srbck
qdtal
ltoxk
ughkh
sywke
cigmu
fioqb
gnycn
cexck
tcekr
byyqn
cgokp
ausjo
ubsgq
sxouf
xxvnu
drjqw
nvaul
ashzf
scexc
ueyta
ryyny
xotaf
prjgo
hjfrk
alqrp
zggry
xrivg
wislr
lzygn
lleum
utbzq
dzbpn
kmkvp
bacqh
kdfik
xaqru
aeeem
otmht
exrjh
poyfh
rgggk
mhbof
kqyzm
czill
oygax
c...

output:

-1

result:

ok 1 cases (1 test case)

Test #50:

score: 0

Accepted

time: 186ms

memory: 50380kb

input:

1
2 500000
tossrwlzkdzzrphwvvnkmdevslssgacszrojwkxgorcupejhwfybmoyegfhulclkqadmdjpfccnbxhsumeffzhfowyhxqqpdrjguansbqlyuglodfwxjphusmwlevcmpjfcbrjbmdbsqovuljaxqfeorcmgjsbwxappqwsuacmjtyhjubdjyevglxpkektgumdrvtwkuzdiyznzactijqouerxfqatzcwjqserfliiqihufyinagdbqglcnqttlhkebmezdjcfvdcmcjgqhygbxmvzndqnywm...

output:

-1

result:

ok 1 cases (1 test case)

Test #51:

score: 0

Accepted

time: 161ms

memory: 50732kb

input:

1
1 1000000
aqfomtfebdjjikpwsgohpqhvbrasmasgmocifvxczotxorlguxtriaftafotynozikgxytfzuztzapeayssibygltogshsbfwlfcqzbfkleizodgzztxzaysqtsvokwictzyehplvlkpucyizyrcimlczpucivarsihznzqmkjyuhajkgasakdeechddnrezbboozngkyxrjkzfgdlzjewmzhfwmfzguwukeeaambyszysderzrbbbdraxbdpqrurmztoepgptyjtbnrwpyntoagemsfeari...

output:

-1

result:

ok 1 cases (1 test case)

Test #52:

score: 0

Accepted

time: 504ms

memory: 107300kb

input:

1
100000 10
kxlhbmfknl
mldtlbegjo
roglqswqdz
fkcfeioyrf
varxnuxhyk
yputtwlqnj
qjfqxkpbug
thnarwcjpt
oqfpxygtat
hagzhuqeem
bwnnbeweqg
semgcubiaz
zoomamfsyb
lhocxkgyvp
nzqeqkhpes
hhhqaraqjq
mdcgqoqgbp
gvsxjqnvjv
sfkoamvaor
sngtozdbrc
yrhpdcfhhf
eptkmcorhi
hwszrfyvqr
xemzcudvkz
rjklevonsv
vnpmsgqdcb
sy...

output:

57071 32365 70498 76321 47033 42515 13879 70306 16545 21723 89369 33158 72717 1564 3478 73488 7079 94670 31357 97413 81420 1435 69916 48115 21903 10703 32980 89658 60064 14341 6792 39135 29633 71548 30588 39584 48432 988 78392 21091 31995 95194 8908 18346 29093 24772 40892 3451 68663 75049 96308 174...

result:

ok 1 cases (1 test case)

Test #53:

score: 0

Accepted

time: 800ms

memory: 111336kb

input:

1
100000 10
dplijbwkgs
yigahsojnn
ftafmnroiu
gklxajdgis
lkkiioljfz
mkckxjukta
rwxjqmbddd
opvmalbpzl
ngobvwffjt
ziszyyrvkb
hxjvrmnlnm
pcytdvmvcb
jyzqhxxzpd
ykfcpnynxt
tqfqojtyoc
cyphatoadm
nsibkreiqr
sjujphkbwv
wdccnduvvj
gefgntmint
qodiytabxc
vpeltdzowm
fppmxjflkq
vhohdpiocs
vuudozaxuh
uoonxsqeko
iq...

output:

-1

result:

ok 1 cases (1 test case)

Test #54:

score: 0

Accepted

time: 602ms

memory: 109152kb

input:

1
100000 10
qyjclrjhcv
hrexdepsrh
drbmgtcoed
twbslhlapq
tocwgicnrn
ndudcbqcoz
eunlkqeugj
ictesjwnlv
ukatawfiji
dktfpbehwi
yggzqhuccl
oznogatwir
efcduoftki
ojyrolvatq
fkpbtdwpmj
lliymvqkws
taqnrqowtg
uzfiimgmkz
lmavtcmajn
hagghgkdro
eprquadsxn
ztmzpejqea
vzitenazyw
nhcbbtdnuu
frafncvjoy
javzrcwaus
ap...

output:

70688 87644 52292 28591 50997 8683 65213 56194 88647 13886 37068 65000 20681 18300 91241 25479 59247 99309 78355 37172 46183 890 93248 58251 61016 63862 65668 95575 76612 30993 32350 70156 5246 69329 17558 54385 25813 83818 60390 97227 91121 97124 36219 14751 88966 55645 45053 15315 88240 88007 9984...

result:

ok 1 cases (1 test case)

Test #55:

score: 0

Accepted

time: 786ms

memory: 107468kb

input:

1
100000 10
sypalllczm
fyvwvgicyp
jqomdiqcfp
aeaaztogli
imxeiuthuk
ydkrfpfmft
udmkztmwfe
ohyczkizug
fzjyyniywg
itrowixklc
tussdfceqf
evpuvluxpg
iluimcnpco
olstppvixo
dvdpowweue
hxiodpcvjl
xhflfalebb
vpfsjldkqf
dfjslcblpv
dzfptmeyqv
rvgrnefzaj
illzbltjxb
xbbdvyufbw
frovlztkno
gsylowileo
zasbhsaiku
rw...

output:

-1

result:

ok 1 cases (1 test case)

Test #56:

score: 0

Accepted

time: 507ms

memory: 105000kb

input:

1
100000 10
jghpqhzbwn
khmnmmjces
evcbszdsee
cpedxvljuc
bijisgizio
lwybtheziw
azeowrjbes
bvcakdyowl
hqrgrmdxkv
latrynwkve
zbwrfmlfzl
bwsrqcxufw
mlxgssthvv
tbnlrnnagy
fumhlmrrsc
klisexvqbh
fuhiznqnbs
gydnvmatzs
kddgnpybzt
lqtposlfrf
teyereqlki
phffqzyxsk
zivoiupzye
fhyewkrofw
vmhqdpsznj
kkfzikuoop
fd...

output:

62710 22124 21615 64416 50729 17817 75759 8250 71227 76572 36113 64382 50393 89892 30766 64265 2688 19630 75184 92872 73160 35194 61878 93279 50160 97752 15405 69031 39795 6621 60553 73886 38245 71924 46293 42507 83951 97193 39 44401 83984 7460 2245 93406 51344 31904 69632 22628 35717 32306 14696 57...

result:

ok 1 cases (1 test case)

Test #57:

score: 0

Accepted

time: 602ms

memory: 109376kb

input:

1
100000 10
ajdomreiyg
awhziinfwu
gtqxnxstjq
acgalthnvc
rlnbmtemxi
ouqfgtxjel
zrpqnultuj
ajpfxgstzw
ugccienqit
cgyjlqfkma
fvvzhsruhh
xzvtqxdzfx
bzklilivkt
vracwjjijn
pijsxthpiv
sloandhcmh
uezrrpwwrp
qizguxpvwx
fgfwudmpmw
zmddapzqly
fvxavrqcax
pstjlrahls
zaewasovpv
wxbnphincw
bcauhtuzyg
svvtswoswv
sy...

output:

56298 54800 57800 20845 22297 55068 48245 66524 33043 94873 64229 71671 10673 46040 58039 68216 4503 17847 81807 89623 80261 78850 92552 76384 80434 24835 19246 91830 24786 86957 81439 51850 74726 47680 85006 53404 54722 85420 4684 7028 11905 49657 16021 46534 51379 36807 31644 38744 29925 93309 846...

result:

ok 1 cases (1 test case)

Test #58:

score: 0

Accepted

time: 815ms

memory: 109664kb

input:

1
100000 10
otqeflvutp
ktjpzyjlbe
utqhsjbhxi
jmmcfrwiml
vfxvqrdzdk
aenkvqbzpo
bfdzgohawd
vdsqzihcsw
jicioserdw
eberxkmhko
vsmxkcsymw
aunqxqooio
fuserissyp
powkmizyqg
pklrsxredz
kvwierqibi
wrzusyeiou
odjaxqedqv
xxntmrkafl
wkgkolzgdv
jxwmcpjiya
pxyhhfzjsh
ewcjkdaymm
taklqmzazs
mwvlhirbzn
lfzultiztz
sn...

output:

382 84345 97930 33349 97904 22097 39718 50938 8097 29501 60138 59343 45850 14999 33878 75165 89190 2927 5148 88359 8690 73883 58554 97241 18578 71278 49948 75768 88615 92548 49864 38657 6906 76512 1953 54994 57182 30718 74311 18643 86406 38020 68701 58080 54940 16925 97405 61397 70404 96178 19096 70...

result:

ok 1 cases (1 test case)

Test #59:

score: 0

Accepted

time: 809ms

memory: 107208kb

input:

1
100000 10
uxfboqjiml
urguovogte
hlfrgfwgkz
lnaljmgocb
cbkdynsxzg
jfggokuktr
fgeeeayprq
glgeqdexax
ccwqbwaake
pexvcckyid
rjvzlorehp
jwrolcaeqq
pwftjauyxv
dtblxopysv
pmvikikgse
pldtousdqo
tgenvzvdnr
payixpmmjr
urkthfeotj
pqomqonmqf
wsnfwcbqce
ynjhtrkmcg
nqjuozngbr
ombhjkloow
fxbwspocpf
ovcbrjolwn
yn...

output:

-1

result:

ok 1 cases (1 test case)

Test #60:

score: 0

Accepted

time: 799ms

memory: 108900kb

input:

1
100000 10
ipzgqbnfvd
sgfrlagntk
gwwweijzea
fxpgdtxgti
waobttsufl
nrdslhdkxf
ssrwruilxq
pdglmfvowa
azjbrlhzff
pchtakzdkl
ajsqpedcoy
pjsukcypln
fiognbhmxj
agpmnzvnms
ikdnsabypt
zaotlspbvj
nummgjsshd
mtteglneuy
eopvrvdxtb
nuwnziuqyv
pmqxpafghb
krwuxxunvh
dnumirddbi
oyiyooimqd
zmlwgndkny
ybxqktsjpq
kv...

output:

-1

result:

ok 1 cases (1 test case)

Test #61:

score: 0

Accepted

time: 818ms

memory: 112312kb

input:

1
100000 10
vhntzmzfjq
lpkanhwnma
hnshcjeytm
rroumhwnmt
jeweevjgqp
bsegdybxio
rwtjvtvlko
fmpcrdsdes
edijyqpurg
zghldxztvl
xbcsrduzmx
tguxmkqcfz
bajotxtuii
zsfgpkokbg
xrgnvbpctc
clxyepehzt
veudydfurf
mavbkeurwo
nfmwtnwspx
uahthuvvxc
vdaadmfinf
kyhxwovgtv
jnqppwnuvt
hiepfckmpa
oxrklvvyof
iintishepc
eq...

output:

55114 5890 73523 20039 73717 80484 81932 10580 63966 54212 46615 18794 75596 81784 59621 27433 58782 87142 96954 20460 34654 94456 70988 69557 90782 85275 15299 63361 36272 18430 95223 18592 74283 56383 5027 26037 65716 99305 22653 78544 53386 14644 41008 12510 61772 17126 43383 35590 78926 97622 53...

result:

ok 1 cases (1 test case)

Test #62:

score: 0

Accepted

time: 594ms

memory: 106508kb

input:

1
100000 10
uudwzdlejj
ivabpznlij
uqnmtxmmgg
ntzanognix
qdgoodcnun
pekrqklkez
eejprmjekr
pwblriymwp
rievkuhrez
npbdnosxjq
eoeicddyic
hotgqnlmge
iygqxwlogm
pnsgildmtr
rqkpassked
qpsqosjzsm
phxkunmotd
oohtwpcpli
ejeiosheqn
rzrjlvpkfa
ynajbomlnb
awxowbwzxx
hfajxtyefh
ulxeladiwo
mroseowqdn
fszffsdlmi
lm...

output:

98022 49231 74735 86553 70945 95573 19083 60070 67293 67591 65469 16535 11014 54415 85543 74500 53899 22122 88031 73490 5687 20252 19108 55906 76389 33388 26799 96605 8839 10946 78462 55394 97124 35854 276 9772 70289 53671 41537 11794 54278 74693 9149 55624 76487 76665 68893 44550 50357 40842 98687 ...

result:

ok 1 cases (1 test case)

Test #63:

score: 0

Accepted

time: 808ms

memory: 109308kb

input:

1
100000 10
akvvptzhlm
ukqiqwgjxr
raftyctsec
tljopwxqgm
odkoyjszvv
vuuxpzuwty
vugkbhgrbq
mghdhtbdmh
cmlrrcpkrj
fropiipnog
fippflholr
hxvyifxfhi
dstwpsdbxl
zekzumxmnr
qywqzyxvln
jacdvjvczu
dpmjugphun
hhrhfdjzkx
jfwnfjfokw
ygziaihrgd
ybrhjiwfaj
nketysvhiu
sydarvrsdv
zlhwpjkvmc
ynaolmsimg
tgjfocrgba
kh...

output:

-1

result:

ok 1 cases (1 test case)

Extra Test:

score: 0

Extra Test Passed