nodgd家里有很多狗！太多的狗给nodgd带来了各种麻烦，于是nodgd决定开个赶走一些狗！
nodgd首先按照狗的品种把所有狗分成N类，依次是第1类，第2类，...，第N类。刚开始第i类有a_i只。
nodgd有时候会心情不爽，就会把第l类、第l+1类、第l+2类、...、第r-1类、第r类的每类狗都进行这样的操作：
  第一步，把这类狗排成一个尽量大的正方形方阵，多余的狗就赶走！
  第二步，在正方形方阵中每一横排任选一条狗留下，其余全部赶走！
当然，狗也是需要喂食的，喂食之前需要先知道有多少条狗。因为赶走了一些狗，所以nodgd也记不清楚到底有多少条狗了，他可能会问你，第l类、第l+1类、第l+2类、...、第r-1类、第r类一共还剩多少条狗？你作为一个优秀的程序员，当然可以写个程序来回答nodgd的提问啦！

简化版题目描述：给个序列，区间开方，向下取整，区间求和。

第一行两个整数N,M，分别表示狗的种类数和操作次数
第二行N个整数a₁,a₂,...,a_N，表示每类狗一开始有多少条
接下来M行，每行三个整数k,l,r。若k=0则表示nodgd心情不爽了又要赶走一些狗了，若k=1则表示nodgd打算给狗喂食了就先向你提问

对于nodgd的每次提问输出答案

样例解释：
第一次操作之后狗的数量分别是1,1,1,2,2,2,2,2,3,3.
第四次操作之后狗的数量分别是1,1,1,2,1,1,1,1,3,3.

数据范围：
1<=N<=100000
1<=M<=100000
1<=a_i<=10¹²
1<=l<=r<=N

nodgd很懒就只造了6个测试点