考拉兹猜想_信奥算法普及+/提高

考拉兹猜想（Collatz conjecture），又称为奇偶归一猜想、 $3n+1$ 猜想、冰雹猜想、角谷猜想、哈塞猜想、乌拉姆猜想或叙拉古猜想。

指对于每一个正整数，如果它是奇数，则对它乘 $3$ 再加 $1$ ；如果它是偶数，则对它除以 $2$ ，如此循环，最终都能够得到 $1$ 。

即对于任意正整数 $n$ ，我们定义

$f(n) = \begin{cases} n / 2 &\tt{if\ n \equiv 0 \pmod{2}}\\ 3n + 1 &\tt{if\ n \equiv 1 \pmod{2}} \end{cases}$

现重复执行该运算，形成一个序列，从任意正整数开始，把每步的结果作为下一步的输入。可记作：

$a_i = \begin{cases} n &\tt{i = 0}\\ f(a_{i - 1}) &\tt{i > 0} \end{cases}$

考拉兹猜想是：所有正整数最终都会到达 $1$ ，即对于上式，存在 $i$ 使得 $a_i = 1$ 。

迄今为止，该猜想经过计算验证，所有不超过 $2^{68} \approx 2.95 \times 10^{20}$ 的正整数，经过上述计算都可以得到 $1$ 。

给定一个长度为 $N$ 的数组 $A_1, A_2, \cdots, A_N$ 。

你需要执行 $Q$ 个操作，第 $i$ 个操作的类型为 $T_i$ ：

$T_i = 1$ ：给定两个整数 $L_i$ 和 $R_i$ ，对数组中 $[L_i, R_i]$ 区间内所有大于 $1$ 的元素 $A_i$ 变为 $f(A_i)$ 。
$T_i = 2$ ：给定两个整数 $L_i$ 和 $R_i$ ，统计数组中区间 $[L_i, R_i]$ 内值为 $1$ 的元素的个数。

$\large{数据范围}$

对于每个测试文件输入格式如下：

$\tt{N\ Q}$
$\tt{A_1\ A_2\ \cdots\ A_N}$
$\tt{T_1\ L_1\ R_1}$
$\tt{T_2\ L_2\ R_2}$
$\tt{\vdots}$
$\tt{T_Q\ L_Q\ R_Q}$

对于所有的 $T_i = 2$ 在单独的一行中输出数组中区间 $[L_i, R_i]$ 内值为 $1$ 的元素的个数。

输入#1

10 8
1 7 16 3 6 10 8 5 2 4
2 1 10
1 1 10
1 2 8
1 3 9
1 2 8
2 1 5
1 4 10
2 7 10

输出#1

1
2
4

$\bf{样例\ 1：}$

A35298.考拉兹猜想