Li Hua and Array

Description:

Input:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1\le n,m\le 10^{5}$$$) — the number of elements in the array and the number of operations to process, respectively.

The second line contains $$$n$$$ integers $$$a_{1},a_{2},\cdots ,a_{n}$$$ ($$$1\le a_{i}\le 5\cdot 10^{6}$$$) — the elements of the array.

Next $$$m$$$ lines, each line contains three integers $$$t_{i},l_{i},r_{i}$$$ ($$$t_i\in\{1,2\},1\le l_i\le r_i\le n$$$) — the $$$i$$$-th operation.

Output:

For each "2 $$$l$$$ $$$r$$$", output the answer in an separate line.

Sample Input:

5 4
8 1 6 3 7
2 1 5
2 3 4
1 1 3
2 3 4

Sample Output:

10
2
1

Note:

Denote $$$\varphi^k(x)=\begin{cases}x,&k=0\\\varphi(\varphi^{k-1}(x)),&k > 0\end{cases}$$$.

At first, $$$a=[8,1,6,3,7]$$$.

To make sure $$$a_1=a_2=a_3=a_4=a_5$$$, we can change $$$a$$$ to $$$a'=[\varphi^3(8),\varphi^0(1),\varphi^2(6),\varphi^2(3),\varphi^3(7)]=[1,1,1,1,1]$$$, using $$$3+0+2+2+3=10$$$ changes.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(8),\varphi^0(1),\varphi^1(6),\varphi^1(3),\varphi^0(7)]=[8,1,2,2,7]$$$, using $$$0+0+1+1+0=2$$$ changes.

After "1 $$$1$$$ $$$3$$$", $$$a$$$ is changed to $$$a=[\varphi^1(8),\varphi^1(1),\varphi^1(6),\varphi^0(3),\varphi^0(7)]=[4,1,2,3,7]$$$.

To make sure $$$a_3=a_4$$$, we can change $$$a$$$ to $$$a'=[\varphi^0(4),\varphi^0(1),\varphi^0(2),\varphi^1(3),\varphi^0(7)]=[4,1,2,2,7]$$$, using $$$0+0+0+1+0=1$$$ change.