Little Elephant and Strings - LUCKSTR (CodeChef Easy Question)

Link to the problem :-

Little Elephant and Strings

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 A₁, A₂, ..., A_K. He thinks that the lucky string S is good if either |S| ≥ 47 or for some j from 1 to K we have that A_j is a substring of S.

The Little Elephant has found N lucky strings B₁, B₂, ..., B_N 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 B_i 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 i^th 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[1] = S[k + 1], T[2] = S[k + 2], ..., T[M] = S[k + M].

Input

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, j^th line among these K lines contains the string A_j. Each of the following N lines contains one lucky string that was found under the pillow. Namely, i^th line among these N lines contains the string B_i. The input file does not contain any whitespaces.

Output

For each of the N strings that were found under the pillow print Good if it is good, and Bad otherwise.

Constraints

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.

Example

Input:
2 4
47
744
7444
447
7774
77777777777777777777777777777777777777777777774

Output:
Good
Good
Bad
Good

Explanation

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.

This problem is quite simple , just follow what the problem says , step by step .

The following C++ code does our work :-

#include<iostream>

#include<string>

using namespace std;

int main()

{

    int k;

    cin>>k;

    int n;

    cin>>n;

    int i=0;

    string arr[k];

    while(i!=k)

    {

        cin>>arr[i];

        i++;

    }

    i=0;

    

    string s;

    i=0;

    while(i!=n)

    {

        int flag=0;

        cin>>s;

        if(s.length()>=47)

        {

            cout<<"Good \n";

            flag=1;

            //continue;

        }

        else

        {

            int j=0;

            while(j!=k)

            {

                size_t found = s.find(arr[j]); 

                if (found != string::npos)

                {

                    cout<<"Good \n";

                    flag=1;

                    break;

                }

                j++;

            }

        }

        if(flag==0)

        {

            cout<<"Bad \n";

        }

        i++;

    }

}

The code takes that k strings and stores them in an array , and then takes n strings and checks each of them if it is good or bad . For checking if the string is good or bad , we first check if the length of the string is >=47 . After , that we check if it has a substring in the array k , if it has we display Good , if it doesn't match with any of the k strings then we display Bad . 

 Please leave any comments if you have any doubts .