Description

One day, while thinking about a project, mzry1992 was riding a motorcycle on the highway. A bald guy kicked him, his motorcycle broke down, and he was sent to the school hospital for an IV drip. With the deadline approaching, he has to ask you to help finish the project.

The goal of this project is to maintain a dynamic infinite polynomial in $x$. Initially, for all $i$, we have $a_i = 0$.

$F(x) = a_0 x^0 + a_1 x^1 + a_2 x^2 + \dots$.

There are four types of operations:

• Multiply the coefficients of the terms from $x^L$ to $x^R$ by a fixed value $v$.
• Add a fixed value $v$ to the coefficients of the terms from $x^L$ to $x^R$.
• Multiply the terms from $x^L$ to $x^R$ by the variable $x$.
• Substitute a fixed value $v$ into $F(x)$ and output the resulting value. After the query, the polynomial is restored to its previous state.

After observation, the team found that users mainly use the first three operations, and the fourth operation appears no more than $10$ times. mzry1992 is responsible for the core code of this project. Can you help him implement it?

Input Format

The first line contains an integer $n$, representing the number of operations.

Then follow $n$ lines, each containing one operation in one of the following formats:

• mul L R v: the first type of operation.
• add L R v: the second type of operation.
• mulx L R: the third type of operation.
• query v: the fourth type of operation.

Output Format

For each query operation, output the corresponding answer. Since the result may be large, print it modulo $20130426$.

6
add 0 1 7
query 1
mul 0 1 7
query 2
mulx 0 1
query 3

14
147
588

Hint

[Sample Explanation]

After operation 1, the polynomial is $F(x) = 7 x + 7$.

After operation 3, the polynomial is $F(x) = 49 x + 49$.

After operation 5, the polynomial is $F(x) = 49 x^2 + 49 x$.

Constraints

• For $30\%$ of the testdata: $N \le 5000$, $0 \le L \le R \le 5000$, $0 \le v \le 10^9$.
• For another $20\%$ of the testdata: $N \le 10^5$, $0 \le L \le R \le 10^5$, $0 \le v \le 10^9$, and there is no mulx operation.
• For the remaining $50\%$ of the testdata: $N \le 10^5$, $0 \le L \le R \le 10^5$, $0 \le v \le 10^9$.

Translated by ChatGPT 5