G. Truecaller
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Valentine's Day is the perfect occasion to confess your love, and what's better than anonymous phone calls ?

You have in your phone a contact list of $$$n$$$ phone numbers, saved as name and its respective phone number.

You receive $$$q$$$ phone calls but here's the catch: You can't see the whole phone number, but rather only $$$k$$$ digits, $$$(1 \leq k\leq 8)$$$ and not necessarily in the same order. Also, among the next $$$q_{i}$$$ digits, $$$(0 \leq q_{i} \leq 9)$$$, there could be duplicates.

Tell for each query $$$q$$$ whether no phone number in your repertory matches it, many possible numbers match it, or the name of the UNIQUE person whose number matches those criteria.

Input

In the first line, you are given an integer $$$n$$$ , $$$(1\leq n \leq 10^{4})$$$.

In the next $$$n$$$ lines, you are given a string $$$name$$$ of lowercase and uppercase english letters $$$(1\leq len(name) \leq 10)$$$ , and an-8-digits string $$$phone$$$. It's guaranteed that all the names are different and all the phones are different.

In the next line, you are given $$$q$$$ queries, $$$(1\leq q \leq 10^{6})$$$

For each $$$q$$$ lines, you get an integer $$$k$$$ , $$$(1\leq k \leq 8)$$$, the number of known digits, and a string $$$partial phone$$$ of size $$$k$$$.

Output

After each query, output "NONE" if no phone number in your repertory matches it, "MANY" if many possible persons match it, or the $$$name$$$ of the UNIQUE person that matches it.

Example
Input
3
Mahdi 12345678
Elyes 11223344
Mohamed 00881212
5
1 5
2 11
3 111
7 7654321
1 9
Output
Mahdi
MANY
NONE
Mahdi
NONE