Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 3.0 Seconds Memory Limit: 65536K

Total Runs: 242 Accepted Runs: 97

MIKE is together with his girlfriend more than a year. And his girlfriend has a lot of problems. But Mike finds some regulars can make her pleased after concluding a number of key words. Now mike has something to tell her which has many ways to say. It is now want you to figure out how many kinds of words match the key words.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (Mike is 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.

The first line of input contains 3 integers, L (0 < L <= 15), D (0 < D <= 5000) and N (0 < N < 500) separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in Mike's words. 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.

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 key words match the pattern.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

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz