P11683 [Algo Beat Contest 001 E] Experiments on Collatz

| Problem | Score | Idea | Std | Data | Check | Solution | | :---------------------------------: | :---: | :---------------------------------------------------: | :----------------------------------------------------------: | :---------------------------------------------: | :----------------------------------------------------------: | :----------------------------------------------------------: | | $\text{E - Experiments on Collatz}$ | $475$ | [joe_zxq](https://www.luogu.com.cn/user/623577) | [joe_zxq](https://www.luogu.com.cn/user/623577) | [joe_zxq](https://www.luogu.com.cn/user/623577) | [fcy20180201](https://www.luogu.com.cn/user/866154) | [Link](https://www.luogu.com.cn/article/1bqxjjm6) by [joe_zxq](https://www.luogu.com.cn/user/623577) | 有朝一日，当星辰与智慧交相辉映，那些曾经的数学难题终将在人类不懈的探索下迎刃而解。那一刻，不仅是难题的征服，更是心灵与理性的飞跃。人类将在数学的浩瀚宇宙中，以无畏的勇气与无尽的好奇，继续前行，越走越远，于未知中播种希望，于挑战中绽放辉煌，书写属于全人类的智慧篇章。 ------------ 这使你充满了决心。

角谷猜想由日本数学家角谷静夫提出，是指对于每一个正整数 $n$，如果它是奇数，则对它乘 $3$ 再加 $1$，如果它是偶数，则对它除以 $2$，如此循环，最终都能够得到 $1$，故又称为 $3n+1$ 猜想。 如 $n = 6$，根据上述操作，得出 $6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$。 小 Z 对这个猜想十分感兴趣，因为如此简单易懂的猜想却从来无人证明，也无人推翻。于是他决定开始研究这个问题。 定义 $f(n)$ 表示正整数 $n$ 变为 $1$ 需要的操作次数，例如 $f(6)=8$。保证在 $1 \sim 10^7$ 的范围内，角谷猜想是正确的。 形象地说，$f(n)$ 的计算步骤如下图所示：  小 Z 的计算能力很差，于是想让你帮他进行计算。他将会对你进行 $Q$ 次询问，类型为 $t \in \{1,2\}$： - 若 $t=1$，读入整数 $x$，请你求出最小的 $y$，使得 $f(y) \ge x$。 - 若 $t=2$，读入正整数 $l$ 和 $r$，请你求 $ \prod\limits_{i=l}^{r} f(i) \bmod 1145141923$。 - 若 $t=3$，请你判断角谷猜想是否是正确的。当然啦，小 Z 知道这个问题对于你太难了，所以不存在这样的询问。但是聪明的你能解决这个数学难题吗？

无

无

#### 样例解释 #1 如表所示，是 $1 \le n \le 6$ 的 $f(n)$ 的值。 | 函数 | 函数值 | | :----: | :----: | | $f(1)$ | $0$ | | $f(2)$ | $1$ | | $f(3)$ | $7$ | | $f(4)$ | $2$ | | $f(5)$ | $5$ | | $f(6)$ | $8$ | 对于第一次询问，$f(2) \ge 1$，可以证明没有 $y < 2$ 使得 $f(y) \ge 1$。 对于第二次询问，$f(3) \ge 2$，可以证明没有 $y < 3$ 使得 $f(y) \ge 2$。 对于第三次询问，$f(3) \ge 7$，可以证明没有 $y < 3$ 使得 $f(y) \ge 7$。 对于第四次询问，$f(6) \ge 8$，可以证明没有 $y < 6$ 使得 $f(y) \ge 8$。 对于第五次询问，$f(2) \times f(3) \times f(4) = 1 \times 7 \times 2 = 14$。 #### 样例解释 #2 对于 $t=2$ 的询问，注意对 $1145141923$ 取模。 #### 数据范围 对于 $100\%$ 的数据，保证 $1 \le Q \le 10^6$。对于每次询问，$t \in \{1,2\}$。对于每次 $t=1$ 的询问，$0 \le x \le 685$。对于每次 $t=2$ 的询问，$1 \le l \le r \le 10^7$。 #### 提示 请使用较快的读写方式。