给定一个长度为 $n$ 的序列 $a$，你需要支持以下四种操作：

• 1 x k：给 $x$ 倍数的下标位置上的值加 $k$。
• 2 x k：给 $x$ 因数的下标位置上的值加 $k$。
• 3 x：查询 $x$ 倍数的下标位置上所有数的和。
• 4 x：查询 $x$ 因数的下标位置上所有数的和。

共有 $m$ 次操作，你需要在每次查询操作后输出答案。

第一行输入两个整数 $n,m$（$1\le n,m\le 5\cdot 10^5$），表示序列的长度和操作次数。

第二行输入 $n$ 个整数，表示序列 $a_1,\dots,a_n$（$0\le a_i\le 10^9$）。

接下来 $m$ 行，每行输入三个整数 op x k 或两个整数 op x（$1\le op\le 4$，$1\le x\le n$，$0\le k\le 10^7$），表示一次修改或查询操作。

对于每次查询操作，输出一行一个整数，表示答案。