该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

失败尽常态

题目背景

小明最近遇到了很多烦恼，中考失利，没有发挥出理想的水平，得到满意的分数。身边的朋友因为口角也慢慢疏远，父母老师对自己的不理解，感觉整个世界好像都不太待见自己，活着感觉真累。 但其实不如意不舒心才是生活的常态，哪有事事的一帆风顺呢。人生中的大部分事情，可能努力会让成功率到达99%，但是那1%是我们无能为力去决定的，不管我们再怎么去努力也不能保证事事一定成功，那我们能做什么呢？我们要做的就是努力的做好自己的99%，哪有尽如人意，但求无愧于心。

题目描述

小明现在想做的，就是调整一下自己的心情和状态，大不了从头再来。他想统计一下，最近的这n天里面到底遇到了多少的困难，每天都会有一个困难指数，他想做的是多次的去求某段区间的困难指数之和。 但是事情从来都没有这么简单，生活也总是喜欢开玩笑，在小明求区间和的过程中，冥冥之中会出现一个数字x，所有下标是x的因子的困难指数都会加y，这两种操作总计会有Q次。

输入格式

第一行两个整数n和Q，代表困难指数的个数和总共的操作次数 第二行 n 个整数，其中第 i 个表示 第i天的困难指数a[i]。 接下来Q行，每行三个整数op,x,y，其中op=1为修改操作，op=2为询问操作。

输出格式

对于每个询问操作输出每行一个整数，表示询问的结果

样例 #1

样例输入 #1

5 3
1 2 3 4 5
2 1 5
1 5 2
2 1 5

样例输出 #1

15
19

提示

对于30%的数据，1<= N , Q <= 1000 对于另外30%的数据，x , Q <= 50000 对于100%的数据，1<= N ， Q <= 100000 ，x <= 2e9 , y <= 1e9