409820: GYM103797 G Get Out!
Description
Wei is in a delicate situation. He has to get out of his unorganized art university! … for a few months… He got a great internship opportunity, but his university doesn't let him just go. To have some fun, the administration of the university made a deal: if he goes to class everyday and stays completely still for five consecutive hours for a whole semester, he will gain permission to do his internship and come back to finish his studies after the internship.
He did not like this solution, but he had no choice, so he kept this deal while trying to find a way out. It's already the last month of the semester, so Wei tried for the last time. And it worked! …sort off… The administration still wants to have some fun, so they are going to play a game with Wei.
Given a list of students registration numbers, they are going to give a series of queries with registration numbers of the administration. For each query, Wei should respond with the student number which gives the greatest digit modular sum with the administration's number. They defined digit modular sum as the sum digit by digit, taking $$$mod 10$$$. For example, $$$56 + 7 =_{dms} 53$$$, because $$$5 + 0 \equiv 5 \pmod{10}$$$ and $$$6 + 7 \equiv 3 \pmod{10}$$$.
Unfortunately, these are empty promises, because the administration added a rule for the game: Wei has to give a response in $$$1$$$ second! So he basically would have to guess anything. But you won't give up on him! Make him a program to win the administration game.
InputThe first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$) — the number of students registration numbers given.
Each of the next $$$N$$$ lines contains a $$$6$$$ digit registration number, possibly with leading zeros — the students numbers. All numbers will be different.
The next line contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) — the number of queries.
Each of the next $$$Q$$$ lines contains a $$$6$$$ digit registration number, possibly with leading zeros — the administration numbers.
Output$$$Q$$$ lines, one for each query — the answers to the game.
ExamplesInput2 000001 999999 1 100009Output
000001Input
3 123456 654321 162534 3 123456 654321 432165Output
654321 123456 162534