Multiple and Factor

Problem Description

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

• 1 x k：给 $x$ 倍数的下标位置上的值加 $k$。
• 2 x k：给 $x$ 因数的下标位置上的值加 $k$。
• 3 x：查询 $x$ 倍数的下标位置上所有数的和。
• 4 x：查询 $x$ 因数的下标位置上所有数的和。 共有 $m$ 次操作，你需要在每次查询操作后输出答案。

Input

第一行输入两个整数 $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$），表示一次修改或查询操作。

Output

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

Sample Input

10 7
1 1 4 5 1 4 1 9 1 9
4 8
2 9 3
1 3 2
3 1
3 2
2 8 2
4 10

Sample Output

16
51
30
19

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（10）