10975 - Dueue's Quiz

[filigabriel]

Is there any special trick for this problem ???

What should be the correct answer for this input

Sample Input

1
4
a
a
bb
bbb
3
3 3
aaa
aaa
aaa
3 3
bbb
bbb
bbb
3 3
ccc
ccc
ccc

My Output

Test Case #1
Query #1
a 9
a 9
Query #2
bb 40
bbb 16
Query #3

Any commenting or suggesting will be pleased

[angga888]

My output is:

Test Case #1
Query #1
a 72
Query #2
bb 40
bbb 16
Query #3

I count a single character as 8 occurences (just like the 'madam' example), therefore I get 72 for the input 'a'. Btw, oops... I forgot to check for multiple words in the list, but fortunately maybe there is no such case in the judge input, that is why my program only output 'a' once.

Hope it helps

[filigabriel]

thanks angga888, but i'm still getting wrong answer .

can anyone post their code of reading test cases of this problem, please ???

I've thought about no printable characters in map.

problem is case sensitive ???

Thanks in advance.

Maybe my algo is wrong . But i have faith in my code and algo.

[little joey]

Yes, duplicates occur in the dictionary, but they should be printed only once in the output. So the output specification should read:
"...Then, all the unique words from dictionary which actually occurred in the table of that query should be listed one in each line (or each in one line!) together with their total number of occurrences in the given table."

I read the dictionary using getchar() and islower():

Code: Select all

...
   scanf("%d",&dwords);
   for(i=0;i<dwords;i++){
      while(!islower(c=getchar()));
      j=0;
      do{
         dword[i][j++]=(char)c;
         }while(islower(c=getchar()));
      dword[i][j]='\0';
...

[angga888]

Yes, duplicates occur in the dictionary, but they should be printed only once in the output.

Wow... I 'accidentally' handled such case without knowing it I was so lucky....

[filigabriel]

Next code was the first one i submitted

All later submissions are very similar.

Code: Select all

#include <stdio.h>

int v[8][2] = {{-1,-1}, {-1,0}, {-1,1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

typedef struct {
 int cont;
 int isfinal;
 int letter[26];
} WORD;

char map[101][101];
char words[15000][101];
WORD w[100000];
int final[15000];
int cw, cf, nrows, ncols;

int cmpint(int* a, int* b) { // Code deleted }

void agregar(int index, char* cad) { // Code deleted }

void readwords() { // Code deleted }

int calcula(int x, int y, int dx, int dy) { // Code deleted }

main() {
 int nc, nq, query, x, y, z, caso;
 scanf("%d", &nc);
 for (caso = 1; caso <= nc; caso++) {
   readwords();
   printf("Test Case #%d\n", caso);
   scanf("%d", &nq);
   for (query = 1; query <= nq; query++) {
     printf("Query #%d\n", query);

     for (x = 0; x < cf; x++) w[final[x]].cont = 0;
     scanf("%d %d", &nrows, &ncols);
     for (x = 0; x < nrows; x++) scanf("%s", &map[x]);

     for (x = 0; x < nrows; x++)
     for (y = 0; y < ncols; y++)
     for (z = 0; z < 8; z++) calcula(x, y, v[z][0], v[z][1]);

     for (x = 0; x < cf; x++)
       if (w[final[x]].cont > 0)
         printf("%s %d\n", words[w[final[x]].isfinal - 1],  w[final[x]].cont);
   }
 }
}

My algorithm consists in generating a "tree" of all dictionary words (logically, all of them with size less than 101).

After, i count all words in all 8 possible directions.

I think, my problem is managing input.

Please help, thanks in advance.

------------>

I have to say Test cases' input is correct .

[Wei-Ming Chen]

10975.... I posted it again in Volume CIX

[Roby]

You've posted in wrong thread, better you made in appropiate thread in Volume 109.

[Wei-Ming Chen]

My code got TLE in this question.
And my method was find the first word, and checked the eight side of it. I thought it was too slow to solve this question. Can someone give me some hints to solve it?

[Tamagodzi]

WORD w[100000];

why is that array only 100000 big ?

if all words differ in first 3 letters and are 100 letters long u need 98*words entrys

i'll write and submit an input checker tomorrow

[filigabriel]

WORD w[100000];
why is that array only 100000 big ?

It's not neccesary to check out anymore !!!! Your observation is correct and exact, thanks !!!!!

I increased length of array to 400000, and it was accepted .

I didn't expect to have any wrong answer, because of using less memory than required.

I will remove code very soon.

[Cho]

Is the following io correct?

Input:

Code: Select all

4

4
hello
bye
one
two
2
3 3
bye
okk
res
3 3
one
wzq
too

4
hello
madam
hello
madam
1
6 6
helloh
oezxec
lnllbv
lmllas
eogfod
hmadam

6
x
xx
xxx
xxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxx
15
1 1
x
1 2
xx
1 3
xxx
2 1
x
x
2 2
xx
xx
2 3
xxx
xxx
3 1
x
x
x
3 2
xx
xx
xx
3 3
xxx
xxx
xxx
4 4
xxxx
xxxx
xxxx
xxxx
5 5
xxxxx
xxxxx
xxxxx
xxxxx
xxxxx
10 1
x
x
x
x
x
x
x
x
x
x
1 10
xxxxxxxxxx
10 10
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
100 100
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

120
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
abc
aca
acb
acc
baa
bab
bac
bba
bbb
bbc
bca
bcb
bcc
caa
cab
cac
cba
cbb
cbc
cca
ccb
ccc
aaaa
aaab
aaac
aaba
aabb
aabc
aaca
aacb
aacc
abaa
abab
abac
abba
abbb
abbc
abca
abcb
abcc
acaa
acab
acac
acba
acbb
acbc
acca
accb
accc
baaa
baab
baac
baba
babb
babc
baca
bacb
bacc
bbaa
bbab
bbac
bbba
bbbb
bbbc
bbca
bbcb
bbcc
bcaa
bcab
bcac
bcba
bcbb
bcbc
bcca
bccb
bccc
caaa
caab
caac
caba
cabb
cabc
caca
cacb
cacc
cbaa
cbab
cbac
cbba
cbbb
cbbc
cbca
cbcb
cbcc
ccaa
ccab
ccac
ccba
ccbb
ccbc
ccca
cccb
cccc
3
100 100
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbbabaabbbbbbaabaaaaaaaaababaaabbabbaaaaaabaababbaaabb
bbbaaabababbaaabbbbaaababbbabaaabaaabbbbbbbbbbbabaaaaabaabababababbbaabaaaababaababbaaaabbababbbabba
babbabbaabaaabbabbbbbbabaaaaaaabbabbaaaaabababbaabaaabaaaabbbaaabaabbbbaabbaaabbbabbbbababaabbaababb
abaabbabbabaabbbbabbbbabbbbaabaabaabababbbbbaaabbabaaabaaabbbabaababbaaabbabaaaabbababbaaaaaabbabbab
babaabaabbabbbbababbbabbbbaaaaaababaaabbbaabbaaababbaaaabaabbaaabaabaaabababbaabaabbbabbbabaaababbbb
aaaaaabbbbbaaaababababaabbbaabbabababbbaaababababaaabbaaababbbbbaabababbbbbbbaabbaaaaabbabbbbbbababa
abbbbbbaaabbaabbbabaababaababbbbaabbaaabababbaaabaabbbaababbabbabaaabbababbbbaabbabbbbbababbbbbaabab
aababaaabbabbbababbaaabbbaaaabbbbaabaababbbaaababbbababaaabbaaababbbbbabbbabbabbbbbbaaaabaaaaabbaaab
abbababbaabbbaabaabbbbbaabaabbaaaaaabbabaabbbaabaaaaaaabbbabbbbaaaaabbaaaabababaaabbbaaaaaabbababbab
baabaaabbbababbbbbaabbabaababaabbbbbbbaababbbbabaaaabaaaabbbbbaababaabbababbaaaabbabbbbbababaabbaaab
bababbaaaaabbaaabababbababbabbaaaabbbaaaabaaabaaabaabababaaababbabaabaaaabaaaabbbaabaaaaabaaaabbabab
ababaabbabaaababbabaaaaaababbbbbbaaababababbababbabababaaabbbbbabbaaaabbabaaaaaabaabbbbbbbbbaabbaaba
babbbbaaabaaaaabaaabbaaaabaaababbbbbaababaabaaabababbaaababaaababaaabbbabababaaaabaaabaabbbabaababab
abbabbabababbbbaababaabbbbbbaaaababbaaababbbbbbbaaaaabaabababaaaaaababbbabbaaaabbababbbbaabaaaaabaab
abbaaaabaaaababaabbbbbbaaabbabbaaabbaabaabbbbaababaaabbbabbaababbbbbabaaaaababbbaaaababbabaaabbbaabb
aaababaaababaaaabaabaababbabbbaaaabababbbbaabbabbaabbaabbbaabaaabbbaabbaabbbbbaaabbaabbaabbbbbaaaabb
babbabbbaabaabaaabbbbbbabbaaabbaaabaaabbabbbabbaababbbbaabaabaababbababaaaabbbbbabbbbaabbbbabbabbaab
babbaababbabaaaabaabaababababbaaaaabaabbabaabbbbaabbbaabababababbbbabaaabaabaabbbbbabbbbbabbbaabbbab
aaabbaaabbababaabbbbbbabbaabaabbbabaaabababaaabaaaaaabaaabbabaabbababababbaabababaaaaabaaabbbbbabbbb
bbabbbbabbaaaabbaababbabaababaaabbbabbbabaabbababbbaabbbbbbabbabbaaaabaabbaabbbabbbbbbbbabbaabbbbaba
aaabbaaabaabbaababbaaabbbaababbbbaaabaaabbabaaababbaabbbbabababbbbababbaaabbaabaabbbaaabbbabbbbbbbab
bbaabbbbbaaaabbabbbabbababbabbbaaaabaabaabbababaaaabbbbbbabbabbbababaaababbabbabbabbabababbbbabaaabb
bbabababbaababaababaaaabbabaabaaabbbbbabaabbbaabababaabaaababbababbbbaababbbaabaaaabababaaaabaabbbba
aaaaabbaabbaabbbbabbbaabbaaaabbabaabbabbabbbaababbaabbbbabababbbbabbbabbbaabbbbbbbabaaababaabaaaabba
bbabaaaaabbbaaabbbababbababbbbabaabababbbbbbababbbbababbabaababaabababaabbababaababbbaaababbaaaaabba
bbbbbaaabbaabaabaabaababbbababbabbabbaabbaaaababbababababababbabbbbabbabbabaabaabaabbbabaabaabababbb
ababaaabaabbbaabbababbbbbabbabbbbabbaabbbabaaaabbaaabababbaabbabbbbaaaabbbaaaaaababaababbaaaaabaaaba
aaaabbaabaabaaabaaabbabbaabaaabababbbbabababbbaaabbabbbababababaaabbabbaabbbbbabbaabababababbaabbaba
bbbabaaabaababbbbabbabbaaaaababbabaaaabbbaaabbabbabbaaabaabaaaababaaababbbbbbaaabbaaaababaaabbababab
bbbaabbabbbabbababbbbbbabbbaabbbaabbbbaabbbabbbbbaaabaabaaabbaaaabbbbbbaaabaababaaaaababbabbbaabbabb
aaaaaabbbabbababbbbabbabbbabaabaabbbbaababaababaaaababaaabbabbbbbabbababaaababbbaabbbaaaaaaababbbbab
bbbaabbbbababbaabbaaaaaabbaaaabbabaaaaabbbaabbaaaaabbbbababbabaabbbabbbababaabbabbaabbbbaaaabbbbbbba
ababbaaabbabaaaaabababbbbabbbbabbaababaaaabbabbaabbaaabbbaabababaabbaabbbbabaaabbabbbaababaaabababab
aabbbaaaabbabbabbbabbbabbbaaabbabbbbbbbbbaaaaaaabbabaabaababbaabbbbababbbabbabbaaaaabaaaaabbaaabbabb
abbabbbabbaaaababbaabababbbbaaabbbbaaabababaabbabbababababbaabababbaaabaababbbaababaabbaabbbabbabbaa
abbbaaaabbbaabaabaaaabaabbaababbbbbbaaaabbaabaaaaaabaababbbabaaabbbbbbaaabbabbbaabbabbbaabbbabbabaab
abaaabbbaabbbabaabbbbbaabbaaaabababbbbaaabaaabbbbbaabbaaaabbaaaaaabbabaaabbaabbabbbabbaabbaababaaaab
ababbbbabaabbababbabbabbaabbaaababaaababbbabbaabbaaababbaaaaabaaaababaaabababaaababababbaaaababbaaaa
babaaaabaabbaaabaaaabaababbbaaababbabbbbbbababbabaabbaaabaababbbbbbaaaabbbbbbbaaaabbabbabbabababbaab
bbaabbaaaabaaaabbbbabaaaaaabaaaaabbabbbbbbababaabbaabaababbabababababaabbbaaaaaaaabaababaabaaaaaaaba
aaabbaaabbaabbaababbbabaabbbbbbbbaabbbabbbaabbbaabaaabbbaaaaababaabaaaaabaaaaabbbbbbaabbababbbabaabb
bbaaaaabbbbbbaabbbabbabbaabaaaabbabaabbabbbbbbbbbabbaaaabaaaaabbababaaabaabbaaabbbbababaaababbaaaaba
bbababbbaabaaaaabaaaaabaaabbabaabbaaaabbababbaaabbabaaabbbbabbbbaaabbbabbabbabbbbbbbaaababaaaabaabaa
aababbabaababaaabaabaabbbbabbaaaababbabaaabaaabbaaaaaaaaababbbbabbbbbbababbabbaabbabbbbbbaaaaaabbaaa
aabbbbbbbbaabbbbabbbaabbabbabbabbbbabbbbbabaabbabbabbabbbbabababaabbaaabbabbbaabababbbaaaaabaaabbaaa
baaabaaababaaaaabbbbabbaaaaabbabaabbaabaabaaabaaabaaaababbaabbbbbaabbbbabaabaaaaabbaaaaabbaaaaabaaab
aaaabababbbaabababbbbbbababbaabaabababbaaaababaabbbbaaababaaaabaaabbbabbbbbabbbaabaaaabbbbaaaabaaaaa
abbabaaaabbaababbaabbaaababbbbabaaabbbbabbabaabaaaaabbaaaabaaabbababbbaabaabaaaaaabbbaabbababbbaaaba
aabbaaabaabbaabbaaaabbaaabaabbabaaabbabbbaabbbbabaababbbaabababbababbbabaaabbbbbbabbbaaaaaaabbabbbab
abbabaaaababaaaabababbbbabaabababaabbaaabbababbbababbabbbabbbabbbbaaababbabbaaaabaaabbbaaabababaabbb
bbbaaaabbbaabaaaabbabbbaaabababbbbbbbbbbabbaabaaaabbabbbbbbbbbbbababbbabbabbaaababaabaabaaaaaabbbaab
aaaaaabaabaaaaaaaaababababaabaaabbaaabbabaaabbbbaabaaabbaaaabbbbbaaaabbaabbbabbaaaaaaabbbbbbbabbaaaa
baaaaaaabbbbbbbbbabaaaabbbababaaababbbbbabbabbbaaaababbbababaaabbaaabbabaabbbbabbbaababbbaaabbbaaaaa
baaabababbabbbbabaaaabbbababaaaaabbabbbabaabaabbbbaaaaabaabaaabbabbbababbaaababbabaaababbbaaaabaaaba
babbaaabbbabaaabaaaababbbabbbabbbabaaabbabbaaaaabbbbbabaaabbbbaaababbbbbbabbbbbaabaaabbabbbabbababab
abaaaabbbbbabaaaaabaaaaaabbbbbabaabaaaaaababbbbbaabbabaaababbbaabaaaaababbbbaabababbbbbbbababaaaabab
aabaababbaabbbbbbaabaaababbbaababaaabbabbbbbbbabaababaaabbbababaaaababbbabbbabbabbabaabbbbbbbbbabaaa
abbabbababaaaaaabbbbabbbbabbbaaabbbbabaabbbaabbabbbaaabbbbabbbaaabbaaabaabbbabababbbbbaabaabbbbaabbb
aaaaabaababbbbabaaabbbbaaabbaaabbaaaabaabbabbaabaabaaaabbabbaabababbababaaaaaabaabaaabbbabbaabbbaaba
bbaaabbabbaaababababbbbbabbbaaaaabbbbbabbbbaaababaaabaabaaabbaaabababbbaaababbbbabbbbaabaababbaabaaa
bbabbaabaaabbbbbbbbaabbbbbbbabbaaaabbbabaaabaabaaaaaaabbaababbaababbaaabbaabbabbbbbbabbabbaababaabba
bbaababaaaabbbaababbaabbaabbababbaaaaababbababababbbbaabbbbbbabaabbbaaaabbbaaaabaaabbabaaaabaabaaaaa
baaabbabababbbbababaabbbababababbaababbbbaabbaababaaaabbbbaababbaabaabaaaaabbbbbbbaaabbaaaababbbabba
bbabbaaaaaabababbaabbbabbbaaabaaababbaaaaaabbbbbabbabaabaaabbaaaababbbaaabbabababaabbbbabbabaaababaa
bbabbababbabbbbbbabbababbbabbbabbaabbabbbbabbbaaabaabbaaababbaababaabaaaabaabaabbbbaaaaaaabbaabbbaba
abaaabaaabababbababaaababbaabaababbbaaaaabbbababaabbaabbbbbaabbaabaababaaaaabaaaabaabaaaaaaaaaaabbbb
babbbaabaabaabbaaabbbaabbbabbaabbababaababbabbbabaabbbbababaaabaabbaabbabbbbbbabbabaaabaabbbbabbbaba
bbabaaaaababbaababbaaaaabbababababbbaaabbbabbabbabbbbabbbbabbbaabbabbbbbbaabababbabbbabbabbabaababaa
babbbaabbbbaababbaaaabbabbababbbabbabaaaabbbaabaababbababaababbbababbabbabbbbaabbbbaaaaaaabaabbabbab
bbaababbbbbbaaaaaabababbabbbbabbabbbaabbbaabbaaabbabababaaaaabbabaabaaaaabbabbbbaabaaabbbaabaababbba
baababbbbabaaabaababbabbbababbbbabbbaabbabaabbaaabbaababbabababbbbabbabaabbaaaaabababbbbaaaabbabbbba
bbbbbbaabaaabbaabaabbbbbbababbabbbabbbbbbbabbabaabaabbaabbbbbbaaabababbbbabbaaababaababbaabbabbaaaba
abaabbbbaabaaabababbbbabbbaaaaabbbbbaaaaaabbabaabbaaaabbabbbbabbbbabbabaababaaaaaaabbbaaabaabaaaabba
ababbbbaababbbbaaabaaaaaaaabbababaaaababbabaabaaaabbaababaabbaaaabbbabbaabababaabbaaabbbbaabbbbabbbb
babababaabbabaaabbbabaaabbabaabbbbaaaaaaabbbbaabaabbbbabbabababbabaabbbbbbababaaaabbababaabaabbbabaa
babaabbbabbbababbbbbbbaabbabbbabaababaababbaabbaaaaabaabababaaababaabababaaaababaabaabaabbbaaabbabbb
babbbabbbbbbbbaaabbbaaaaabaababababbaaababbbbaabbbabaabaaabbbababbbbbababbabbababbbaaabaaaabaaababba
babbbbaabbbaabaabaaababbbbbabbabbaaabbbababaaababaababaaabaabbaaaaaabbabbbbbbbababaaababbbbaaabaaaab
aaaaaabbbaabbbabbaaaabbbbababbaaaaaabbabbababbaaabaaabaababbabbaaabbbabaabbbabbaaaabbbaaaaaaabbabaab
ababbbaabaabbbbbaaabbababaabbbabaabbaababaaaaabbaaaaaabaaabbbbabababbaaaabaabbaaaabbaabaabababbabbba
bbbbbbbaaabaaababaabbbababbbbabbbbbabaababbbbbaaaabbaababaabbabbaabaabaabbbaabbaabbaabbababbabbaabba
bbaababbaaabbbabbababaaaabbbaababaabaabbaabaaaabbbbbbabbaaabbbababaabbbbabbbaaaabbbabababaabbaaaaaaa
bbbaaabaabbaaaaaaaaababaabbaabbababbabababaababbbabbbaabbaaabaabbabbbbbbaababbbaabababbbbbbbabbabbbb
aabbbaabaaaababbabaaabaaabaaabbbabbaaabbabaabbbabbabaaaabababbaabaabbaaaaabbbbaaababbababbbbabbbbaba
bbbbbabaaabbaaabbababbababbbbbabbaabbbaabaaaaaaababbaaabababaabbbbbabbaaabbbaaabaaaaaaaaabbabbaaaaaa
aabbbbbbaaabaaaaabbbbbabababbaaaaabbbaaaabbbbbbabbbbabbabaabaaaaaaabbbaaabaabbbbbbaababaabbbaabbbbaa
aabbaababbbabaaabaabbbaaabbabbbbaaabaaaabbbbbabaabaaabababaabbabbaabababbabbaababbbbbaabaabaababbaba
aabaababbaabbaaaaababaaaabbaaabaaababaaaaaaaaaabbaababbbbbbaaaaaabbaababaababbbbbabbabbbabbababaaabb
bbbbaabaabbabaababbbabbabbbabbbbbaabababaaaaaaaaabbbbbbaababaaababbaabababbaaabbaaaaaabbbaaabbbaaabb
ababbaaababbbbbbaaaabbbbbaabbabababbbbbbaabaaabbabbbbaabbbbbabbabaaaaabaaabbbbababaabbbabbababbaabba
abbbaaaababbaababaaaaababaabbbaababaababbbaaaaabaaaaabbbbbaaaaabbbbaabbbbbbbabaabbababbbaabaabbbbbab
aaabbabbaaabbbaabababaaaabbbaaaaaabaababbabaabaababbaaaaaabbbabaababaaaaababababbaabbabbbbbaabbaabaa
baabaaaabbabababbabaaaaabbbbaaabbbabbbaabbababbabaaaabaabaaaabbabbabbabaababababbaaababbbaaabaaabbbb
bbabbaaaabbbababbbaaabbaabababbaabbbbbabbbaaaabababaabbaaaabbabbbaabbaababababbbaabbbbbbbbbabbbbabaa
babbbbabbbabbbaabbbbbaabaabbbbbbababbbabbaaaababbbbabbbaaaaaaabbabbaabaabaabbaaabbaaaaaabaabbbbaaaaa
bbababbaabaabbbbbabbbbababbbbaaabaababaabbaabbaaabbaaaaabbbabbbababbaaaaabaaabbabababbabaaaababbbbaa
bbaaaabaaabaaaaabbbababbbbbabbbababbaaabbaaabbbbbabbaaaaabbbbaaabaabbababbababbabaabbababbbbbaabbaab
baabbbbabbbaabbbaaababaabbbaaabbbaabaaaaaaabababaaaaababaabababababbaaaababaaabaaabbabaabbbaabbbaaba
abbabaaababaaabbabaabbbbaabbbabbbbbbbababbaaaababaaaaabbbbbbaababaabaabbbbbaaabbaabbbbababababbbbbbb
aaaabbabbbabbbbaaabaaaaabbabbabbbaaaabbabbabababbaabbaaaabbaabbaaaabbbbbabbaaabbabbbabaaaabbbaabaaaa
100 100
abccbaaaababbaacbababacabcbcbaabcabaababbaacacababbbabccabbccbccbaabbbcaabbabbbbcccbabbbcbaacababcca
acbccbcbaaaacbaaabcbbcbbcbaabaaccaaccbcaaabaccaacbbacaccbabbcaabbabaabbabcacccccbacbcbbcbccaabbbaabc
bcbabcbacacabbacbcaccccbacaaccabcbbcbacacbaaccbcbabbacccacbabcbbbbbabaacbbacbacacaccabbcacbbcbcaabbc
aacbaccbacacabbaaabccccbbbabaccbbccabbaccaaacabaaaaacbcccbbbaabaccacbaabaabbaccacbacbcaaaacccbaabccb
bcaabcbbabbbbaacacabbbcabbcccabbcbcbccacabaaccbcacabccbbbacaccccabcbacbababbbabccbaaaababacabbabbcba
bbabbabbbccaaaccaababcaccbaaaccccbbcaabccbabbccccbcabacccbbabacbacacbcbcbaaabcbbcbaccaccaabbababbabb
bbababccacbacacbabcacbaacaaaacacabbcccacbbbabcccbbccabccacabcabaacbcbabbbbccaacbccccbbcaaacacaaccccb
bbacbccccbbabcbabccbccaaabccccacacabbccacbbabccccacbbacbcbcbcabccaccbbcccbbbcacbbcbcaabbcabccbcbaaca
bcbbbacccaaaccbcabbbaaababbababcbccaacaccccbacbabbaabacaaabccbccccbbcbbaabaabcbcbcbcacacbaaaacbaabac
baaacbbbbaccabcbbbaaacabcbbcbacacbbaacbabacaabacbbacbbcccabcccbbcabcaccccbaaccbcbacacbbccbbacbaabaac
cccbacbbcaacccbaccbabbbacaaabcabacccbccabcbbbbaccccacacbbccbcabaabbbbabbacbbaacbcbaacaccbababbabbacc
cbcaccbccbacbcacbcabcacabbccccbbcbabaaacbbaaababccbabaaabbcbabcbabbacbcbacbaaacacbbbacaaaacacbbaaacc
cabaccacbacbacbabccaaacbccabbacabbccacbacababbaaabcbbabcacbcacccbacbccaccacabccbaabbcbccaccacbacabca
ccaacaabccbaabacaccacbcabaccbcbaaaaacbbbbcabaacabbaccbaabbbbaccabbabbbbabbccbcccacbabacbbbcbabcbabba
abbabcaccaaabcaccaccbbbaaacbabbbbccaacaacbacabacbacabcaabaacaaaccabbbbbacbabacabbbacabbaabbbabacbbac
babcaabbbbbabacaacccabccbccabaccabcccbcbacccbbcbbcaacccbcaaabaccbccbbcbcabababccccbabaacaabaacbcbcca
acbbcbababaacabcbbabbbbcbcaaacbcbcbacbcbbcccacaabacaccabcccaccbccaacbaccbbaccaaabccbcbbaacbacbbbbabc
aacaabbbcbaabaaacaacaacabacbbcbcaabaaaccbabbabaabbaaaccbbcbccaabaaaabcaacbcaacbaabccbccabcccccbaaccc
acbbcccbbbbabaabbabacaccaabaacacabcccccbbbbbcbcbbccababbabaacbcbcbbccaaaaaabaccbccabaaabcbbbcaacbbbb
aabcccbccaaaccbaaaacabccbcccbcaaababcbaabaabbccbbabccccbbbabababaabcbabbcbaaaccaccbccccbbabcccacbaab
cabbabbbabbaccabccabaaccbabaacccccbabbccabbcbcaabbabbaaaacbcbacaabbccbacaaacbbaabbcaccacbabbcaccaacb
bcbabcbaccacabaccccaacabccbaacbbccacbaaccbabcbcabccaaababcbcbaacababbcbcbcbcbbaacacbaabcacaabacaabbc
ccaabaabbcaaaaabbbbccaacbccbccbbbaacbcaababcacbbbccccccbcccabbabcccabccaaacbccbccbbbcabbbaacaaaaaccb
abbbbcbaaabcaaaaacabacbcabbacacacaaacbacacabaacabababaaaacbbaabbbcabbcabbaabcaccabcacccbabccbabbacba
babbbbcaaaaacacccbaaaccbcbccbcaaaaabaccabbabbbbacaccaabbabcaaaaaacaacbbacbcbcbcaabcbbaccaabbabbcccaa
bbabbacaabccabcbcacbaaccbcbbbacbcabbaccbcbaabccacabaacbcababbbbcbbbccaaccbacaccbbcaabccccabacbbaabbb
cabcbcaaaacbbacccaaacacbcbbaaacbcbacbcababacaacbaaabcabccabbccaaaaabacccbaacacaabbbabaabbcabbcbcaaba
bcbbccbcaaaccabaccccaaacabaaacccabbbcabcacccacbacacabaacbbabbbcbbaccacccbcacacbccbbbacbabaacabcaaacb
aacbabcbbbcbbcbaaababbacbbbaaccccaababbbbaaabacccbcbcccaaaacbbacbbacbbccacabccabaaaacbbacabcabaabaca
bcababbbccccbbcabccbbcbcbccbbaacccabaccabcbacbacbbaacacabbbcbcaababacacacacbacbbcbbaabbbacccbcabbbac
cbcccbcaaacabcbbaaccbcccbccacccacbbbcbcabccbabaccbabcbbcabbbabacbaccaabacccacaacccabcacbbccaacabcaba
bccaabbcaacbaaabcaaccbaaaccbabccabbabccaaabccccaaccaaabcbbbbabababacaaccbababccbbcaaacccbcbcabbbcbab
cabcbbabbcccbaabcaacaaaaaacaccbbccbcaccbbbbbacbaabccaaacabaaaabbcacbbcabcaacccbcbbbbccacbbcccabaaabc
bbacbcabcbbccbbccccabbbaccabbcacaccaccababbbaaaccaabbbbabaabcbbcacbbaacabbaabaababbbaaacababcbbbcbca
ccbcaaaccbacbabbccbbbbacbbcbbaacacbaaabcacbcbbabacbabacbabbaababbcaababcbabbacccccbcbbbbcccacbaccacc
cbaabacccaabccbacbccccabbbbababcaccabbbbbbcbacaabbcbcacacacbaccaabbaacabcbaaabbaabbcbcaaaccbccbbcbaa
aabaabbaaabbbcabbcbabbabbbbbcacccbbacbcabacaacccabcccabcbbcbbcbcbcacccbaabccccaacabbabbccccbaabcccbc
caabacbabbacaacaacaabbbcccaabbbcbbbbbbacaaccbcacaabbaccbbbcacababcaaacaaacaaabbbbaaaababbbcbcacabcbb
bbacccbcbcaaacacbabcbcbccaacabcbbccbaacbaacbbcbbbbbcbaacbcababccacaacbabccabcacacccaccbbaacaabbcbcbb
bbccbbccacabbcaacaabcabbaaaaaacacbbbcacbbccaccccccbabcababaababaacbbaccbbaccbabacaaccacaaccccbccbcab
bbcccabbbcaccbbbbbcbcbacbaaacbbcbbcbccacbcccabacaccbccacccacbbabbbacabbbccacbbccaabacacacbcbaabaabaa
cbccbbbcccccabcbccabccaacbcbbccaabccbccbcbaaabacccbbbbbababcaacccbccaaccabcbcbcbacaccababacaabcccaba
baccccabababbabcabbccabcaccaaaacacbbbaabbbaabbcacaacacabacacaabcaaacaabababbcabbacccaacababacbbbccab
bcbbcacacaabcbcacacaccccabbbbabaabbcbbcabbcacbbabcbaaabaabbbbbaabbcaacabbcababbbbacaabccbaacbbccbbcb
aaabcbbbbbbcccbacacacacaacaaabcbbcaccccbabbcbccaacccbaccacbbccbacababacababbabbbaababccacbcabcbacbab
abcbacaabbabcababaccababbabcaaabbbcaccbbacbcaabcababbbbaaabacabcaaababababcbbcbcbaacabcabbbcaacbcacb
abacbababbacabaccccbccaaabcbaaaaaaabcccacbcaaccbcbcbccabaacbabaacababaacbabaccaaccbbabbcbabcbaaccaca
baabcbaccaabaaaacacabbbbccacccbbabaacbbcabcbcbaaabcbabaaaccacabccaabaccbbbaaaababbcacacbccacbbacbacb
abacacbcbcbcbaaaabaacaabbcacbcbacbabbbbabaccbbbcbbabacacaaacbaabbaaacaccabaccccbabcabbccaacbbaccbacc
aabaabcaccabccabcabcabababcbccccabbbaacaaacccbcaaccacabcbaacbcabcaabaababaccbaabccbaabbbbbacabcbaacb
bcbcbacbcaccabcabbaabbbabbbcbbbcaccabbbabacbabacbbcabaabcbaabaaaacacbbcbacaabaabaaaacbcaacbabaabbaca
acbbaabcabbcbcbcacababccccccacacccabcacaccbaaacbbbbbaacccacbacbcbcabbbcabcacccccaabcaacbcbaaccacbabc
aacbbbaaccacbccbccaaaacbcbabbcbbbbccacacccccbaccacbabbbbbcbbbbbaabbaccabbccbaabbccccbabbcabbaabaacab
acacccbaacaabcbabacbaccbacbacbbacacacaaabbbacacaabccbabbbbacbcbacabcbabcacbccbcbbcaaccbaccbcaacaabcc
babbcccbbcaccccabbbacbaacabbabaacaabbbccccaabbbbcacaababbbcbbcababaaccbcabcccbcabacbbccacbcaccababbb
bcbabbcbccccbbbbbccaccbacabcabcbcbbcbaaaabccbbaaaacabbbbcbabcabcabbacccbabbaaacabbcabbaabaabbbccbaca
ccbbbbcbacccccccbcbbcccacacacbacabcbaaccbbccaabcaccbabaabbacacbbbacaaacbacbaccccbbacaacacccaabccacca
cccbabacbaccbcbacacbbcbbababacbbbbaacbabbcbcbcaaabacbcaababaabbaacbccbbacabbcbbacacccbcbccabbbcabbcb
caabaacbbcaccbaacbccaabcabacabbbbaaaccbccacbababbacababcbccbabcaacabcacccabbaaaaaaabbacabccabbaccaca
bcababbacbcbbacaacabcaabaaccabbacbacbacbcaaabaabaacbbbaccaabcbcbaccaacacaabcbaaccacbbaabbabacacabaaa
abacccccbbaccbcbcccbccbbabacaabacbcabccabcabbbbacbacccccbacacbcbabaaaabbcbccababbbbcbacbaccaabbbbccc
bcacbbcbbbbbabcbcabccbbbaaabcbcabaccbcacbbcccbaabcbbaacbcabcbabcbcaacccbaabaabcbacacabbacccbcaabbccb
abccbababcccacbbabbabbcbbcbbabbcbbccccbccabbabacaccccbbbbcaaababbbcbbacbacbcbcacabbbbbcbabccbabbacca
cbabcbabbabcacbcbbbcabaaccbaaacaacaabbbabaacaccabacabbbababcbacaacaababccabacbcabcbccbcabcbbccacbbac
abacbccacaabbbaccbbaccccabcbabaacababbcbaabaaabaaaacbabbbbcbbccccbcbbaabbbbcccabbcbccbcccbbbcbcbccaa
abbbbabacbaaacccbcbcbbbababbbbbbabbacccbbaaccbbccbaaacbccbacacbbbacbbcccbacbcbaabcabbbcbbbbccbaacbac
cccabbbacbacbaabbbbaaccaccabbcbbbbcacbabaababccacbabbabbcbcbcacbcaacaaacbabaccbaccaabccacaaaabcbbccb
bbcbbbcabbbcacbcbccaabbccbbbaaaaacccbcaacbabacacbaccacccacccbabbbcbaabaabaacbcbbbbacaacccbccaccaacba
ccbbaacccbabccbaaccabbaabbcbcabaacbaaaabcbcacbbcacbbbacbccabbbacacbbbaabbbcaacbacbbbbbbabccaaabcaacc
caabaaccacbcbbababbcccacccabccaaccabccbbcbcbbaccabcaabbaaacbcabbcaacbbaaababbbabbabcaccababcabbabcca
bbacbbbcacaaaaabaaaacaabaccbcaaaabaabcacabbcacbbcbacbbbacccbccbcbcccbaaccabccaaabaccaacacacccbbaacaa
cbbcbacbabbcbaacabccbaccabcababaabcccacaabcccbabccbabccacbbaacbabcaccbabccacacbbcbacbacbaaabcccacaaa
bcccbabaccaacbbccbbcacbaabccabaacccacccaaababbcccbcaacabcbabbbbacaccaccaaaabacbabbacbbcaaaaaacbababc
bbbacccabbabaccaacbcbbabbcbbbacacccabacaccacaaacaabacabbbbacbbccaabacbcacbccacabacbbbabbabbaaaacaaca
ccbbbbccbccababcbaaabccccaababbababacbcbaabacbbbaaaabaabbcaacbccccbaabbcbcacbaaabcabcacaccbbcacacaab
cbbbcccacacabaacbcbcabaaaaccbacaabacaababaacabcccaacbbaaabbabacabcbaabccabbaccccccbabcabbabbbbbabacc
bccccabcabbccbacabbaacbacccacccbcabaacbcabbcbccaacbccccbbbaccaaabababacccccacccaaacabcccaabababcabbc
ccaaccabcacbcbbaacaaaabcaaacbcaaabbbbaccbccbabcabccabacabbccacacbabcabaacbcaababccaacbbcbacbacbbbaba
bbaaaaaaaabbbabbcaaacbbaababaabbcaabcababaaaaaabcaabaaaabaaacacabaaabbccbbccacbcacbaccbcbcaabbcbcacb
cbcccacaccaabcccccccbcacaccbaabbbaaaacabbcaaacacaccccacaabcaacccbcaababaacbcabbacbbccaaaaaaccaaaaaac
bcaaccaccaacababcbccacccabcacacbabbabaccbbbcacacacbacaabcbcaccaccbbcaaccabcbabbcacaaaaaccbbcbcacaccc
bccabccbabccacaacbcbcacabbabcaacabaabcbacababbcacabcbccbbbbbcbbbaababcbbbcabaabaaaabccccbcabcacbcabb
abcbabcbbbbbaaabccaacbbbbbbaabababbcccacccabaabbaabbaaccbcacabaabbbcbbbccccbccaacbabbabaccacaccbbbbc
bcacabbcbaaaacacccabbcabcaacbbbaccccbccabcbabccbbbabbccaabbcbbbaaaccaacabcaaaacacabbbaaaacccacabacba
acabaccbabacbbaaaacbcacbcacbbcbbcaaccacccbcaaacbbacacaababbcabccccabbcacaccacacbccacaaaaabbcacbbcaca
ccbaabaacbabbaaaaabbbaaabccbcbbbababaacbbaaacbabcaacaabacacbaaacbbccabbaabbcaaacaacabcbcbbaaabbcccbc
baaabaaacbbbcabbbbabaababbacbcbbbcaaaacabaaabbcaaaaaccacabaccaccbcabcbcabcbbcacbcaabbacbccbbabbbaaac
bbcaaaababcaaacbbbacbabbacaccabbbcaaabaaabbaacacbbaaccbacbabaccbbcabbbcbcbbccbbcacaacabcaababbabaccb
bcacbcbbccbcabbbabaacaccacaabacbbaababccaacbbcbaaabaccaaaabbabcbbbbcaabccccaaccbcabcbbaaacbaaaaaabaa
aabaaaaacbbcacbcbbcbbccbbacaabccabaaabbaccabccccccccbccbbbaacccaacbcacababcacabbcacbccbacccaabccabcb
bacccacabaaccabacabbbbcbcbbaacabaaabaaaaaaaabaacccbbcabacaacbbccbbacabcccaabbccbbaacccacccccbacaaaac
cbbcbbabbabcbcbbaccbcaaaabbbbbcccbbabbabaaacaabbbccbaaabcabcbbcacbcbbbcbccbaabbccbccbaacacaacaacbcbc
cbbcbaacbbbabbaccccbbbbbacbaabbbccababccbbbcacaccacbbbcbbbccaacccbcbbaacaccaaccccbbbcaaccccbabcbbbcb
bcacbbbbaaabcbaabcbcccccacabaaaabbababcccbbbbaacacabbacabcbabbaabbacbcbaaaacccccbcacbbcbcaabccaabcab
acacacaaabbacacbcaccbbcabacaabccccaaaacacacaabccbbcbaccaabaaabccbbbcbcbabbbcbaccbcbbbaacacbcacbaacab
caccccbcabbbabaacabccaacbababcaaabcbbccbbbccbbcabbcccbababcccbabcbccccbaacccabccbcbabbaaacbbbaabcacb
bcaccabaabbbbccccccbbccaabbcacbbacbacbbbcbabcbacacabbaaabbcbcbbbcccabcccbbbcbccabccbcbbaaaabaacabacc
abaaacbaabbcbbcaabccaaaabababccabaacaacccbaabcbbccacaaaabaabcaccacabcaabbaccbcbcacaccccabccbcbcbbbbb
bcabacbcbaaccabcacaacbccbbabcaaabacbccbbcccbcbacaaacabbbacaabaaabcaaabccbcccacbbbcbacacacbbbabaabbab
aaabcabbacbccacaaacaaabaaabbabaccbaabbaccbccbcccccccbbabbbacbbcbabacacaabccabbaaaaaaaccccabaabccbbac
100 100
ddaadbcbccddccddaaddbacddaddbdbaaccbbcbadbabdbbcacdaaddbaadcdbccdcbadbccaaadaaccdbddcbbbcdbaddccadbb
adbcbbcaadacbcbdaacaaaccabdbdacdacbbccabacbdbddbbbabdbbacddbbdacadadababcbcbdccacbabcbabbbdcbdcdddad
cadbbadddbcbbcddbabbcdcaaabcbaccabaabddbbccaaccaadbcaccbbdccdabddcbdddabcaaacdaaaaabdabaaccaacddcbab
ccaacccbaddcaacbacbdbcaaabccbacdccabdcbabbbdbdcdcbdcbddbadadacdbabacddbbbbacbcccbdcddccdddccaddcdbad
bbcabdbacdaaccbddbcdbbdaadcddadbcaddaddaaabbabdbccdbcbcbbcddbacdbacbcbadbdbcdabcddbaddcacaddaacdcbba
dbcbdcddacabccdbddbcdbcdaaacbdbaadcbbabdcbbaacdddbbcacaccadddccdadadaabdbaddacddbbcbcbbaaacddddcabab
daacbdadcaabaacdadacbaabbacacbcacdcbdccacdcabaadcbcacacdcdbcaabdcbdacbdbbdaaccdbbbdbbaabbcbdcacacccc
dbadcaadcdacabdcbacacdcbcdbdccadaaabccacbbdcddcccbaacaaacdcbcbcaddbaabbaacabdbacbbbaadcbccbcddbbadba
acdccacbdcacbbcbadbaadbbababcccacdcddbdbdbdbccacddbacbdcbbcbbcbadbbbdabdaabdbcaaabccdcaddacbbbbccbca
dbbdbcccbdbcdaababbcbdbacbbddbdbcadccdbdcacbaadcacbddadcbaacddbabbcaddabbacbabcadbddcbaacadabbdadaaa
bcbcbbcbcdcabccbbaacdadabbdcabdddabcccccdddcdbdcadcdcabaacdbaaaaccacadcdcdbbacccabdacaaabdbcabdaaccc
aabbdadcbcdaacdaaadbacdbdadddbcbbbbdccdabdbbabcadabdccbbcccadabdacacacdaaccabaaddadbbdbcdbcacbdcaddc
acabcaacbcacaabaabbcadacccadbacccacaadadcaabdbddaadcbcacdbabdcacddbbbbccaacddbaddabbaaccdadcdddaccad
babdcddbabbaabaaddbaacacaabbddacacddabdcdcdbdadccbdabcacccdacbcadcccccbddcacbdabdbcddcdccdbcaadccadd
bdcdadabbdbbaddbbbbbdbdcadcdddcdacddddbddbdaadcbddbabdacdacbabdcdbcddabdadcdabcdcabcbabcadcaabbddcdc
abccddcadbbbaadaccdadcdbadccddabdccdaaddbdbaddabaadbacbacaaaddadcdbaabaacddddcacdcaaadaabcababcbaabb
cacbdbdaddcdaabccbabcccabddccbbdcabbdbbdddadccbcdbabdabccaddccacbbbccaabddadcabcbbbcdbdcdabddddbbdcb
babcabdcdcbccddacdcbbdddcacbbcdbddbbbdbbbbbdcbcabadcdbddbbbbccbcadbdcdcdadbbdbcbdccccccccddccdacbcad
adbbbbaddbcaadcbbcabbabaabadbcbcccacdadcbdabbbbcacbdabacaabbabddadbaccdbcccdbcbcdabbbdcadbdbdcddcaba
dbbbbcbdabdadbdcaadaacbdbbbcbaaabdabcdaaccdbdcaddcbddbacccbdadbaacdccbbdabbadbaaaacabaaccbddabcdbbba
dacabcacaadadcaabbbacccbacbcdddcdaaccbbdbbaacdbcdccabbdcacdbccbbcbdbccbcccbddbbaabbcaccbacadcbdadddc
bbcaacabbdccdbabcbddbadaaaaacdabdcaabbcabbdbacabdccdcbcbddcaddbbbcbdaddcbddbaabddcccdcdcacdbdaddcdda
caddabdbcdcdddbabbdccbadbdcdccaababadadccdbaccbadaccbbbbbccdcaccaddbacddaaadaaddbbabbabdaddcbabdabdb
cacbbcadcacaacaaddccbbacdbdddccbbdbaabbbdbaadcadcdccaddabbcbdcdacbbdbbdadbdccacbcccdcdcdcdacabadaaac
bdbbcdbdccdcaccdbacaccdbbadbdccddbaabdadcdcadbcbaccccaadcbbdabbdaabaaaabcdbadbbdabacaacddccbcddbcbcb
badccccbbbabdbcddcdcbbccbcccdddbccdbdadbababacbcacbadabccbabcbcbcdcdabcaaacadabdbababccddabaabbabbcd
ccadbababacbbbdcdcdcddddacbaabacdbacaaabbaabaddaccccdcbdcdcbcddabdaaaacdabccddbdbbdbbbcadcaaaabaabcb
caabaacbbbacbdadaadbccdbacaccbddbbcdddcbdcbcbaabadadddcdacbdbbddbbacbacddaacbacdcdbbcbddabadbdcacbcc
abaddbbabddabcbaabaaccbbabdabcdccadacaabcbdacbbaabcdaadcacddbcbddaccbaaaddcbdbcadcadcbacabdccccabbcc
ddcbbddbcacadaabcacababbbdccccdaaadcccaadabccaabcacaccbdbadabbbabdaaabddadbdaabcbdadddbbcaaddbdabaac
dcbbddacdcdaaadbbddcbbadcccdadccbdcaddaabacbcdbbccbdbcadbbddcabaadbbbddacaccdaaaaabdcdaabaaaadcbabac
adbaabccdabbdcddaaabaabababbddbdadaabcdddbabccbdabddbbaacdcddabacddbabbbcaaabbccbcdbaaddbbaadaadadbd
cbababdbaabbadcacdacaabdadcdaddbccadcbdaabdddabacdbadbdbbbcccdbaaaacdcbdacabbbaaabddabdcccbabdddadbd
dcbdabacdccababdbcbbdcddbaaddddbddddbacddabbadbbccbcbbaacabaabcbcddbccdaabddbabbbaccddacbadbadccabab
ddaacdbbbcccadbbbbdcbbacbccbcbdaaccdcadadbabcbccabadcbabbdacdcabcbacdcbadbdbabbcdaadbcbdaacadcdcadbb
bdcabccdbdcbdddcbdbdadbacadadaadbbdacadcbdaccabbcaccdcbbbacbcacbbdbbbdadabbbcbcaaacdbdbadccbbaddabcd
ddccdbddcbbcabbaaadabdaaacdaddcbcabcbddadadabcbbcdbccbabadcaabdaadaadabdababadbdcdabcbcaaddacddabcbd
acabbcacaaacbaacbdbcadaacbdaaccaaccbdcddbbdbccabaacdbbddcddabaacdbbaabadddcbbbcbcccccdbcbbdbacdccbcb
ddbcdabbcbaddddaddbaaaddbccaaabbbaababdcccdcabbabdbcbccbbdddbabaabcacdbaaaddaccddcdadacaaaadbdabdacc
caacbaabdbaabaabcdbdadccbaabcccadccadabbcbaaaaacdbddddbbbdcdcdacbdddabdddacdcadcbacdaabddacacacdbbbd
aadcbbcacdbbadbaacbcbcadcdcdcccdbdcdbaadbbbbbbdccbdccddbdcadaaaabadbbbdcbcaacabacbbadcbcaacdacbcacbb
aaacbdcccdddacaacaabbaccbabaaadcdbdcbcdaccbcbbabcdbcdacbdcccdacbabaacadcabccaaadaaddbdadcadbabcbbcda
dbbddaacbacacdabdbbbdcdbadddcbddbcddadbdbcacdbcdbcadbadbccbdcdcbcbdabccbdadbdaddacdabcdcccdabccbaacd
abdddadcdcbbdbaacbddaddddaaadbddbbdbcadacbacddaaadcbbbddaddbbcacdaaadcbaadccdadadbbaaadbbbbbacdacdaa
cbdcccbadabdaabdcabbcbaddbbccdaaaacbdadbdabcccacbcabbccadccaacababccdacaacbbbbccdadaacbaddcbdcadcdda
ccdcbdddcdbdaadacabcddbcdcdbccbabcbccaaadcdadaacaaaddcccabcdbcdcdacbaaabdbccdccbbcacaaccdbcccdcbbaac
ccccdaabdaacbcdabcbbabbccccbccadaaacbdbaaaaaaadadcdabbdcabddcccbdbacacddabaadbbdbbadabcdabadbacccadb
bbbdcdbcbdaadddbababccdaabacbdbadacadcdbddcbbbbdcbccdbcdcddaabcccddbcbbbdcbdabdaababcacadaabacbaccad
ddbddccadbcbaccadbdbacdbacdcabbbdbbddbbacdbbccaaddbbadadbbbddbbaaacabbcccbdbbcbabbdcdbddbabadabaaaad
daadbcdbbddbbbcbccdddbdabdcadbdaabbdcccacdacdccbabcaabbaadcaaaccbddbcaacbaaaaaddbbcbcbbdacbbdddbbadb
dcbababcddbccaddadacccbdadacadbaadaccbcbbdadbbdbcacbbcababcbdaaccdddaccbbadbbabbbbddbcaacdabadccacaa
accbdcdbdbadabdbdbdacdadcabbcbabcdccdbadbabaddbccbbaaaaccdccacdbaacdcbccccaacbcdcbaabccdcabcdcbaabbb
dcbdcbbccccddbdbbaacbabbcbbdbcbddbabccdddcbdcbbdcaccdbacbaacddacaaabbcacdbdccbdbcbcdbaabbbcadadbabbc
ddcaadabacbaaddccccabcdcacccdcdbbccbbadaccddbcadcbcabbdaddacdbcccaaadabcccadddcbcdaacacacaddcabacaab
adcaadbaaabbbdabdcdbacbbdbbdcbbbcbcbdddbacaddabcaddbcddddddabbaabdacdaaccbbcbaabcdcbcbbcbcbdddbbddcc
aaaaccccccbcdbaaccdcbcdabdabcdcccbbdadaaccaccdadbaacaddbcbbdcbbccbbcbcdabaabaaabacbcabdbcbdabddbaccc
abdbaadcdbcdbadddaacbdaabdddcdcdbcaaccdccadadbabbacaadcccddccabababaacbbbcdbddadbbbbcbcdccbddbbbccdc
aabbbdbcabbcdabcabacddcbccbddcccbbdbbadccdbcddbcaadaaacccdacbdcdadcdcddbbbbbcdccaabacaacdadbcbdbddaa
cbcbcabcdbabacadadccbbcbbaacbcddddaaacbdcddbcdbacbccbdbbdacdccaababcaabbaddcabaaacbbcadccbbddbcbcdaa
adadaadbccaddddaabbababddcdaacdbcbacccbccbdaccacadacbdcccabbcaaccddbdadacbdacaaabacaadacabbbbbadccbb
bacababcbccbdcddbbcdcadaaaddababdbbbabbdbcdcddbdadbcdbdbddadaddccdcacadcccddabcdccbdaabacbbcacbaacda
dbcacacdcdaacdcbabadcdabcbdcacbddaabdcaccbbcabdbdabdcdcdbabbcdacdbdabcacddbabdccbbaddcdbcddadcadcaab
ccdabaccddbbdabbaacdabaacbbcbcccabbdaddbbabcacabbcbadbcaabcccbdacdcbbbdbaccabbaacccbdadbddaaacbcbacc
dddbcbddacdcabcbbdacbbddacccaaaddbdccbcbdcdccabbacbacbdaadaaddcaddddbcbdcdbbacdabbbdabaddddbcbcabbcb
cabaddbcdcddcbccbdbdbabbccbdbababdcbabccbcdcbaccbcabcabdcccdbcbdcaabaababbbacaccccdadccdccdcdbaccbcc
acdbadcbddcdccdaacbddacaddccadcadccbadcccdcbaaaddacbacacdcbdadcbbacdadaddcbdbdbdcaabbcbdbbdadddcdaba
bdcaacabdddaabbadcbbbaccababdcbdcbcddcaabbddccdbbaabbcabdddcacabdcbddcdaaddacadbdcbbdbbabdcbdaabacdc
bcbaccdcdabacdcbcaddbadacacacbdaacabccbcccbbbdbaddbddcacacbbaadcacccaaddbcdbabddaccadbbbbddbcbbabcaa
bcdcdbcdaddcabdbcbaccbcabbcbaccdacdcabdadadaabaddcdaccdbabccacacbcdabacaaabbcabbdaadbacbdabdccccbabd
badcaacdbdbabdbbabdddbcdaddcdcaaadccbccdbdbabddacdbadcdcadbddcdddacbcdbadccadabadacadccbcacacdddbcbd
ddcdcccaadbcadababaaaadcdbabcdbdbdddcbbbdcbcaaacadacabdacacaccdcdbccabbdadcdddcbcaaaccaddaabcdcabdaa
daabaaabbabddacbacaddbaabcaaadbcdaaacddcddddbdacadadbdaaaddcddaabadaccddaaccdbacbaaaccbbccadccdbdaba
bdddbdddbcccababaccaddddcdacaaaacbaabacdacacacddbabbddabcaacbadbbaccadccdcbbbddbbcaddadccadcaabdcdbc
cbbddaaadacadbbdcddbcdbcaadbcabaaabcccccdbbddccbabbddbbbbabaacbdbcdaccdaacadbdaacabdacadabddbccabbdb
dcdbdacabccadcdccccbabadacacbdbadabccbbbacccdbdaabddcbbabddcacbcacccdcddccccddaacadaacdbabddcacdbddc
cabbbaddcdddabcbacaccadcdabcddccbbdaddbcabaadbdccdaacbbdaccdbcdbcdbaddaccadacbdcadbdacdbbcbddaaabbca
cadaccacbdcbaabcbbcaaaccbbdcacaadcaddcddbbaabbccaaccdaadabcababbcbbacaddbbbdaccdbbcabcaddadcdccddbdd
bbbbbbabadbabdabcccbdccddacbddcdddbccacdbdbbdccddacccdbdacdabbbbaddbccdaabbddbbcdaacdacdcaddbacabbcd
addbdcacbcbddddaddddbcddabdbbcadbcccaddbcabcbdbaaccccadabcbdaadcdbdcdacbbddcdcaabdabaddbabaddbadbaab
dbbbddbabcbbcaaddbddcadbbdddabdaacdcdaadbbdcddabadcbcbaacadccbbdcababdaabbabbccdcccdadbadccdbacbcbac
bcbcbaccaadacabdbbddddcdbcbdddcaacccdbcccbdacdadabccccabbadbbaddbaaabaaabbcbabcdbccabdacbabbbcbdacad
cbacaaaadabaaaccdccbbabccacdccadddcbacaaaddccdadadbdccdcabaaccacdbbaaddccbbacdcbacdadabcddbcaacccaca
adbbbadcbbbaadcdabbbabbabdadabbaaccdcdbccdbcdcdababacdccacdccaccbacaacccbcbacdbadddccbdbbddcdbbcccac
dbacccdbddcdbbaadddbbbaadbbbdcccdabdcabcaaabacdbbbdbcacadcadbcccbdcaacacbdbadcccaadcdaabcbaddabcaddc
acadabddcbddbcddbbaaadccbcccacdbddbbdbcabddddacbcdaacdcdacdbcbaaaacbccaabacdddbdbcbcdadddccdbbaaddad
dcacbbacdbbdcdcbdacbcbabcaaaaddcaabccaabbdaccabcdcaccdbddaabaaddadacccadacccacabccdcbabacdadccababbd
dacbbbbdacabaddacaabcddbdbcbdbaabadddddadcbdbdcacdbbadddcbadbdadcadaccccaadccbcadbbbddccdcdccdcaacbb
dbabddbdccbcacaadcbccadcdbcadadbbabdbcbbcabcbccdbcdcadaadcadbbdbadddbdbbbadbdbdcdccdadbadaaaabcaacbd
dbccdcccbacaacaadbabbacadaadcbcaaaabacacabbcbcccdddadcbcdcbbbadbcadcbbdbcccdadabcddabdcdddadcdadabca
bbacbbcaadcaadaccbbddddbacbbddcaaadcaaaabdaddbcccccbdcacdcbabcdbdaaaabcaaababaadbbbbaaaddbbdbcbabdcb
accdaadabddcdbbabbcdbbcadaaacadaacbcbaacaaacbaacdbadaacaacdcddbcbbdbabbabcaddbacabacaabbdbaccdbdcdad
acbcabcddacbcddbcdbdacbdccdcdaabbccbcbbadbbdbbbaadabaddcadcaaaccadcbbcaccadddbccbdaaccccccaacdddaacb
daacbbcbcbcdcdddcbbaddddabdabbcbadbacadcbaabbdbdbcbdadaadccaaccdddddabccbbbbbcaacadadadabcaddcbaabca
aadabcccdcdbbdbccdadacacbabdddbcabcbbcaccdbdddacbacaaadbdbacbcbcdbcacbcbcddbdadacacdacbddcdbbdcdbcac
cddaddbabcaddbabaccbadcbdbacdcacaacdcdddbbbaabacaccccaacaddcadcbbaabcdadabdcdccbaabdccddddcaadcdddbd
dacdbccccccdbccaddbbaadaabddbcbacadaaacabadaddcabbddababdaccdddbcbaccacccacdadbdbcbcbacabcddcdbbdbaa
cadddbdaccddcadccaaacccdbdbbccbdbbbbdbcaaadbabacabacdadbababcdbcbaabdddddbdaadccbdacdaccadcaddccaaac
cdbabbbcbbddacbddcccaacccaccbabbabbabacdddabbcdbccaaadcacbcdbccbbbdcaccadbadbacbaaaabcacdcbbdbadcadd
adbaddbcdccdbbcacababdbddbddcabdaacbcbbbabcccdbbdbbabaaccbdabcabadcabdbbccddcddcabdbcbdbddacadcbbcba
cbbcddbcbccbcabbbdcbccbccbbbcddcadbddcacacdcacbbaabbdcdadcccdaabdbbaabadcbccddaabbdcdaddaaadbaadaaad

Output:

Code: Select all

Test Case #1
Query #1
bye 1
Query #2
one 1
two 1

Test Case #2
Query #1
hello 4
madam 2

Test Case #3
Query #1
x 1
Query #2
x 2
xx 2
Query #3
x 3
xx 4
xxx 2
Query #4
x 2
xx 2
Query #5
x 4
xx 12
Query #6
x 6
xx 22
xxx 4
Query #7
x 3
xx 4
xxx 2
Query #8
x 6
xx 22
xxx 4
Query #9
x 9
xx 40
xxx 16
Query #10
x 16
xx 84
xxx 48
Query #11
x 25
xx 144
xxx 96
Query #12
x 10
xx 18
xxx 16
xxxxxxxxx 4
xxxxxxxxxx 2
Query #13
x 10
xx 18
xxx 16
xxxxxxxxx 4
xxxxxxxxxx 2
Query #14
x 100
xx 684
xxx 576
xxxxxxxxx 96
xxxxxxxxxx 44
Query #15
x 10000
xx 78804
xxx 77616
xxxxxxxxx 70656
xxxxxxxxxx 69524
xxxxxxxxxxx 68400

Test Case #4
Query #1
a 4965
aa 19242
aaa 9406
aaaa 4574
aaab 4685
aab 9559
aaba 4731
aabb 4679
ab 19871
aba 9832
abaa 4731
abab 4933
abb 9756
abba 4808
abbb 4789
b 5035
ba 19871
baa 9559
baaa 4685
baab 4746
bab 9986
baba 4933
babb 4921
bb 19820
bba 9756
bbaa 4679
bbab 4921
bbb 9762
bbba 4789
bbbb 4832
Query #2
a 3360
aa 8964
aaa 2976
aaaa 1020
aaab 1000
aaac 923
aab 2999
aaba 1026
aabb 933
aabc 994
aac 2862
aaca 961
aacb 972
aacc 891
ab 8859
aba 2930
abaa 1026
abab 960
abac 895
abb 2886
abba 950
abbb 966
abbc 904
abc 2914
abca 964
abcb 958
abcc 961
ac 8652
aca 2906
acaa 961
acab 955
acac 930
acb 2887
acba 964
acbb 924
acbc 935
acc 2747
acca 924
accb 902
accc 875
b 3359
ba 8859
baa 2999
baaa 1000
baab 980
baac 969
bab 2908
baba 960
babb 977
babc 932
bac 2825
baca 955
bacb 922
bacc 907
bb 8814
bba 2886
bbaa 933
bbab 977
bbac 941
bbb 2892
bbba 966
bbbb 936
bbbc 946
bbc 2881
bbca 924
bbcb 994
bbcc 926
bc 8758
bca 2887
bcaa 972
bcab 922
bcac 951
bcb 2936
bcba 958
bcbb 994
bcbc 938
bcc 2831
bcca 902
bccb 918
bccc 972
c 3281
ca 8652
caa 2862
caaa 923
caab 969
caac 926
cab 2825
caba 895
cabb 941
cabc 948
cac 2820
caca 930
cacb 951
cacc 906
cb 8758
cba 2914
cbaa 994
cbab 932
cbac 948
cbb 2881
cbba 904
cbbb 946
cbbc 986
cbc 2806
cbca 935
cbcb 938
cbcc 897
cc 8488
cca 2747
ccaa 891
ccab 907
ccac 906
ccb 2831
ccba 961
ccbb 926
ccbc 897
ccc 2778
ccca 875
cccb 972
cccc 886
Query #3
a 2516
aa 5008
aaa 1256
aaaa 306
aaab 330
aaac 302
aab 1248
aaba 312
aabb 324
aabc 286
aac 1209
aaca 278
aacb 307
aacc 300
ab 5002
aba 1240
abaa 312
abab 317
abac 294
abb 1255
abba 288
abbb 307
abbc 341
abc 1197
abca 289
abcb 317
abcc 298
ac 4942
aca 1206
acaa 278
acab 302
acac 291
acb 1227
acba 289
acbb 313
acbc 299
acc 1225
acca 294
accb 288
accc 303
b 2506
ba 5002
baa 1248
baaa 330
baab 324
baac 286
bab 1262
baba 317
babb 313
babc 304
bac 1205
baca 302
bacb 301
bacc 290
bb 4978
bba 1255
bbaa 324
bbab 313
bbac 312
bbb 1210
bbba 307
bbbb 270
bbbc 299
bbc 1230
bbca 313
bbcb 280
bbcc 298
bc 4906
bca 1227
bcaa 307
bcab 301
bcac 313
bcb 1236
bcba 317
bcbb 280
bcbc 316
bcc 1196
bcca 288
bccb 316
bccc 289
c 2498
ca 4942
caa 1209
caaa 302
caab 286
caac 280
cab 1205
caba 294
cabb 312
cabc 290
cac 1238
caca 291
cacb 313
cacc 299
cb 4906
cba 1197
cbaa 286
cbab 304
cbac 290
cbb 1230
cbba 341
cbbb 299
cbbc 272
cbc 1192
cbca 299
cbcb 316
cbcc 276
cc 4934
cca 1225
ccaa 300
ccab 290
ccac 299
ccb 1196
ccba 298
ccbb 298
ccbc 276
ccc 1212
ccca 303
cccb 289
cccc 312

[mf]

My accepted program's output is almost the same.
But for single-letter queries I print (the number of times that letter occurs)*8.

[Moha]

Yes, Because of we have 8 direction, we should count each single letter 8 times. just like madam in problem-statement

[Cho]

But for single-letter queries I print (the number of times that letter occurs)*8.

Oh.. my code generates correct output naturally. But I thought counting the occurence of a single character in all eight direction is wrong. Then I specially handle those single character case and then got WA.
Thx for your help.