Bạn được cho hai số nguyên dương $X$ và $Y$ có cùng độ dài trong hệ thập phân. Hãy xác định $Z$ là số nguyên dương trong hệ thập phân thỏa mãn các điều kiện sau:

• Các chữ số của $Z$ là một hoán vị các chữ số của $X$. $Z$ không được có chữ số 0 ở đầu. Ví dụ, nếu $X = 1103$, $Z$ có thể là $1103$ hoặc $3101$, nhưng $Z$ không thể là $2110$, $301$ hoặc $0131$.
• $Y \le Z$.
• $Z$ là giá trị nhỏ nhất thỏa mãn các điều kiện trên.

Bạn cần thực hiện $Q$ truy vấn. Mỗi truy vấn thuộc một trong các loại sau:

• Cho $i$ và $x$, thay đổi chữ số thứ $i$ của $Y$ thành $x$.
• Cho $i$, in ra chữ số thứ $i$ của $Z$. Nếu không tồn tại $Z$ như vậy, in ra $-1$.

Các chữ số của một số nguyên được đánh số từ trái sang phải bắt đầu từ 1. Ví dụ, chữ số thứ ba của $1234$ là $3$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên cách nhau bởi dấu cách $X$ và $Y$. Dòng thứ hai chứa một số nguyên duy nhất $Q$, số lượng truy vấn. Mỗi dòng trong $Q$ dòng tiếp theo chứa các số nguyên cách nhau bởi dấu cách mô tả các truy vấn. Mỗi dòng có một trong các dạng sau, trong đó số nguyên đầu tiên đại diện cho loại truy vấn:

• "1 $i$ $x$": Thay đổi chữ số thứ $i$ của $Y$ thành $x$.
• "2 $i$": In ra chữ số thứ $i$ của $Z$. Nếu không tồn tại $Z$ như vậy, in ra $-1$.

Đảm bảo rằng có ít nhất một truy vấn loại 2. Gọi $len(A)$ là số lượng chữ số của số nguyên dương $A$.

• $1 \le X, Y < 10^{100\,000}$
• $1 \le Q \le 100\,000$
• $len(X) = len(Y)$
• Chữ số đầu tiên của $X$ và $Y$ không phải là 0.
• Đối với truy vấn loại 1, $1 \le i \le len(Y)$, $0 \le x \le 9$, và nếu $i = 1$ thì $x \neq 0$.
• Đối với truy vấn loại 2, $1 \le i \le len(Y)$.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra một dòng duy nhất chứa câu trả lời cho truy vấn đó.

Ví dụ

Ví dụ 1

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

3
4
0
3

Ví dụ 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

8
0
3
4
6
8
-1

Ví dụ 3

2950 9052
4
2 1
2 2
2 3
2 4

9
0
5
2