Teacher Mai 发现许多关于算术函数的问题都可以归约为以下问题：
维护一个下标从 $1$ 到 $l$ 的数组 $a$。有两种操作：
- 对于所有满足 $\gcd(x, n) = d$ 的 $x$，将 $v$ 加到 $a_x$ 上。
- 查询 $\sum_{i=1}^{x} a_i$。
输入格式
输入包含多组测试数据，以一行 “0 0” 结束。
对于每组测试数据，第一行包含两个整数 $l, Q$ ($1 \le l, Q \le 5 \cdot 10^4$)，分别表示数组的长度和操作次数。
接下来的 $Q$ 行，每行表示一个操作，格式为 “1 n d v” 或 “2 x” ($1 \le n, d, v \le 2 \cdot 10^5, 1 \le x \le l$)。输入文件总大小不超过 7 MB。
输出格式
对于每组测试数据，输出每个查询的答案，每个答案占一行。
样例
样例输入 1
6 4 1 4 1 2 2 5 1 3 3 3 2 3 0 0
样例输出 1
6 7