У вас есть массив \(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\).
Можете ли вы обработать все запросы?
Выходные данные
Для каждого запроса типа \(2\) выведите одно целое число — ответ на этот запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3 4
2 3 0
2 4 3
1 4 -4
2 1 0
|
4
4
0
|