You are working for OTC, the Olandican Telecommunication Company. Unfortunately, OTC does not decide wisely in assigning telephone numbers to the clients. For example, it did not make a good estimate on demand increase. As a result, it had to increase the number of digits in the local telephone numbers of Oland (the capital) from six to seven, and then again from seven to eight digits.
As usual, a telephone number consists of two parts: an area code, and the local number within that area code. For example, if 021 is the area code of the Oland city, a telephone number in that city may be 0211234567. Note that no area code is the prefix of another area code. The process of changing telephone numbers is not easy though. It requires updates to several databases of millions of records. Fortunately, these changes follow a limited number of rules as follows:
1. For all local numbers in a given area code, repeat the ith digit. For example, for the area code 021, repeating the second digit causes the number 0211234567 change to 02112234567.
2. For all numbers in a given area code, swap the ith and the (i + 1)th digit. For example, for the area code 021, swapping the second and the third digits causes the number 0211234567 change to 0211324567.
3. Change a given area code. For example, changing 021 to 0211 causes the number 0211234567 change to 02111234567.
Note that changing area codes in the third rule preserves the property that no area code is the prefix of another. You are to write a program that given the area code information, and the set of all telephone numbers, plus a given set of rules, determine the resulting telephone numbers after the changes.
The first part of the input describes the set of area codes. It starts with a line containing a single integer A (1 <= A <= 1000), which is the number of area codes in Olandica, followed by A lines of the following form:
The output contains one line corresponding to each query containing the changed number.
4 021 Oland 0511 Moland 0311 Boland 03121 Kamand 7 2002 1 Moland 2 2001 3 Moland 0515 2003 2 Boland 3 2005 1 Kamand 1 2000 1 Kamand 1 1999 1 Kamand 1 1998 3 Oland 012345 2000 2005 0311243426 2000 2005 05113837462 2000 2005 03121437478 0 0 0
0311244326 051538837462 031214437478