Dane są dwie dodatnie liczby całkowite $X$ oraz $Y$ o tej samej długości w zapisie dziesiętnym. Zdefiniujmy $Z$ jako dodatnią liczbę całkowitą w zapisie dziesiętnym spełniającą następujące warunki:

• Cyfry liczby $Z$ są permutacją cyfr liczby $X$. Liczba $Z$ nie może mieć wiodących zer. Na przykład, jeśli $X = 1103$, to $Z$ może wynosić $1103$ lub $3101$, ale $Z$ nie może wynosić $2110$, $301$ ani $0131$.
• $Y \le Z$.
• $Z$ jest najmniejszą wartością spełniającą powyższe warunki.

Musisz obsłużyć $Q$ zapytań. Każde zapytanie jest jednego z następujących typów:

• Dane $i$ oraz $x$, zmień $i$-tą cyfrę liczby $Y$ na $x$.
• Dane $i$, wypisz $i$-tą cyfrę liczby $Z$. Jeśli taka liczba $Z$ nie istnieje, wypisz $-1$.

Cyfry liczby całkowitej są numerowane od lewej do prawej, zaczynając od 1. Na przykład trzecią cyfrą liczby $1234$ jest $3$.

Wejście

W pierwszej linii znajdują się dwie oddzielone spacją liczby całkowite $X$ oraz $Y$. W drugiej linii znajduje się pojedyncza liczba całkowita $Q$, oznaczająca liczbę zapytań. Każda z kolejnych $Q$ linii zawiera liczby całkowite oddzielone spacjami, opisujące zapytania. Każda linia ma jedną z następujących postaci, gdzie pierwsza liczba całkowita reprezentuje typ zapytania:

• "1 $i$ $x$": Zmień $i$-tą cyfrę liczby $Y$ na $x$.
• "2 $i$": Wypisz $i$-tą cyfrę liczby $Z$. Jeśli taka liczba $Z$ nie istnieje, wypisz $-1$.

Gwarantuje się, że występuje co najmniej jedno zapytanie typu 2. Niech $\text{len}(A)$ oznacza liczbę cyfr w dodatniej liczbie całkowitej $A$.

• $1 \le X, Y < 10^{100\,000}$
• $1 \le Q \le 100\,000$
• $\text{len}(X) = \text{len}(Y)$
• Pierwsze cyfry $X$ oraz $Y$ nie są zerami.
• Dla zapytania typu 1: $1 \le i \le \text{len}(Y)$, $0 \le x \le 9$, oraz jeśli $i = 1$, to $x \neq 0$.
• Dla zapytania typu 2: $1 \le i \le \text{len}(Y)$.

Wyjście

Dla każdego zapytania typu 2 wypisz w pojedynczej linii odpowiedź na zapytanie.

Przykład

Wejście 1

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

Wyjście 1

3
4
0
3

Wejście 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

Wyjście 2

8
0
3
4
6
8
-1

Wejście 3

2950 9052
4
2 1
2 2
2 3
2 4

Wyjście 3

9
0
5
2