CF1207F.Remainder Problem

You are given an array $a$ consisting of $500000$ integers (numbered from $1$ to $500000$). Initially all elements of $a$ are zero.

You have to process two types of queries to this array:

• $1$ $x$ $y$ — increase $a_x$ by $y$;
• $2$ $x$ $y$ — compute $\sum\limits_{i \in R(x, y)} a_i$, where $R(x, y)$ is the set of all integers from $1$ to $500000$ which have remainder $y$ modulo $x$.

Can you process all the queries?

给你一个包含 $500000$ 个整数的数组 $a$（下标从 $1$ 到 $500000$）。初始时，$a$ 的所有元素均为 $0$。

你需要处理对该数组的两类查询：

• $1$ $x$ $y$ — 将 $a_x$ 增加 $y$；
• $2$ $x$ $y$ — 计算 $\sum\limits_{i \in R(x, y)} a_i$，其中 $R(x, y)$ 表示所有在 $1$ 到 $500000$ 范围内、且对 $x$ 取模余数为 $y$ 的整数构成的集合。

你能处理全部查询吗？

The first line contains one integer $q$ ($1 \le q \le 500000$) — the number of queries.

Then $q$ lines follow, each describing a query. The $i$-th line contains three integers $t_i$, $x_i$ and $y_i$ ($1 \le t_i \le 2$). If $t_i = 1$, then it is a query of the first type, $1 \le x_i \le 500000$, and $-1000 \le y_i \le 1000$. If $t_i = 2$, then it it a query of the second type, $1 \le x_i \le 500000$, and $0 \le y_i \lt x_i$.

It is guaranteed that there will be at least one query of type $2$.

第一行包含一个整数 $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 \lt x_i$。

保证至少存在一个类型为 $2$ 的查询。

For each query of type $2$ print one integer — the answer to it.

对于每个类型为 $2$ 的查询，输出一个整数——即该查询的答案。