On vous donne deux entiers positifs $X$ et $Y$ de même longueur en base 10. Définissons $Z$ comme l'entier positif en base 10 satisfaisant les conditions suivantes :

• Les chiffres de $Z$ doivent être une permutation des chiffres de $X$. Les zéros non significatifs ne sont pas autorisés dans $Z$. Par exemple, si $X = 1103$, $Z$ peut être 1103 ou 3101, mais $Z$ ne peut pas être 2110, 301, ni 0131.
• $Y \le Z$.
• $Z$ est la valeur minimale satisfaisant les conditions ci-dessus.

Vous devez effectuer $Q$ requêtes. Chaque requête est l'une des suivantes :

• Étant donné $i$ et $x$, changer le $i$-ième chiffre de $Y$ par $x$.
• Étant donné $i$, afficher le $i$-ième chiffre de $Z$. S'il n'existe pas un tel $Z$, afficher $-1$.

Les chiffres d'un entier sont numérotés de gauche à droite en commençant par 1. Par exemple, le troisième chiffre de 1234 est 3.

Entrée

La première ligne contient deux entiers séparés par un espace, $X$ et $Y$. La deuxième ligne contient un seul entier $Q$, le nombre de requêtes. Chacune des $Q$ lignes suivantes contient des entiers séparés par des espaces décrivant les requêtes. Chaque ligne a l'une des formes suivantes, où le premier entier représente le type de la requête :

• "1 $i$ $x$" : Changer le $i$-ième chiffre de $Y$ par $x$.
• "2 $i$" : Afficher le $i$-ième chiffre de $Z$. S'il n'existe pas un tel $Z$, afficher $-1$.

Il est garanti qu'il y a au moins une requête de type 2. Soit $\text{len}(A)$ le nombre de chiffres d'un entier positif $A$.

• $1 \le X, Y < 10^{100\,000}$
• $1 \le Q \le 100\,000$
• $\text{len}(X) = \text{len}(Y)$
• Les premiers chiffres de $X$ et $Y$ ne sont pas 0.
• Pour une requête de type 1, $1 \le i \le \text{len}(Y)$, $0 \le x \le 9$, et si $i = 1$, alors $x \neq 0$.
• Pour une requête de type 2, $1 \le i \le \text{len}(Y)$.

Sortie

Pour chaque requête de type 2, afficher une seule ligne avec la réponse à la requête.

Exemples

Entrée 1

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

Sortie 1

3
4
0
3

Entrée 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

Sortie 2

8
0
3
4
6
8
-1

Entrée 3

2950 9052
4
2 1
2 2
2 3
2 4

Sortie 3

9
0
5
2