题目背景

Problem	Score	Idea	Std	Data	Check	Solution
$\text{E - Experiments on Collatz}$	$475$	joe_zxq			fcy20180201	Link by joe_zxq

有朝一日，当星辰与智慧交相辉映，那些曾经的数学难题终将在人类不懈的探索下迎刃而解。那一刻，不仅是难题的征服，更是心灵与理性的飞跃。人类将在数学的浩瀚宇宙中，以无畏的勇气与无尽的好奇，继续前行，越走越远，于未知中播种希望，于挑战中绽放辉煌，书写属于全人类的智慧篇章。

---

这使你充满了决心。

题目描述

角谷猜想由日本数学家角谷静夫提出，是指对于每一个正整数 $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 知道这个问题对于你太难了，所以不存在这样的询问。但是聪明的你能解决这个数学难题吗？

输入格式

第一行包含一个正整数 $Q$，表示询问的次数。

接下来 $Q$ 行，每行输入格式为 1 x 或 2 l r，表示询问内容。

输出格式

对于每次询问，包含一行一个整数，表示询问的答案。

5
1 1
1 2
1 7
1 8
2 2 4

2
3
3
6
14

3
1 114
1 514
2 114514 1919810

73
837799
248276873

提示

样例解释 #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$。

提示

请使用较快的读写方式。