|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||73||1||1||100.000%|
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:
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:
area - code area - name
where area - code is a string of at least one, and at most 5 digits, and area - name is a string of at least one, and at most 20 letters (both uppercase and lowercase). There are no two lines with the same area-code or area-name.
The second part of the input describes the rules applied by OTC. The first line of this part contains a single integer R (0 ≤ R ≤ 10000) , the number of rules applied, followed by R lines of the following form:
year rule - info
where year is the year in which the rule is applied. You may assume the rule is applied on the first day of the year, and at most one rule is applied each year. The rule - info part depends on the specific rule applied. The following list shows the rule-info formats corresponding to the rules described in the problem statement:
You can assume that input data is consistent; i.e. in the rules section, indices are not out of range, and an area code will never be prefix of another, at any fixed time. The third part of the input consists of several lines of the following form:
year1 year2 number
The query says that in year1 , there was a telephone number number , and asks for that number in year2 ( year1 ≤ year2 ). You must change the number according to the rules applied in the years between year1 + 1 and year2 in that order. The queries end with a line containing three zeros. The years are positive integers less than 109 .
In every line in the input containing more than one data item (number or name), the data items are separated by one or more spaces. There may be arbitrary number of leading or trailing spaces too. Each data item is at least one character. Each line of the input is at most 50 characters.
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