Training Site

# Passport Control

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 3.0 seconds

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.

• 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.

• ### Sample Input 1

5 6
NZ YG12329405
AU KO97527898
AU OG45153808
US LP74256824
NZ GN24664280
ALL
ALL
ALL
NZ
ALL
ALL


### Sample Output 1

YG12329405
KO97527898
OG45153808
GN24664280
LP74256824
NA

• ### Sample Input 2

10 8
IT DX14551064
NZ PB48245801
NZ YG90195850
NZ NN49587015
NZ AC14233172
NZ MD89734029
DIP IX58407934
FR OO15332345
NZ ST30533158
NZ GP52996563
ALL
NZ
ALL
ALL
DIP
NZ
ALL
DIP


### Sample Output 2

DX14551064
PB48245801
YG90195850
NN49587015
IX58407934
AC14233172
MD89734029
NA