전화번호 변경

문제

OTC(올란디카 전기통신 회사, Olandican Telecommunication Company)에서 일한다고 가정합니다. OTC는 고객에게 전화번호를 배정할 때 현명한 결정을 내리지 못했습니다. 예를 들어 수요 증가를 제대로 예측하지 못해, 수도 올란드(Oland)의 지역 내 전화번호 자릿수를 6자리에서 7자리로, 다시 7자리에서 8자리로 늘려야 했습니다.

전화번호는 두 부분으로 이루어집니다. 하나는 지역 번호(area code)이고, 다른 하나는 그 지역 안에서 쓰이는 지역 내 번호(local number)입니다. 예를 들어 올란드 시의 지역 번호가 021이라면, 그 도시의 전화번호는 0211234567처럼 될 수 있습니다. 어떤 지역 번호도 다른 지역 번호의 접두사(prefix)가 되지 않습니다.

전화번호를 바꾸는 과정은 간단하지 않습니다. 수백만 건의 레코드를 담은 여러 데이터베이스를 모두 갱신해야 하기 때문입니다. 다행히 이 변경은 다음의 정해진 규칙만을 따릅니다. 아래에서 자리 위치 $i$ 는 지역 번호를 제외한 지역 내 번호에서 왼쪽부터 $1$ 번째로 세어 매깁니다.

어떤 지역 번호에 속한 모든 지역 내 번호에 대해, 지역 내 번호의 $i$ 번째 자리를 한 번 더 반복합니다. 예를 들어 지역 번호 021에서 두 번째 자리를 반복하면 0211234567은 02112234567이 됩니다.
어떤 지역 번호에 속한 모든 번호에 대해, 지역 내 번호의 $i$ 번째 자리와 $(i+1)$ 번째 자리를 서로 맞바꿉니다. 예를 들어 지역 번호 021에서 두 번째와 세 번째 자리를 맞바꾸면 0211234567은 0211324567이 됩니다.
어떤 지역의 지역 번호 자체를 다른 값으로 바꿉니다. 예를 들어 021을 0211로 바꾸면 0211234567은 02111234567이 됩니다.

세 번째 규칙으로 지역 번호를 바꾸어도 "어떤 지역 번호도 다른 지역 번호의 접두사가 되지 않는다"는 성질은 항상 유지됩니다. 지역 번호 정보와 모든 전화번호, 그리고 적용되는 규칙들이 주어질 때, 모든 변경을 마친 뒤의 전화번호를 구하는 프로그램을 작성하세요.

입력

입력의 첫 부분은 지역 번호 목록입니다. 첫 줄에 지역 번호의 개수 $A$ ( $1 \le A \le 1000$ )가 주어지고, 이어지는 $A$ 개의 줄에는 각각 다음 형식으로 정보가 주어집니다.

지역번호   지역이름

지역번호는 $1$ 자리 이상 $6$ 자리 이하의 숫자 문자열이고, 지역이름은 $1$ 자 이상 $20$ 자 이하의 영문자(대문자와 소문자 모두 가능) 문자열입니다. 같은 지역번호를 가진 두 줄이나 같은 지역이름을 가진 두 줄은 없습니다.

입력의 두 번째 부분은 적용되는 규칙들입니다. 이 부분의 첫 줄에 규칙의 개수 $R$ ( $0 \le R \le 10000$ )이 주어지고, 이어지는 $R$ 개의 줄에는 각각 다음 형식으로 정보가 주어집니다.

연도   규칙정보

연도는 규칙이 적용되는 해입니다. 규칙은 그 해의 첫날에 적용되며, 한 해에는 최대 하나의 규칙만 적용됩니다. 규칙정보는 적용되는 규칙의 종류에 따라 다음 중 하나의 형식을 가집니다.

1 지역이름 i
2 지역이름 i
3 지역이름 새지역번호

입력 데이터는 항상 일관적이라고 가정해도 됩니다. 즉 규칙에서 자리 위치 인덱스는 범위를 벗어나지 않으며, 어느 시점에서도 한 지역 번호가 다른 지역 번호의 접두사가 되는 일은 없습니다.

입력의 세 번째 부분은 여러 개의 질의이며, 각 줄은 다음 형식입니다.

연도1   연도2   전화번호

이 질의는 "연도1에 전화번호라는 전화번호가 있었을 때, 연도2에는 그 번호가 무엇이 되는가?"를 묻습니다(단, 연도1 $\le$ 연도2). 연도1 + 1부터 연도2까지 그 사이에 적용된 규칙들을 순서대로 그 번호에 적용해야 합니다. 질의는 세 개의 $0$ 으로 이루어진 줄로 끝납니다. 모든 연도는 $10^9$ 미만의 양의 정수입니다.

한 줄에 둘 이상의 데이터 항목(번호나 이름)이 있을 때, 항목들은 하나 이상의 공백으로 구분됩니다. 줄의 앞이나 뒤에 임의 개수의 공백이 있을 수도 있습니다. 각 데이터 항목은 최소 한 글자이며, 입력의 각 줄은 최대 $50$ 자입니다.

출력

각 질의마다 한 줄에, 변경이 끝난 전화번호를 출력합니다.