F. Making Number
time limit per test
1.5 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

You are given two positive integers $$$X$$$ and $$$Y$$$ of the same length in base 10. Let us define $$$Z$$$ as the positive integer in base 10 satisfying the following conditions.

  • The digits of $$$Z$$$ should be a rearrangement of the digits of $$$X$$$. Leading zeros in $$$Z$$$ are not allowed. For example, if $$$X = 1103$$$, $$$Z$$$ can be $$$1103$$$ or $$$3101$$$, but $$$Z$$$ cannot be $$$2110$$$, $$$301$$$, nor $$$0131$$$.
  • $$$Y \leq Z$$$.
  • $$$Z$$$ is the minimum value satisfying the above conditions.

You have to perform $$$Q$$$ queries. Each query is one of the following:

  • Given $$$i$$$ and $$$x$$$, change the $$$i$$$-th digit of $$$Y$$$ into $$$x$$$.
  • Given $$$i$$$, output the $$$i$$$-th digit of $$$Z$$$. If there is no such $$$Z$$$, print $$$-1$$$.

The digits of an integer are numbered from left to right starting from $$$1$$$. For example, The third digit of $$$1234$$$ is $$$3$$$.

Input

The first line contains two space-separated integers, $$$X$$$ and $$$Y$$$.

The second line contains a single integer $$$Q$$$, the number of queries.

Each of the following $$$Q$$$ lines contains space-separated integers describing the queries. Each line has one of the following forms, where the first integer represents the type of the query:

  • "1 $$$i$$$ $$$x$$$": Change the $$$i$$$-th digit of $$$Y$$$ to $$$x$$$.
  • "2 $$$i$$$": Output the $$$i$$$-th digit of $$$Z$$$. If there is no such $$$Z$$$, print $$$-1$$$.

It is guaranteed that there is at least one query of type 2.

Let $$$\mathrm{len}(A)$$$ be the number of digits in a positive integer $$$A$$$.

  • $$$1 \leq X, Y < 10^{100\,000}$$$
  • $$$1 \leq Q \leq 100\,000$$$
  • $$$\mathrm{len}(X) = \mathrm{len}(Y)$$$
  • The first digits of $$$X$$$ and $$$Y$$$ are not $$$0$$$.
  • For a query of type 1, $$$1 \leq i \leq \mathrm{len}(Y)$$$, $$$0 \leq x \leq 9$$$, and if $$$i = 1$$$, then $$$x \neq 0$$$.
  • For a query of type 2, $$$1 \leq i \leq \mathrm{len}(Y)$$$.
Output

For each query of type 2, output a single line with the answer to the query.

Examples
Input
3304 1615
6
2 3
2 4
1 1 3
2 2
1 2 4
2 1
Output
3
4
0
3
Input
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
Output
8
0
3
4
6
8
-1
Input
2950 9052
4
2 1
2 2
2 3
2 4
Output
9
0
5
2