Se te proporcionan dos enteros positivos $X$ y $Y$ de la misma longitud en base 10. Definamos $Z$ como el entero positivo en base 10 que satisface las siguientes condiciones:

• Los dígitos de $Z$ deben ser una reordenación de los dígitos de $X$. No se permiten ceros a la izquierda en $Z$. Por ejemplo, si $X = 1103$, $Z$ puede ser 1103 o 3101, pero $Z$ no puede ser 2110, 301, ni 0131.
• $Y \le Z$.
• $Z$ es el valor mínimo que satisface las condiciones anteriores.

Debes realizar $Q$ consultas. Cada consulta es una de las siguientes:

• Dados $i$ y $x$, cambia el $i$-ésimo dígito de $Y$ por $x$.
• Dado $i$, imprime el $i$-ésimo dígito de $Z$. Si no existe tal $Z$, imprime $-1$.

Los dígitos de un entero están numerados de izquierda a derecha comenzando desde 1. Por ejemplo, el tercer dígito de 1234 es 3.

Entrada

La primera línea contiene dos enteros separados por espacios, $X$ y $Y$. La segunda línea contiene un único entero $Q$, el número de consultas. Cada una de las siguientes $Q$ líneas contiene enteros separados por espacios que describen las consultas. Cada línea tiene una de las siguientes formas, donde el primer entero representa el tipo de consulta:

• "1 $i$ $x$": Cambia el $i$-ésimo dígito de $Y$ por $x$.
• "2 $i$": Imprime el $i$-ésimo dígito de $Z$. Si no existe tal $Z$, imprime $-1$.

Se garantiza que hay al menos una consulta de tipo 2. Sea $len(A)$ el número de dígitos en un entero positivo $A$.

• $1 \le X, Y < 10^{100\,000}$
• $1 \le Q \le 100\,000$
• $len(X) = len(Y)$
• Los primeros dígitos de $X$ y $Y$ no son 0.
• Para una consulta de tipo 1, $1 \le i \le len(Y)$, $0 \le x \le 9$, y si $i = 1$, entonces $x \neq 0$.
• Para una consulta de tipo 2, $1 \le i \le len(Y)$.

Salida

Para cada consulta de tipo 2, imprime una sola línea con la respuesta a la consulta.

Ejemplos

Entrada 1

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

Salida 1

3
4
0
3

Entrada 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

Salida 2

8
0
3
4
6
8
-1

Entrada 3

2950 9052
4
2 1
2 2
2 3
2 4

Salida 3

9
0
5
2