Background

Xiao D is an IO contestant who is about to take ION. However, the large number of strange problems in the written test question bank gives him a headache. Please help him.

Problem Description

The written test question bank can be abstracted as $n$ problems. Each problem consists of a statement and an answer, both of which are strings. It is guaranteed that all problem statements are distinct.

To check how well Xiao D has memorized the written test materials, the coach held a mock exam. The exam contains $q$ problems. Each problem has $4$ options, and Xiao D needs to choose the option that matches the answer among the $4$ options.

Now you need to help Xiao D finish this exam.

Input Format

The first line contains two positive integers $n, q$.

The next $n$ lines each contain $2$ strings separated by spaces, representing the problem statement and the answer for that problem.

The next $q$ lines each contain $5$ strings separated by spaces. The first string is the problem statement in the mock exam. The remaining $4$ strings, in order, are options A through D for this problem. It is guaranteed that all options are distinct.

Output Format

For each problem in the mock exam, output a single character indicating which option corresponds to the correct answer. It is guaranteed that every problem has a solution.

3 4
decoak yes
duliuchutiren nonono
csps noiptg
decoak yes no qwq qaq
csps noiptg noippj noi cspj
decoak qwq qaq yesyes yes
duliuchutiren yes no nono nonono

A
A
D
D

Hint

Constraints

Let $s$ be the maximum string length in the input.

For $30\%$ of the testdata, $n, q, s \le 10$.
For another $20\%$ of the testdata, $s = 1$.
For $100\%$ of the testdata, $n, q, s \le 100$, and all strings consist of lowercase Latin letters.

Translated by ChatGPT 5