AIOC Banner

Problem: Dictionary

Want to try solving this problem? You can submit your code online if you log in or register.


The problems in this set are designed to be more accessible to beginning coders. As a learning aid, walkthroughs discussing how to solve the problems in this set are available by clicking on this link. On completion of this problem set, students should have experience at using arrays to store, search through, and manipulate large data sets.

Dictionary

Input File: dictin.txt
Output File: dictout.txt
Time Limit: 1 second

Integerland and Wholenumberland are alike in many ways: similar culture, similar traditions - they even share the same national dress (the parenthetic pyjamas). Yet despite this, the two nations have never gotten along well. It is widely believed that this is because of their greatest differences - their language. A sentence that sounds perfectly intelligible on one side of the border is complete gibberish on the other side.

For example, if an Integerlander wanted to find out the time, she would ask, "140 2 87 2 3?". On the other hand, a Wholenumberlander would ask "19 71 555 71 556?". As you can see, these languages are very distinctive. It would be impossible to mistake one for the other.

This year's regional trade talks are to be held in Australia. You have been appointed the official translator for the proceedings. Using your trusty Integerlandese-Wholenumberlandese dictionary and your rusty laptop, you must be able to fluently translate from one language to another.

Input

The first line will consist of two integers d and w, separated by a space. You are guaranteed that 0 <= d, w <= 1,000.

The following d lines will each describe an entry in your bilingual dictionary. Each of these lines contains two integers separated by a space: a word in Integerlandese, and its Wholenumberlandese counterpart. All integers will be between -2,000,000,000 and 2,000,000,000 inclusive. You are guaranteed that no Integerlandese word will appear more than once in the dictionary.

The following w lines will each contain a single word in Integerlandese for you to translate.

Output

For each Integerland word you are asked to translate, you must print out a single line containing the corresponding Wholenumberland word. If there is no translation in your dictionary, you should print "C?" for that line.

Sample Input

5 6
2 71
3 556
140 19
87 555
71 3
140
2
87
2
3
4

Sample Output

19
71
555
71
556
C?

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

 


Privacy statement
© Australian Mathematics Trust 2001-2024

Contact: training@orac.amt.edu.au
Page generated: 29 March 2024,  4:24pm AEDT