Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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.

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.

  • 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