给定两个长度相同的十进制正整数 $X$ 和 $Y$。定义 $Z$ 为满足以下条件的最小十进制正整数：

• $Z$ 的各位数字是 $X$ 的各位数字的一个重排。$Z$ 不允许有前导零。例如，若 $X = 1103$，$Z$ 可以是 $1103$ 或 $3101$，但不能是 $2110$、$301$ 或 $0131$。
• $Y \le Z$。
• $Z$ 是满足上述条件的最小值。

你需要执行 $Q$ 次查询。每次查询为以下两种之一：

• 给定 $i$ 和 $x$，将 $Y$ 的第 $i$ 位数字修改为 $x$。
• 给定 $i$，输出 $Z$ 的第 $i$ 位数字。如果不存在这样的 $Z$，输出 $-1$。

整数的位数从左到右从 $1$ 开始编号。例如，$1234$ 的第三位数字是 $3$。

输入格式

第一行包含两个空格分隔的整数 $X$ 和 $Y$。 第二行包含一个整数 $Q$，表示查询次数。 接下来的 $Q$ 行，每行包含描述查询的空格分隔整数。每行格式如下，其中第一个整数表示查询类型：

• “$1\ i\ x$”：将 $Y$ 的第 $i$ 位数字修改为 $x$。
• “$2\ i$”：输出 $Z$ 的第 $i$ 位数字。如果不存在这样的 $Z$，输出 $-1$。

保证至少有一次类型为 $2$ 的查询。 令 $\text{len}(A)$ 为正整数 $A$ 的位数。

• $1 \le X, Y < 10^{100\,000}$
• $1 \le Q \le 100\,000$
• $\text{len}(X) = \text{len}(Y)$
• $X$ 和 $Y$ 的首位数字不为 $0$。
• 对于类型 $1$ 的查询，$1 \le i \le \text{len}(Y)$，$0 \le x \le 9$，且若 $i = 1$，则 $x \neq 0$。
• 对于类型 $2$ 的查询，$1 \le i \le \text{len}(Y)$。

输出格式

对于每次类型为 $2$ 的查询，输出一行，包含查询的答案。

样例

样例输入 1

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

样例输出 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

样例输出 2

8
0
3
4
6
8
-1

样例输入 3

2950 9052
4
2 1
2 2
2 3
2 4

样例输出 3

9
0
5
2