B. Randy Ranges
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Randy is a college student passionate about the ICPC. Some time ago, during the weekly training sessions he has with his team, he learned about range query problems and was fascinated. Since then, Randy always bothers his friends insisting that they solve problems of this style; even his friends from other majors...

During a visit to Lincoln Park, Randy meets a man exercising in an ICPC t-shirt. With an air of superiority, he approaches the man with the most difficult range problem he knew; to his surprise, the man gives him a correct solution less than a second after hearing the problem. Looking closely, Randy realizes that he is talking to Poly, the first Bolivian to obtain the title of Grandmaster in Codeforces and the last living member of the 2880 Algorithms Club.

Poly smiles, happy to meet someone who shares his passion. Playing along with Randy, he says "If you don't solve this problem, I'll hit you." The problem is as follows:

The function $$$f(x)$$$ is defined as the sum of the digits in base $$$10$$$ of $$$x$$$ minus the smallest digit. For example, $$$f(324) = 3 + 2 + 4 - 2 = 7$$$ or $$$f(1100) = 1 + 1 + 0 + 0 - 0 = 2$$$.

Given an array $$$a$$$ of $$$n$$$ integers numbered from $$$1$$$ to $$$n$$$, process $$$q$$$ queries of two types:

  1. Given two integers $$$x$$$ and $$$v$$$, replace the value of $$$a_x$$$ with $$$v$$$
  2. Given two integers $$$l$$$ and $$$r$$$, calculate the minimum number of times the function $$$f(a_i)$$$ must be applied to the elements of $$$a$$$ in the range $$$[l, r]$$$, so that all the elements in that range become equal.

Note that, while processing type 2 queries, the elements of $$$a$$$ do not change.

Randy fails to solve the problem, even after going home and thinking about it for days. Fortunately, today marks the first edition of the SanSi Cup, a programming competition where the best programmers from across the country gather. He goes one by one, but it seems that no one can solve the problem. You are the only person left, you must solve it to prevent Randy from being hit.

Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

The second line contains $$$n$$$ integers forming the array $$$a$$$ ($$$0 \leq a_i \leq 10^{18}$$$).

The third line contains an integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$), indicating the number of queries to be processed.

The following $$$q$$$ lines each contain three integers, indicating the following:

  • If the first integer is equal to $$$1$$$, two integers $$$x$$$ and $$$v$$$ follow $$$(1 \leq x \leq n, 0 \leq v \leq 10^{18})$$$, indicating the values for the type $$$1$$$ query.
  • If the first integer is equal to $$$2$$$, two integers $$$l$$$ and $$$r$$$ follow ($$$1 \leq l \leq r \leq n$$$), indicating the range for the type $$$2$$$ query.
Output

For each type $$$2$$$ query, an integer indicating its response should be printed.

Examples
Input
4
50 5 15 4
3
2 1 3
1 3 14
2 2 4
Output
2
4
Input
8
88 178 146 95 84 198 55 103
5
2 6 8
2 2 5
2 3 8
1 8 169
2 6 7
Output
7
10
14
5
Note

For the first example case:

  • The first query is of type $$$2$$$, the function $$$f(a_i)$$$ needs to be applied twice for all the elements in the range $$$[1,3]$$$ to become equal: $$$f(50)=5, f(15)=5$$$.

  • The second query is of type $$$1$$$, the value of $$$a_3$$$ is replaced by $$$14$$$.

  • The third query is of type $$$2$$$, the function $$$f(a_i)$$$ needs to be applied four times for all the elements in the range $$$[2,4]$$$ to become equal: $$$f(5)=0, f(f(14))=0, f(4)=0$$$.