Hôm nay là buổi học hè đầu tiên của lớp X, cô giáo tổ chức một trò chơi nho nhỏ để tăng sự hứng thú học tập của các bạn học sinh. Vì đây chỉ là một trò chơi nho nhỏ, nên chúng cực kỳ dễ. Và đặc biệt hơn nữa, là bạn nào chiến thắng trò chơi này sẽ có thưởng. Vì thế, các bạn học sinh ai cũng cố gắng hết sức để có thể giành chiến thắng. Nội dung trò chơi như sau:

Cô giáo đưa ra một dãy số ~A~ gồm ~N~ phần tử được đánh số từ ~1~ đến ~N~. Giá trị ban đầu của tất cả các phần tử đều là ~0~. Cô giáo sẽ thực hiện ~Q~ thao tác gồm ~2~ loại, mỗi loại có nội dung như sau:

• ~1\ x\ y~: Cô giáo sẽ tăng giá trị của phần tử ở ~A_x~ lên ~y~ đơn vị.

• ~2\ a\ b~: Cô giáo yêu cầu các bạn hãy tính tổng ở tất cả giá trị của các phần tử ~A_k~ thỏa mãn: ~1 \le k \le N~ và ~k \bmod a=b~.

Cô giáo yêu cầu rằng ai trả lời đúng hết các câu hỏi mới là người có khả năng dành chiến thắng. Tất cả mọi người vẫn chưa nhận ra rằng, trò chơi này khó thế nào. Chỉ có duy nhất Tèo - một bạn học giỏi thứ Z lớp, thấy rằng trò này rất khó để chiến thắng. Sắp đến lúc bắt đầu trò chơi mà cậu vẫn chưa nghĩ ra cách nào để chiến thắng, thì chợt nghĩ đến bạn - thiên tài tin học. Bạn hãy viết một chương trình để giúp Tèo chiến thắng trò chơi này nhé!

Input

• Dòng thứ nhất chứa hai số nguyên dương ~N~ và ~Q~ lần lượt là số phần tử của mảng và số thao tác của cô giáo.

• Dòng thứ ~i~ trong số ~Q~ dòng tiếp theo, mỗi dòng là một trong hai thao tác:

  • ~1\ x\ y~: ~1 \le x \le N, -1000 \le y \le 1000~.

  • ~2\ a\ b~: ~1 \le a \le N, 0 \le b < a~.

Output

Gồm nhiều số nguyên, mỗi số nguyên được ghi trên một dòng là kết quả của thao tác loại ~2~.

Scoring

Sample Input 1

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

Sample Output 1

3
3
-6