考慮以下定義在正整數上的函數：
$$
\mathrm{collatz}(n)=
\begin{cases}
3n+1 &\text{if }n\text{ is odd,}\\
n/2 &\text{otherwise.}
\end{cases}
$$

1937 年，Lothar Collatz 提出了一個猜想：對於任何正整數，重複代入 $\mathrm{collatz}(\cdot)$ 總有一刻會達到 $1$。

目前已知這個敘述對於所有小於 $2.36\times 10^ {21}$ 的整數都成立。但是，這個猜想是否對所有正整數都成立，仍然是未知數。這些年來，不乏有數學家嘗試證明這個猜想，但都以失敗告終。著名的數學家 Paul Erdős 曾針對此問題給出以下評價：

"Mathematics may not be ready for such problems."

背景故事就到此為止，以下是真正的問題。

給定一個 $n$ 個正整數的陣列 $a_1,a_2,\ldots,a_n$。

接下來依序進行 $q$ 次操作，每個操作都是以下兩種類型之一。

• $1\ l\ r$: 對於所有 $l\le i\le r$，將 $a_i$ 替換為 $\mathrm{collatz}(a_i)$。
• $2\ l\ r$: 輸出 $\sum_{i=l}^ r a_i$。

你能在不使用 LLM 的情況下解決這個問題嗎？