F. Задача об остатках
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$, состоящий из $$$500000$$$ целых чисел (элементы нумеруются от $$$1$$$ до $$$500000$$$). Изначально все элементы $$$a$$$ — нули.

К этому массиву поступают запросы двух типов:

  • $$$1$$$ $$$x$$$ $$$y$$$ — увеличить $$$a_x$$$ на $$$y$$$;
  • $$$2$$$ $$$x$$$ $$$y$$$ — посчитать $$$\sum\limits_{i \in R(x, y)} a_i$$$, где $$$R(x, y)$$$ — множество всех целых чисел от $$$1$$$ до $$$500000$$$, дающих остаток $$$y$$$ при делении на $$$x$$$.

Можете ли вы обработать все запросы?

Входные данные

В первой строке записано одно целое число $$$q$$$ ($$$1 \le q \le 500000$$$) — количество запросов.

Затем следуют $$$q$$$ строк, каждая из которых задает запрос. В $$$i$$$-й строке записаны три целых числа $$$t_i$$$, $$$x_i$$$ и $$$y_i$$$ ($$$1 \le t_i \le 2$$$). Если $$$t_i = 1$$$, то это запрос первого типа, $$$1 \le x_i \le 500000$$$, и $$$-1000 \le y_i \le 1000$$$. Если $$$t_i = 2$$$, то это запрос второго типа, $$$1 \le x_i \le 500000$$$, и $$$0 \le y_i < x_i$$$.

Гарантируется, что во входных данных есть хотя бы один запрос типа $$$2$$$.

Выходные данные

Для каждого запроса типа $$$2$$$ выведите одно целое число — ответ на этот запрос.

Пример
Входные данные
5
1 3 4
2 3 0
2 4 3
1 4 -4
2 1 0
Выходные данные
4
4
0