给定一个数组 $$$a$$$,由 $$$500000$$$ 整数组成(编号从 $$$1$$$ 到 $$$500000$$$)。最初 $$$a$$$ 的所有元素都为零。
您必须处理对此数组的两种类型的查询:
- $$$1$$$ $$$x$$$ $$$y$$$ — 将 $$$a_x$$$ 增加 $$$y$$$;
- $$$2$$$ $$$x$$$ $$$y$$$ — 计算 $$$\sum\limits_{i \in R(x, y)} a_i$$$,其中 $$$R(x, y)$$$ 是从 $$$1$$$ 到 $$$500000$$$ 的所有整数的集合,其中余数为 $$$y$$$模$$$x$$$。
您能处理所有查询吗?
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 500000$$$) — 查询数量。
接下来是 $$$q$$$ 行,每行描述一个查询。第 $$$i$$$ 行包含三个整数 $$$t_i$$$、$$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le t_i \le 2$$$)。如果$$$t_i = 1$$$,那么它是第一类型的查询,$$$1 \le x_i \le 500000$$$,和$$$-1000 \le y_i \le 1000$$$。如果$$$t_i = 2$$$,则它是第二种类型的查询,$$$1 \le x_i \le 500000$$$,并且$$$0 \le y_i < x_i$$$。
保证至少有一个 $$$2$$$ 类型的查询。
输出
对于 $$$2$$$ 类型的每个查询,打印一个整数 - 它的答案。
示例
输入 #1
5 1 3 4 2 3 0 2 4 3 1 4 -4 2 1 0
输出 #1
4 4 0