E. Li Hua и массив
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Li Hua хочет решить задачу о $$$\varphi$$$ — функции Эйлера. Напомним, что $$$\varphi(x)=\sum\limits_{i=1}^x[\gcd(i,x)=1]$$$.$$$^{\dagger,\ddagger}$$$

У него есть последовательность $$$a_1,a_2,\cdots,a_n$$$ и он хочет выполнить $$$m$$$ операций:

  • «1 $$$l$$$ $$$r$$$» ($$$1\le l\le r\le n$$$) — для каждого $$$x\in[l,r]$$$, изменить $$$a_x$$$ на $$$\varphi(a_x)$$$.
  • «2 $$$l$$$ $$$r$$$» ($$$1\le l\le r\le n$$$) — найдите минимальное количество изменений, необходимое для того, чтобы стало верно $$$a_l=a_{l+1}=\cdots=a_r$$$. За одно изменение он выбирает один $$$x\in[l,r]$$$ и изменяет $$$a_x$$$ на $$$\varphi(a_x)$$$.

Каждая операция второго типа является независимой, то есть массив не изменяется.

Предположим, что вы Li Hua. Пожалуйста, решите эту задачу.

$$$^\dagger$$$ $$$\gcd(x,y)$$$ обозначает наибольший общий делитель (НОД) целых чисел $$$x$$$ и $$$y$$$.

$$$^\ddagger$$$ Выражение $$$[\textrm{cond}]$$$ равно $$$1$$$, если условие $$$\textrm{cond}$$$ верно, и $$$0$$$ в противном случае.

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

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\le n,m\le 10^{5}$$$) — количество элементов в массиве и количество операций для обработки, соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_{1},a_{2},\cdots ,a_{n}$$$ ($$$1\le a_{i}\le 5\cdot 10^{6}$$$) — элементы массива.

Далее идут $$$m$$$ строк, каждая строка содержит три целых числа $$$t_{i},l_{i},r_{i}$$$ ($$$t_i\in\{1,2\},1\le l_i\le r_i\le n$$$) — $$$i$$$-я операция.

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

Для каждого запроса вида «2 $$$l$$$ $$$r$$$» выведите ответ в отдельной строке.

Пример
Входные данные
5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4
Выходные данные
10
2
1
Примечание

Обозначим $$$\varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k > 0\end{cases}$$$.

Сначала $$$a=[8,1,6,3,7]$$$.

Чтобы сделать верным выражение $$$a_1=a_2=a_3=a_4=a_5$$$, мы можем изменить $$$a$$$ на $$$a'=[\varphi^3(8),\varphi^0(1),\varphi^2(6),\varphi^2(3),\varphi^3(7)]=[1,1,1,1,1]$$$, используя $$$3+0+2+2+3=10$$$ изменений.

Чтобы сделать $$$a_3=a_4$$$, мы можем изменить $$$a$$$ на $$$a'=[\varphi^0(8),\varphi^0(1),\varphi^1(6),\varphi^1(3),\varphi^0(7)]=[8,1,2,2,7]$$$, используя $$$0+0+1+1+0=2$$$ изменения.

После «1 $$$1$$$ $$$3$$$», $$$a$$$ меняется на $$$a=[\varphi^1(8),\varphi^1(1),\varphi^1(6),\varphi^0(3),\varphi^0(7)]=[4,1,2,3,7]$$$.

Чтобы сделать $$$a_3=a_4$$$, мы можем изменить $$$a$$$ на $$$a'=[\varphi^0(4),\varphi^0(1),\varphi^0(2),\varphi^1(3),\varphi^0(7)]=[4,1,2,2,7]$$$, используя $$$0+0+0+1+0=1$$$ изменение.