Обозначим за D(x) количество положительных делителей натурального числа x. К примеру, D(2) = 2 (2 делится на 1 и 2), D(6) = 4 (6 делится на 1, 2, 3 и 6).
Вам дан массив a из n целых чисел. Нужно обрабатывать два вида запросов:
- REPLACE l r — для каждого
заменить ai на D(ai); - SUM l r — посчитать
.
Выведите ответ на каждый запрос 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
