두 개의 양의 정수 $X$와 $Y$가 10진법에서 같은 길이로 주어집니다. 다음 조건을 만족하는 10진법 양의 정수 $Z$를 정의합시다.

• $Z$의 자릿수는 $X$의 자릿수를 재배열한 것이어야 합니다. $Z$에서 선행 0은 허용되지 않습니다. 예를 들어, $X = 1103$이면 $Z$는 $1103$ 또는 $3101$이 될 수 있지만, $2110$, $301$, $0131$은 될 수 없습니다.
• $Y \le Z$.
• $Z$는 위 조건을 만족하는 최솟값입니다.

$Q$개의 쿼리를 수행해야 합니다. 각 쿼리는 다음 중 하나입니다.

• $i$와 $x$가 주어지면, $Y$의 $i$번째 자릿수를 $x$로 변경합니다.
• $i$가 주어지면, $Z$의 $i$번째 자릿수를 출력합니다. 그러한 $Z$가 존재하지 않으면 $-1$을 출력합니다.

정수의 자릿수는 왼쪽에서 오른쪽으로 1부터 번호를 매깁니다. 예를 들어, $1234$의 세 번째 자릿수는 $3$입니다.

입력

첫 번째 줄에는 공백으로 구분된 두 정수 $X$와 $Y$가 주어집니다. 두 번째 줄에는 쿼리의 개수인 정수 $Q$가 주어집니다. 이어지는 $Q$개의 각 줄에는 쿼리를 설명하는 공백으로 구분된 정수들이 주어집니다. 각 줄은 다음 형식 중 하나이며, 첫 번째 정수는 쿼리의 유형을 나타냅니다.

• "1 $i$ $x$": $Y$의 $i$번째 자릿수를 $x$로 변경합니다.
• "2 $i$": $Z$의 $i$번째 자릿수를 출력합니다. 그러한 $Z$가 존재하지 않으면 $-1$을 출력합니다.

유형 2 쿼리가 적어도 하나 이상 존재함이 보장됩니다. $len(A)$를 양의 정수 $A$의 자릿수라고 합시다.

• $1 \le X, Y < 10^{100\,000}$
• $1 \le Q \le 100\,000$
• $len(X) = len(Y)$
• $X$와 $Y$의 첫 번째 자릿수는 0이 아닙니다.
• 유형 1 쿼리의 경우, $1 \le i \le len(Y)$, $0 \le x \le 9$이며, $i = 1$이면 $x \neq 0$입니다.
• 유형 2 쿼리의 경우, $1 \le i \le len(Y)$입니다.

출력

유형 2의 각 쿼리에 대해, 쿼리에 대한 답을 한 줄에 하나씩 출력합니다.

예제

입력 1

3304 1615
6
2 3
2 4
1 1 3
2 2
1 2 4
2 1

출력 1

3
4
0
3

입력 2

838046 780357
10
2 1
2 2
1 2 4
2 3
2 4
1 4 5
2 5
2 6
1 1 9
2 2

출력 2

8
0
3
4
6
8
-1

입력 3

2950 9052
4
2 1
2 2
2 3
2 4

출력 3

9
0
5
2