Changing Phone Numbers

You work for OTC, the Olandican Telecommunication Company. Unfortunately, OTC did not make wise decisions when assigning telephone numbers to its clients. For example, it underestimated the growth in demand, so 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.

A telephone number consists of two parts: an area code and the local number used within that area. For example, if the area code of Oland city is 021, then a telephone number in that city may look like 0211234567. No area code is a prefix of another area code.

Changing telephone numbers is not easy, because it requires updating several databases containing millions of records. Fortunately, the changes follow only a limited set of rules. In the rules below, the position $i$ is counted starting from $1$ within the local number, i.e. after removing the area code.

1. For every local number under a given area code, repeat the $i$-th digit of the local number once more. For example, under area code 021, repeating the second digit changes 0211234567 into 02112234567.
2. For every number under a given area code, swap the $i$-th and $(i+1)$-th digit of the local number. For example, under area code 021, swapping the second and third digits changes 0211234567 into 0211324567.
3. Change the area code of a given area to a new value. For example, changing 021 into 0211 changes 0211234567 into 02111234567.

Changing area codes with the third rule always preserves the property that no area code is a prefix of another. Given the area-code information, all telephone numbers, and the set of rules that are applied, write a program that determines the resulting telephone numbers after all changes.

The first part of the input describes the area codes. The first line contains a single integer $A$ ($1 \le A \le 1000$), the number of area codes, followed by $A$ lines, each of the form:

area-code   area-name

area-code is a string of at least $1$ and at most $6$ digits, and area-name is a string of at least $1$ and at most $20$ letters (uppercase and lowercase allowed). No two lines share the same area code, and no two lines share the same area name.

The second part describes the rules applied. Its first line contains a single integer $R$ ($0 \le R \le 10000$), the number of rules, followed by $R$ lines, each of the form:

year   rule-info

year is the year in which the rule is applied. Each rule takes effect on the first day of that year, and at most one rule is applied in any given year. Depending on the rule, rule-info has one of the following forms:

• 1 area-name i
• 2 area-name i
• 3 area-name new-area-code

You may assume the input is always consistent: rule position indices are never out of range, and at no point in time is one area code a prefix of another.

The third part consists of several queries, each of the form:

year1   year2   number

The query asks: given that in year1 there was a telephone number number, what does that number become in year2 (with year1 $\le$ year2)? You must apply, in order, the rules that were applied in the years from year1 + 1 through year2. The queries end with a line containing three zeros. Every year is a positive integer less than $10^9$.

When a line contains more than one data item (a number or a name), the items are separated by one or more spaces, and there may be an arbitrary number of leading or trailing spaces. Each data item has at least one character, and each input line has at most $50$ characters.

For each query, print on its own line the resulting telephone number after the changes.