题目描述

一个长为 $n$ 的序列 $a$（下标从 $1$ 开始），两种操作：

• 1 x y 将所有下标为 $x$ 的倍数的数加上 $y$。
• 2 x 求所有下标为 $x$ 的倍数的数的和。

数据随机。即，每次的 $x$ 均在 $[1,n]$ 均匀随机生成。

输入格式

第一行两个整数 $n,m$，$m$ 为操作数。

接下来一行 $n$ 个整数，描述序列 $a$。

接下来 $m$ 行，每行一个操作，格式如上。所有的 $x$ 和 $y$ 均为整数。

输出格式

对于每个 $2$ 操作输出答案。

样例

输入

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

输出

6
9
18

数据范围

对于 $80\%$ 的数据，$n,m\le 10$；

对于 $90\%$ 的数据，$n,m\le 5\times 10^4$；

对于 $100\%$ 的数据，$1\le n,m\le 10^6$，$1\le x,a_i\le 10^6$（这里的 $a_i$ 为其初值）。

样例解释