Code Jam Qualification Round -C

Welcome to Code Jam

In the practice contest, you may try as many times as you want.

Small input
10 points

Download A-small.inMore options   ▼

SubmitYour submission was received. You can still resubmit for minutes.
Only your last submission counts.

Time Remaining:   

Input: A-small-practice.in.

your output file:

source file(s):

remove Add another file

source file(s):    not needed for the practice contest

  

Large input
23 points

Download A-large.inMore options   ▼

SubmitYour submission was received. You can still resubmit for minutes.
Only your last submission counts.

Time Remaining:   

You may resubmit this multiple times within the remaining
time-frame. Only your last submission will count.

your output file:

source file(s):

remove Add another file

source file(s):    not needed for the practice contest

  

Problem

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

Input

The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.

Output

For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.

Limits

Small dataset

1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10

Large dataset

1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500

Sample

Input	Output
3 5 4 abc bca dac dbc cba (ab)(bc)(ca) abc (abc)(abc)(abc) (zyx)bc	Case #1: 2 Case #2: 1 Case #3: 3 Case #4: 0

In the practice contest, you may try as many times as you want.

Small input
10 points

Download C-small.inMore options   ▼

SubmitYour submission was received. You can still resubmit for minutes.
Only your last submission counts.

Time Remaining:   

Input: C-small-practice.in.

your output file:

source file(s):

remove Add another file

source file(s):    not needed for the practice contest

  

Large input
23 points

Download C-large.inMore options   ▼

SubmitYour submission was received. You can still resubmit for minutes.
Only your last submission counts.

Time Remaining:   

You may resubmit this multiple times within the remaining
time-frame. Only your last submission will count.

your output file:

source file(s):

remove Add another file

source file(s):    not needed for the practice contest

  

Problem

So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".

To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

Input

The first line of input gives the number of test cases, N. The next N lines of input contain one test case each. Each test case is a single line of text, containing only lower-case letters and spaces. No line will start with a space, and no line will end with a space.

Output

For each test case, "Case #x: dddd", where x is the case number, and dddd is the last four digits of the answer. If the answer has fewer than 4 digits, please add zeroes at the front of your answer to make it exactly 4 digits long.

Limits

1 ≤ N ≤ 100

Small dataset

Each line will be no longer than 30 characters.

Large dataset

Each line will be no longer than 500 characters.

Sample

Input	Output
3 elcomew elcome to code jam wweellccoommee to code qps jam welcome to codejam	Case #1: 0001 Case #2: 0256 Case #3: 0000


def isSubStr(w,b):
    #print w
    #print b
    if(len(w)==0):
        return 1
    else:
        if(len(b)==0):
            
            return 0
        if (w[0]==b[0]):
            
            tf=isSubStr(w[1:],b[1:])
            wf=isSubStr(w,b[1:])
            return tf+wf
        else:
            return isSubStr(w,b[1:])
            
                
FileIn=open("C-large.in","r")

content=FileIn.read()

content=content.split('\n')





matchStr='welcome to code jam'

caseCounter=int(content[0])
print content[0]
#print content
i=0
FileOut=open('result2-l.out','w')

while i<caseCounter:
    
    #print content[i+1]
    #print isSubStr(matchStr,content[i+1])
    result=isSubStr(matchStr,content[i+1])
    result=str(result)
    if len(result)>4:
        result=result[(len(result)-4):]
    else:
        result=result.rjust(4,'0')
    FileOut.write("Case #"+str(i+1)+": "+result+'\n')
    i=i+1
    
    
FileOut.close()