A password is a number that is exactly divisible by 9. It is the largest number that can be formed by rearranging all the available digits in a provided range (\(L,\ R\)) inclusive and adding another number of your own choice to this sequence at any position. The password is missing a digit that must be added. You are also given an encrypted number. You are also provided \(q\) queries. The queries could be of two types.

• Update a digit at a position.
• Determine the largest number that is divisible by 9 in the provided range with the mentioned conditions. In the provided mentioned number, print its \(x^{th}\) digit.

You must retrieve the password.

Input format

• First line: A string \(s\)
• Second line: A number \(q\) indicating the number of questions that must be asked
• Third line:
  • For each \(q\):
    • A number \(t\) indicating the type of query 1 to update and 2 for the query
    • For a query of type 1, two numbers follow \(x\) and \(y\).
      Update the value at position \(x\) (1-based indexing) to \(y\).
    • For a query of type 2, three numbers follow \(l\), \(r\), \(x\).
      Determine the \(x^{th}\) digit between \(l\) to \(r\) inclusive (1-based indexing) for the retrieved password.

Output format

For each query of type 2, print the \(x^{th}\) digit of the formed password.

Constraints

\(|s|\le 10^6\\ q\le 5 \times 10^5\\ 0<x \le |s|\ and\ 0 \le y \le 9\\ 0< l \le r \le |s|\ and\ x\le (r-l+2)\)