Даны два положительных целых числа $X$ и $Y$ одинаковой длины в десятичной системе счисления. Определим $Z$ как положительное целое число в десятичной системе счисления, удовлетворяющее следующим условиям:

• Цифры числа $Z$ являются перестановкой цифр числа $X$. Ведущие нули в $Z$ не допускаются. Например, если $X = 1103$, то $Z$ может быть $1103$ или $3101$, но $Z$ не может быть $2110$, $301$ или $0131$.
• $Y \le Z$.
• $Z$ — минимальное значение, удовлетворяющее вышеуказанным условиям.

Вам необходимо выполнить $Q$ запросов. Каждый запрос относится к одному из следующих типов:

• Даны $i$ и $x$, изменить $i$-ю цифру числа $Y$ на $x$.
• Дан $i$, вывести $i$-ю цифру числа $Z$. Если такого $Z$ не существует, вывести $-1$.

Цифры целого числа нумеруются слева направо, начиная с 1. Например, третья цифра числа $1234$ — это $3$.

Входные данные

Первая строка содержит два целых числа $X$ и $Y$, разделенных пробелом. Вторая строка содержит единственное целое число $Q$ — количество запросов. Каждая из следующих $Q$ строк содержит целые числа, разделенные пробелом, описывающие запросы. Каждая строка имеет один из следующих форматов, где первое целое число представляет тип запроса:

• «$1\ i\ x$»: изменить $i$-ю цифру числа $Y$ на $x$.
• «$2\ i$»: вывести $i$-ю цифру числа $Z$. Если такого $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

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

8
0
3
4
6
8
-1

Примеры 3

2950 9052
4
2 1
2 2
2 3
2 4

9
0
5
2