Sophie has just gone to a new school and has already made ~N~ friends! Each one of her friends has given her their name and their phone number. Because she has really bad memory, she decided to write a program to store each friend's name and their corresponding phone number! However, her program does not work properly and just prints out random things, so she has asked you to do it for her instead. Please write a program that will accept ~Q~ queries, of two different types:

name u: Given a phone number u, containing exactly 10 digits, print out the name of the friend with that phone number.

phone u: Given the name of the friend, print out the friend's phone number.

Input Specification

The first line will contain ~N~ ~(1 \leq N \leq 10^5)~ and ~Q~ ~(1 \leq Q \leq 10^5)~, the number of friends that Sophie has and the queries she has for you, respectively.

The next ~N~ lines will contain string ~s_i~, the friend's name, followed by their phone number. It is guaranteed that the length of the friend's name will not exceed 10 characters and the phone number is exactly 10 digits long.

The next ~Q~ lines will contain two strings. The first one will either be name or phone. If it is name, then the second string will contain the number of the friend, or else it will contain the name of the friend if the first string is phone.

Output Specification

~Q~ lines, the answer to each of Sophie's queries.

Sample Input 1

4 3
Ray 1234567890
Martin 4836751947
Alessia 5214394726
Kayla 0224583369
phone Alessia
name 4836751947
phone Ray

Sample Output 1

5214394726
Martin
1234567890

Sample Explanation 1

Since the query is phone, we get Alessia's phone number which is ~5214394726~. The second query is name, and the phone number matches to Martin. The final query is also phone so we get Ray's phone number which is ~1234567890~.