Making Number

You are given two positive integers $X$ and $Y$ with the same number of digits in base 10. $Z$ is the positive integer in base 10 that satisfies all of the following conditions.

• The digits of $Z$ are a rearrangement of the digits of $X$. The first digit of $Z$ cannot be 0. For example, if $X=1103$, $Z$ can be $1103$ or $3101$, but $Z$ cannot be $2110$, $301$, or $0131$.
• $Y\le Z$.
• $Z$ is the minimum value that satisfies the conditions above.

Process $Q$ queries. Each query is one of the following two types.

• Change the $i$-th digit of $Y$ to $x$.
• Output the $i$-th digit of $Z$. If no such $Z$ exists, output $-1$.

Digits are counted from the left.

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

The second line contains $Q$.

Each of the next $Q$ lines is a query in one of the following forms. The first integer is the query type.

• 1 $i$ $x$: Change the $i$-th digit of $Y$ to $x$.
• 2 $i$: Output the $i$-th digit of $Z$. If no such $Z$ exists, output $-1$.

At least one query of type 2 is given.

For each query of type 2, print the answer on its own line.

$1\le X, Y<10^{100000}$ $1\le Q\le 100000$ $X$ and $Y$ have the same number of digits. The first digits of $X$ and $Y$ are not 0. For a query of type 1, $1\le i\le$ the number of digits of $Y$ and $0\le x\le 9$. If $i=1$, then $x\ne 0$. For a query of type 2, $1\le i\le$ the number of digits of $Y$.