题目描述

小 H 是一个数学大佬，他最喜欢研究一些怪怪的函数。

今天他研究出了一个特别有意思的函数 $f(x)$，表示 $x$ 的各个位数之和，例如 $f(1)=1,f(19)=10,f(222)=6$。现在有一个百思不得其解的问题难住他了，有一个长度为 $n$ 的数组 $a_i$，有 $m$ 条指令，每条指令会输入 $3$ 个正整数，表示操作的类型，区间左端点，区间右端点：

• $1$ 操作：给定 $L,R$，将闭区间 $[L,R]$ 里面的每个数都作用 $f(x)$。

• $2$ 操作：给定 $L,R$，求闭区间 $[L,R]$ 里面的数的最小值。

小 H 太菜了，求求你了快帮帮他吧。

输入格式

第一行一个正整数 $n$（$1\le n \le 2\times10^5$），表示数组的长度。

第二行 $n$ 个正整数 $a_i$（$1\le a_i\le10^{18}$），表示数组中的每个元素。

第三行一个正整数 $m$（$1\le m \le 2\times10^5$），表示指令条数。

接下来的 $m$ 行，每行 $3$ 个正整数 $op,L,R$（$op\in (1,2),1\le L\le R\le n$），其中 $op$ 表示操作类型。

输出格式

对于每个操作 $2$ 你需要输出一行一个正整数表示答案。

输入样例

5
100 9 43 23 8
9
2 1 2
2 1 3
2 1 5
1 3 3
2 1 5
1 2 5
2 1 5
1 1 1
2 1 2

输出样例

9
9
8
7
5
1

提示

执行一次 $1$ 操作后数列变为：$[100,9,7,23,8]$

执行两次 $1$ 操作后数列变为：$[100,9,7,5,8]$

执行三次 $1$ 操作后数列变为：$[1,9,7,5,8]$