#P1207F. Remainder Problem

    ID: 4270 Type: RemoteJudge 4000ms 512MiB Tried: 3 Accepted: 3 Difficulty: 7 Uploaded By: Tags>brute forcedata structuresimplementation*2100

Remainder Problem

Description

You are given an array aa consisting of 500000500000 integers (numbered from 11 to 500000500000). Initially all elements of aa are zero.

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

  • 11 xx yy — increase axa_x by yy;
  • 22 xx yy — compute iR(x,y)ai\sum\limits_{i \in R(x, y)} a_i, where R(x,y)R(x, y) is the set of all integers from 11 to 500000500000 which have remainder yy modulo xx.

Can you process all the queries?

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

Then qq lines follow, each describing a query. The ii-th line contains three integers tit_i, xix_i and yiy_i (1ti21 \le t_i \le 2). If ti=1t_i = 1, then it is a query of the first type, 1xi5000001 \le x_i \le 500000, and 1000yi1000-1000 \le y_i \le 1000. If ti=2t_i = 2, then it it a query of the second type, 1xi5000001 \le x_i \le 500000, and 0yi<xi0 \le y_i < x_i.

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

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

Input

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

Then qq lines follow, each describing a query. The ii-th line contains three integers tit_i, xix_i and yiy_i (1ti21 \le t_i \le 2). If ti=1t_i = 1, then it is a query of the first type, 1xi5000001 \le x_i \le 500000, and 1000yi1000-1000 \le y_i \le 1000. If ti=2t_i = 2, then it it a query of the second type, 1xi5000001 \le x_i \le 500000, and 0yi<xi0 \le y_i < x_i.

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

Output

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

Sample Input 1

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

Sample Output 1

4
4
0