同じ長さの10進法の正の整数 $X$ と $Y$ が与えられます。以下の条件を満たす10進法の正の整数 $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桁は $3$ です。

入力

1行目には、スペースで区切られた2つの整数 $X$ と $Y$ が与えられます。 2行目には、クエリの数である単一の整数 $Q$ が与えられます。 続く $Q$ 行の各行には、クエリを表すスペースで区切られた整数が与えられます。各行は以下のいずれかの形式であり、最初の整数がクエリのタイプを表します。

• "1 $i$ $x$": $Y$ の第 $i$ 桁を $x$ に変更する。
• "2 $i$": $Z$ の第 $i$ 桁を出力する。そのような $Z$ が存在しない場合は $-1$ を出力する。

タイプ2のクエリが少なくとも1つ存在することが保証されています。

正の整数 $A$ の桁数を $\text{len}(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行に出力してください。

入出力例

入力 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