"好像有点感觉哦"--小x(Master of Graph)
每当图论大师小x看到图,他都会说一句"好像有点感觉哦",他以为自己有掌控图的能力,能把某些特定编号的点的权值修改成自己想要的值,所以每次修改后他都会自信回头(不管了),
但是他的队友(咋胡佬)发现小x并没有把那些特定编号的点的权值修改成他想要的值,由于小x给力的操作(给力哦铁汁),假设点原来的权值为x,修改后会变成f(x)
(f(x)是统计十进制数字x每一位的和),
咋胡佬发现了这一规律后,自信满满地来到小x面前询问他某些特定编号的点的权值和,
您作为小x的死忠粉iXiang也发现了这一规律,自然不希望自己的idol(偶像)受到质疑,因此您决定帮助小x一一回答咋胡佬的问题
输入描述:
第一行一个数字n,m(1 <= n,m <= 100000,以空格分隔),表示图的点数和边数。
第二行n个数字ai(0 <= ai <= 1000000000000,以空格分隔),表示编号为i的点的权值为ai。
接下来m行,每行两个数字(1 <= u,v <= n),代表编号u的点和编号为v的点之间的无向边
接下来一行,一个数字q(1 <= q <= 100000),表示有q个事件。
接下来q行，每行三个数字"x l r",（1 <= l <= r <= n)。
若x为1,代表小x对编号为l到r所有点的权值进行修改,您无需输出,但修改对后面的事件有影响
若x为0,代表咋胡佬对小x的询问,您需要输出编号l到r所有点的权值和
输出描述:
对于每个操作0，输出编号区间[l,r]的和。
示例1
输入
复制
10 9
3841 45109 42780 10844 63078 15424 7341 8629 56972 10886
1 2
1 3
2 4
2 5
7 4
5 8
6 3
6 9
10 9
6
1 2 10
0 10 10
0 9 10
0 2 3
1 3 3
0 1 10