Guess the Song from the Intro

Time limit1sMemory limit1024 MB

Summary

Given stored songs with their first seven notes, for each query of three notes, print the unique song title starting with those notes, ? if several match, or ! if none.

Level: Easy2 of 10
Topics: String, Implementation
Solved: No attempts yet

Problem

Yunsu and Jeonghwan are going to play a game called Guess the Song from the Intro. In this game, a player hears the intro of a song and tries to name its title first. The player who names it earns a point, and the player with more points at the end wins.

Yunsu has perfect pitch and can name any song after hearing only its first four notes. So Jeonghwan wants to build a program that identifies songs from only their first three notes, so that he can beat Yunsu. He first built data of the song titles and note names he knows, and then started implementing the program. For example, the following is part of the score of TwinkleStar.

Ignoring rhythm, the score above is written as the note names CCGGAAG.

To beat Yunsu, the program must be able to print the title TwinkleStar from the first three notes CCG alone. Unlike Yunsu, who knows every song in the world, Jeonghwan knows the notes of only $N$ songs. So he will store the information of those $N$ songs in the program. If several stored songs begin with the input first three notes so that the song cannot be identified, print ?. If no stored song matches the input first three notes, print !.

Help Jeonghwan finish a program that identifies, from only the first three notes, the songs whose notes he knows. This program is case-sensitive.

Input

The first line contains two integers $N$ and $M$ , separated by a space: the number of songs whose notes Jeonghwan knows, and the number of songs he will try to name.

From the second line, each of the next $N$ lines contains the title length $T$ , the title $S$ made of English letters, and the seven note names $a_1, a_2, a_3, a_4, a_5, a_6, a_7$ that first appear in that song, separated by spaces.

Each of the next $M$ lines contains the three note names $b_1, b_2, b_3$ of a song Jeonghwan will try to name, separated by spaces.

Each note name is one of C, D, E, F, G, A, B. No title is given more than once.

Output

For each song Jeonghwan tries to name, print one line: the title if exactly one stored song has the same first three notes, ? if two or more do, or ! if none do.

Constraints

$1 \le N \le 1\,000$
$1 \le M \le 1\,000$
$1 \le T \le 30$
All numbers in the input are integers.

Examples1

Example 1

Input

4 4
11 TwinkleStar C C G G A A G
8 Marigold E D E F E E D
23 DoYouWannaBuildASnowMan C C C G C E D
12 Cprogramming C C C C C C C
E D E
C G G
C C C
C C G

Expected output

Marigold
!
?
TwinkleStar