숫자 만들기

두 양의 정수 $X$와 $Y$가 주어진다. 두 수의 10진수 자릿수는 같다. $Z$는 다음 조건을 모두 만족하는 10진수 양의 정수이다.

• $Z$의 자릿수는 $X$의 자릿수를 재배열한 것이다. $Z$의 맨 앞자리는 0일 수 없다. 예를 들어 $X=1103$이면 $Z$는 $1103$ 또는 $3101$일 수 있지만, $2110$, $301$, $0131$은 $Z$가 될 수 없다.
• $Y\le Z$이다.
• $Z$는 위 조건을 만족하는 값 중 최솟값이다.

다음 $Q$개의 질의를 처리한다. 질의는 다음 두 종류 중 하나이다.

• $Y$의 $i$번째 자릿수를 $x$로 바꾼다.
• $Z$의 $i$번째 자릿수를 출력한다. 해당하는 $Z$가 없으면 $-1$을 출력한다.

자릿수는 왼쪽부터 센다.

첫째 줄에 두 정수 $X$와 $Y$가 공백으로 구분되어 주어진다.

둘째 줄에 $Q$가 주어진다.

다음 $Q$개의 줄에 질의가 주어진다. 각 질의의 첫 번째 정수는 질의의 종류이며, 형식은 다음과 같다.

• 1 $i$ $x$: $Y$의 $i$번째 자릿수를 $x$로 바꾼다.
• 2 $i$: $Z$의 $i$번째 자릿수를 출력한다. 해당하는 $Z$가 없으면 $-1$을 출력한다.

종류가 2인 질의가 적어도 하나 주어진다.

종류가 2인 질의마다 답을 한 줄에 하나씩 출력한다.

$1\le X, Y<10^{100000}$ $1\le Q\le 100000$ $X$와 $Y$의 자릿수는 같다. $X$와 $Y$의 맨 앞자리는 0이 아니다. 종류가 1인 질의에서 $1\le i\le$ ($Y$의 자릿수), $0\le x\le 9$이다. $i=1$이면 $x\ne 0$이다. 종류가 2인 질의에서 $1\le i\le$ ($Y$의 자릿수)이다.