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