EIU Programming Practices and Exams

ABC software company consists of N programmers numbered from 1 to N who are doing a big project for foreign companies, each programmer must participate in a certain task. To manage employees effectively, You are assigned to write a program that inputs the employee ID and outputs the task id that person is in charge of.

Input

The first line contains two integers M and N - respectively the number of employees and the number of query (1 ≤ M, N ≤ 10 ^ 5).

In the next M lines, each line contains two integers a_i and b_i - the id of employee i-th and the id of the task which is assigned to employee i-th (1 ≤ ai, bi ≤ 10 ^ 9).

The next N lines, each line containing a single integer id - employee id (1 ≤ id ≤ 10 ^ 9).

Ensuring that no two employees have the same code and the employee id that managers are looking always existed.

Output

For each query, output the corresponding task in one line.

Example

Input:
5 2
1 2
2 2
3 1
4 3
5 1
1
3
Output:
2
1