#P1207F. Remainder Problem
-
ID: 4270
Type: RemoteJudge
4000ms
512MiB
Tried: 3
Accepted: 3
Difficulty: 7
Uploaded By:
Hydro
Tags> Remainder Problem
Description
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.
Input
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$.
Output
For each query of type $2$ print one integer — the answer to it.
5
1 3 4
2 3 0
2 4 3
1 4 -4
2 1 0
4
4
0
Related
In following contests: