Collatz Conjecture Queries

The famous Collatz Conjecture (also known as the 3n+1 conjecture) is formulated as follows. For each positive integer \(n\), if \(n\) is odd, replace it with \(3n+1\); if \(n\) is even, replace it with \(n/2\). Repeating this process, the conjecture asserts that no matter which positive integer you start with, you always eventually reach 1.

For example, if \(n = 6\), the sequence is \[ 6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1, \] so we define \(f(6)=8\) (the number of operations needed to transform 6 into 1).

In this problem, let \(f(n)\) denote the number of operations required for \(n\) to become 1. You will be given \(Q\) queries. Each query is of one of the following types (where \(t \in \{1,2,3\}\)):

• Type 1: Given an integer \(x\), find the smallest positive integer \(y\) such that \(f(y) \ge x\).
• Type 2: Given two positive integers \(l\) and \(r\), compute \[ \prod_{i=l}^{r} f(i) \bmod 1145141923. \]
• Type 3: Determine whether the Collatz Conjecture is true. (Note: such queries will never appear.)

Note: It is guaranteed that the Collatz Conjecture holds for all \(n\) in the range \([1, 10^7]\).

inputFormat

The first line contains a single integer \(Q\), which denotes the number of queries. Each of the following \(Q\) lines represents a query. Each query starts with an integer \(t\) (\(t \in \{1, 2, 3\}\)).

• If \(t = 1\): a single integer \(x\) follows.
• If \(t = 2\): two integers \(l\) and \(r\) follow.
• If \(t = 3\): (this query will not appear, but if it does, you may output any answer).

outputFormat

For each query, output the answer on a separate line:

• For Type 1: output the smallest \(y\) such that \(f(y) \ge x\).
• For Type 2: output \( \prod_{i=l}^{r} f(i) \bmod 1145141923 \).
• For Type 3: output your answer regarding the truth of the Collatz Conjecture.

sample

2
1 8
2 6 6

6
8