Lychee Order

View as PDF

Submit solution

Points: 5
Time limit: 1.5s
Memory limit: 64M

Author:
Problem type

Flora decides to eat N lychees, when she stumbles upon a dilemma! Some of her lychees aren't ripe, making them more sour than usual. However, she's impatient and refuses to wait any longer before eating her lychees. She decides to eat the lychees in the order from least ripe to the most ripe. She will rate the lychees on how ripe she believes they are using numerics. The higher the number, the more ripe. She wants to know the order which she will eat her lychee in, and will ask q questions (1 \le q \le N), where each question contains i, and wants the name of the i-th lychee which she will eat. No lychee will have the same ripeness.

She notices that some lychee do not look appetizing, and can even give them negative ripeness value because she's weird. As her friend, she begs you to help her so she can eat in peace!

Constraints

1 \le N \le 10^6

-10^9 \le b_i \le 10^9

Input Specification

The first line of the input will contain N and q, representing the number of lychees given and the number of queries.

The next N lines will each contain a_i and b_i, representing the name and ripeness of the lychee respectively. The name of the lychee is guaranteed to be under 30 letters and can consist of uppercase and lowercase letters.

The next q lines will each contain an integer i, representing the i-th lychee.

Output Specification

For each query, output the name of the i-th lychee that Flora will eat.

Sample Input

5 3
lychee1 500
lychee2 0
lychee3 3
lychee4 -4
lychee 199
1
2
5

Sample Output

lychee1
lychee
lychee4

Comments

There are no comments at the moment.