Tổng Theo Số Dư

Có một mảng $a_1,\dots ,a_{5\cdot 10^5}$, ban đầu mọi phần tử bằng $0$. Bạn cần xử lý các phép cộng tại một vị trí và các truy vấn tổng theo lớp số dư của chỉ số.

• $1$ $x$ $y$: thực hiện $a_x\leftarrow a_x+y$.
• $2$ $x$ $y$: in $\sum a_i$ trên mọi chỉ số $1\le i\le 5\cdot 10^5$ thỏa $i\mathrm{mod}x=y$.

Input

• Dòng đầu chứa $q$. Mỗi trong $q$ dòng tiếp theo mô tả một thao tác theo một trong hai dạng trên.

Output

• Với mỗi thao tác loại $2$, in tổng được yêu cầu.

Constraints

• $1\le q\le 5\cdot 10^5$.
• Với loại $1$: $1\le x\le 5\cdot 10^5$ và $-1000\le y\le 1000$.
• Với loại $2$: $1\le x\le 5\cdot 10^5$ và $0\le y<x$.
• Có ít nhất một thao tác loại $2$.
• Mọi đáp án nằm trong miền số nguyên $64$ bit có dấu.

Scoring

• Subtask $1$ ($50$ điểm): $q\le 2000$.
• Subtask $2$ ($50$ điểm): không có ràng buộc bổ sung.

Example

7
1 3 5
1 8 4
1 10 -2
2 5 3
2 4 0
1 8 -1
2 2 0

9
4
1