3∑+1?

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

玄黄最近发明了一个神奇的函数:

Xh(x)=3*( ∑(x的每一位) )+1 ,x为自然数。

现在你面前有n个自然数,玄黄现在要求你完成两种操作 。
1、帮玄黄求出这n个数中,区间 [l, r] 的和,并把答案告诉玄黄 。
2、帮玄黄把区间 [l, r] 中的每一个数 x 都变成 Xh(x)。

Input

第一行输入一个正整数n(0 第二行输入n个自然数,下标从 1 至 n,每个自然数大小不超过 100000000003。 
第三行输入一个正整数m(0 之后有m行,每行输入三个数op, l, r( 0 < op <3, 1 <= l <=r <=n ),op 代表玄黄要求你的操作编号,op 为 1 时执行第一种操作,op 为 2 时执行第二种操作,l 和 r 代表区间范围 。

Output

当 op 为 1 时,输出区间 [l, r] 的和,每次输出占一行。

Sample Input

5 
1 3 5 7 9 
5 
1 1 5 
2 3 5 
1 3 4 
2 1 3 
1 2 5

Sample Output

25 
38 
82

Hint

Source

玄黄