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