A12805 | 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?

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 < x_i$ .

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

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