← 返回题目列表

Codeforces · 1207/F

F. 余数问题

中文机器翻译题面 查看原题

给定一个数组 $$$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