Little Elephant and Strings
Problem code: LUCKYSTR
All submissions for this problem are available.
A Little Elephant from the Zoo of Lviv likes lucky strings, i.e., the strings that consist only of the lucky digits 4 and 7.
The Little Elephant has K favorite lucky strings A1, A2, ..., AK. He thinks that the lucky string S is good if either |S| ≥ 47 or for some j from 1 to K we have that Aj is a substring of S.
The Little Elephant has found N lucky strings B1, B2, ..., BN under the pillow. Now he wants to know which of them are good. Help him and find for each i from 1 to N whether the string Bi is good or not.
Notes.Let S be some lucky string. Then
- |S| denotes the length of the string S;
- S[i] (1 ≤ i ≤ |S|) denotes the ith character of S (the numeration of characters starts from 1);
- The string T of the length M is called a substring of S if for some k from 0 to |S| - M we have
T = S[k + 1], T = S[k + 2], ..., T[M] = S[k + M].
The first line of the input file contains two integers K and N, the number of favorite lucky strings of the Little Elephant and the number of strings he has found under the pillow. Each of the following K lines contains one favorite lucky string. Namely, jth line among these K lines contains the string Aj. Each of the following N lines contains one lucky string that was found under the pillow. Namely, ith line among these N lines contains the string Bi. The input file does not contain any whitespaces.
For each of the N strings that were found under the pillow print Good if it is good, and Bad otherwise.
1 ≤ K, N ≤ 50
For each string S in the input file we have 1 ≤ |S| ≤ 50.
Each string in the input file consists only of the lucky digits 4 and 7.
Input: 2 4 47 744 7444 447 7774 77777777777777777777777777777777777777777777774 Output: Good Good Bad Good
The string S = 7444 is good since the favorite string 744 is its substring.
The string S = 447 is good since the favorite string 47 is its substring.
The string S = 7774 is bad since none of the favorite strings 47 and 744 is a substring of S.
The string S = 77777777777777777777777777777777777777777777774 is good since its length is 47. Note, however, that S does not have favorite substrings at all.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.