Passport Control

There is a single queue of people at Auckland Airport waiting to immigrate, each with different types of passports. When a desk is free, the first eligible person in the queue gets their turn. There are 3 types of desks labelled NZ, DIP and ALL. The NZ desk is for New Zealand citizens only, DIP is for diplomatic passports only, and ALL accepts all passports.

When a desk becomes available, your job is to find the next person in line for the desk.

Input

On the first line are two integers, $N$, the number of people in the queue, and $K$, the number of times when a desk becomes free. On the next $N$ lines, each representing a person in the queue, are two space separated strings - the type of passport (NZ, DIP, ...) up to 3 characters, and the passport number (a string of letters and numbers up to 10 characters long). It is guaranteed that all passport numbers are unique.

On the next $K$ lines is a label representing the type of desk which has opened up - NZ, DIP or ALL.

Output

For each of the $K$ times that a desk is available, print the passport number of the next person admitted. If there is no eligible person, print NA in capitals.

Subtasks

• For 25% of points, $1 \leq N, K \leq 100$.
• For another 25% of points, $1 \leq N, K \leq 1,000$.
• For another 10% of points, $1 \leq N, K \leq 50,000$, and there are only NZ and DIP desks.
• For another 10% of points, $1 \leq N, K \leq 50,000$, and there are no diplomatic passports or people.
• For the remaining 30% of points, $1 \leq N, K \leq 50,000$, with no other restrictions.

Explanation

For the first sample test case, the first three desks accept all passports, so the first 3 people in the queue get their turn first. The 4th desk only accepts NZ passports, so the last person in line (the only remaining NZ passport) is the 4th person admitted. After the last person is processed, there is nobody left (the last desk made available is not used), so NA is printed.