給定兩個長度相同的十進位正整數 $X$ 與 $Y$。定義 $Z$ 為滿足下列條件的十進位正整數：

• $Z$ 的位數必須是 $X$ 的位數的一種重排。$Z$ 不允許有前導零。例如，若 $X = 1103$，$Z$ 可以是 $1103$ 或 $3101$，但 $Z$ 不能是 $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