Обозначим за D(x) количество положительных делителей натурального числа x. К примеру, D(2) = 2 (2 делится на 1 и 2), D(6) = 4 (6 делится на 1, 2, 3 и 6).
Вам дан массив a из n целых чисел. Нужно обрабатывать два вида запросов:
Выведите ответ на каждый запрос SUM.
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 3·105) — количество элементов в массиве и количество запросов, соответственно.
Во второй строке заданы n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 106) — элементы массива.
Затем следуют m строк, в каждой из которых записаны 3 целых числа ti, li, ri, обозначающих i-й запрос. Если ti = 1, то i-й запрос — REPLACE li ri, иначе это запрос SUM li ri (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n).
Хотя бы один запрос имеет тип SUM.
Для каждого запроса SUM выведите ответ на него.
7 6 6 4 1 10 3 2 4 2 1 7 2 4 5 1 3 5 2 4 4 1 5 7 2 1 7
30 13 4 22
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач