题目描述

有一个长度为 $5 \times 10^5$ 的数列 $a$，数列下标从 $1$ 到 $5 \times 10^5$。初始时数列中的所有元素的数值均为 $0$。

你需要对这个数列进行 $q$ 次操作，操作分为如下两种类型：

• 1 x y：将 $a_x$ 的数值增加 $y$；
• 2 x y：查询 $\sum\limits_{i \in R(x, y)} a_i$。其中 $R(x, y)$ 表示 $1$ 到 $5 \times 10^5$ 范围内所有满足模 $x$ 为 $y$ 的数组成的集合。也就是说，对于每次查询操作，你需要计算数列 $a$ 中所有除以 $x$ 的余数为 $y$ 的下标对应的元素之和。

输入格式

第一行，一个整数 $q(1 \le q \le 5 \times 10^5)$，表示操作次数。

接下来 $q$ 行，每行包含三个整数 $t_i, x_i, y_i(1 \le t_i \le 2)$。

如果 $t_i = 1$，这是一个更新操作，其中 $1 \le x_i \le 5 \times 10^5, -1000 \le y_i \le 1000$；
如果 $t_i = 2$，这是一个查询操作，其中 $1 \le x_i \le 5 \times 10^5, 0 \le y_i \lt x_i$。

输出格式

对于每次查询操作，输出一行，包含一个整数，表示数列 $a$ 中所有除以 $x$ 的余数为 $y$ 的下标对应的元素之和。

样例

5
1 3 4
2 3 0
2 4 3
1 4 -4
2 1 0

4
4
0

12
1 13 -20
1 5 4
1 2 20
1 8 20
2 5 0
1 15 7
1 6 12
2 6 1
2 16 7
1 8 -10
2 7 4
2 13 9

4
-20
0
0
0

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$q \le 50$，对于 1 x y 操作，$x \le 50, |y| \le 10$，对于 2 x y 操作，$x \le 50$
• 对于 $60\%$ 的数据，$q \le 5000$，对于 1 x y 操作，$x \le 5000, |y| \le 100$，对于 2 x y 操作，$x \le 5000$
• 对于 $100\%$ 的数据，$q \le 5 \times 10^5$，对于 1 x y 操作，$1 \le x \le 5 \times 10^5, |y| \le 1000$，对于 2 x y 操作，$0 \le y \lt x \le 5 \times 10^5$