LCC/Moose '18 Contest 3 S1 - Caroling

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Mariah’s favourite part of the holiday season is the abundance of catchy Christmas songs. Every day, Mariah’s mom gives her a ride to school and Mariah asks her to put on a song that is stuck in her head. However, Mariah does not know the names of many of the songs that she sings, so she sings her mom part of the song and hopes that her mom recognizes it.

Mariah does not know all the lyrics to the songs she sings, so she replaces some of the words with words consisting of the string ‘na’ repeated any number of times.

Mariah’s mom knows the titles and lyrics of every Christmas song and she has a good guess of which song Mariah is thinking of. To verify her guess, she’d like to know if the words that Mariah sang match some contiguous subsequence of the lyrics of the song. Can you help her verify her guess?

Input Specification

The first line of input contains an integer D (1 \le D \le 10), the number of days in the holiday season.

For each of the days, the input contains four lines in the following format:

An integer N (1 \le N \le 500), the number of words in the song Mariah's mom thinks Mariah is thinking of.

N space-separated, lowercase strings S_1, S_2, \ldots, S_N, the lyrics of the song.

An integer M (1 \le M \le 10), the number of words that Mariah sang.

M space-separated, lowercase strings T_1, T_2, \ldots, T_N, the words that Mariah sang.

It is guaranteed that 1 \le |S_i| \le 20, 1 \le |T_i| \le 20.

Output Specification

For each day, output Yes if what Mariah sang could be a part of the song lyrics, or No otherwise.

Sample Input

make my wish come true all i want for christmas is you
na na na for christmas is you
jingle bells jingle bells jingle all the way
nana bells nana all the way downtown

Sample Output



There are no comments at the moment.