HMRO - Help the Military Recruitment Office!

no tags 

At the end of year 2004, the regional agencies of the Polish Military Recruitment Office (known as WKU in Polish) is sending a call to all boys born in 1984. Every recruit has his personal 11-digit identification number (PESEL, format: YYMMDDXXXXX, where YYMMDD is the date of birth, and XXXXX is a zero-padded integer smaller than 100000). Every agency of the Military Recruitment Office has its own code (MRO, format: a place code consisting of 3 upper case letters and a one-digit number). But this year the army underwent some reforms and not all boys at conscription age are going to be recruited. The list of closed down MRO points is as follows: the code of the closed down MRO is followed by the code of some other MRO, to which all the recruits are now going to be assigned. The list of recruits contains their PESEL codes. Your task is to prepare the complete list of recruits and determine the codes of their new MRO-s.

Input

s [the number of tests <= 10]
p [the number of boys at conscription age <= 100000]
PESEL and MRO code
z [the number of closed down MRO points <= 100000]
old_code new_code [old_code - the code of closed down MRO,
new_code - its new MRO code]
p [the number of recruits <= 100000]
PESEL [PESEL code of recruit]
[empty line]
[next tests]

Output

one PESEL and MRO code per line in the order of input
[empty line between tests]
[other results]

Example

Input:
1
4
84101011111 GDA1
84010122222 GDA2
84010233333 GDA2
84020255555 GDY1
1
GDA2 GDA1
3
84101011111
84010122222
84020255555

Output:
84101011111 GDA1
84010122222 GDA1
84020255555 GDY1

Warning: large Input/Output data, be careful with certain languages

hide comments
Saurabh Manchanda: 2010-11-17 19:02:18

Will the MRO codes be always entered in lexicographic order??

Iqram Mahmud: 2010-04-12 14:58:18

I am wondering what to do if I have case like this like 18-0 said -

2
84101011111 GDA1
84101011111 GDA2

I used an assert, and I think there are things like that. I don't understand what's meant by "ignoring" them. :(

Luke Pebody: 2010-02-24 18:39:07

What do you mean ignore this case? Do you mean that all old different MRO codes will lead to the same final MRO code?

Can the new_code of one MRO move be the old_code of another MRO move? If so, will they always occur in this order (i.e. close 1 and send to 2 cannot happen before close 3 and send to 1)

Tasnim Khan: 2009-12-06 17:43:15

The input does contain for same person different MRO codes , but you can ignore this case

Last edit: 2009-12-06 17:50:27

Added by:mima
Date:2004-06-01
Time limit:30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:-