Description

On a beautiful continent there are $100\,000$ countries, numbered from $1$ to $100\,000$. The economy is prosperous, there are countless accounting offices, and each country has one bank.

When a big company's leader opened accounts in these $100\,000$ banks, he deposited $3$ coins in each. He is very stingy, so he will from time to time send his lackey GFS to tally deposits in some banks or ask GFS to change the deposit of a certain bank.

In this land, the summation operation on wealth corresponds to our multiplication. That is, the total deposit when the leader opened accounts is $3^{100000}$. The banknote denominations issued here are the smallest $60$ primes ($p_1=2, p_2=3, \ldots, p_{60}=281$). Anyone’s wealth can only be represented using these $60$ basic denominations. Suppose a person’s wealth is $fortune$ (a positive integer), then $fortune = p_1^{k_1} \times p_2^{k_2} \times \ldots p_{60}^{k_{60}}$.

The leader tends to take deposits from a consecutive range of banks to one accounting office to tally. To avoid GFS colluding with an accounting office, he will not choose the same accounting office every time. After following the leader for many years, GFS has figured out the rule: if the leader chooses to tally the wealth of banks numbered in $[a,b]$, he will first “sum” (i.e., multiply) the wealth over $[a,b]$ (denoted as $product$), and then pick an accounting office whose number is in $[1, product]$ to tally the deposits, both to verify his own computation and to check whether the accounting office and GFS are colluding. GFS noticed that if an accounting office’s number $number$ is in conflict with $product$, the leader will never choose that office.

What does it mean to be not in conflict with $product$? If there exist integers $x, y$ such that $number \times x + product \times y = 1$, then we say $number$ is not in conflict with $product$, i.e., that accounting office may be chosen by the leader. When the leader makes a lot more money, he will change the deposit in some bank; thus the $product$ computed for the same interval at different times may differ. Moreover, the leader will not let the deposit in any single bank exceed $10^6$.

Now that GFS knows in advance the leader’s plan for tallying and changing deposits, he wants you to tell him, for each tally, how many accounting offices the leader can choose from. Since this number can be very large, GFS only wants the answer modulo $19\,961\,993$.

Input Format

The first line contains an integer $x$ denoting the total number of tally and update operations.

Then follow $x$ lines, each with $3$ integers $a_i, b_i, c_i$. If $a_i = 0$, this record is a tally plan: the leader will tally deposits of banks from $b_i$ to $c_i$, and you need to compute the answer GFS wants for this record. If $a_i = 1$, this record is an update: you should change the deposit of bank $b_i$ to $c_i$, and you do not need to output anything for this record.

Output Format

For each query, output a single integer per line denoting the answer.

6
0 1 3
1 1 5
0 1 3
1 1 7
0 1 3
0 2 3

18
24
36
6

Hint

Sample Explanation

• Initially, each country’s deposit is $3$.
• The $product$ for $1$ to $3$ is $27$. In $[1,27]$, there are $18$ numbers not in conflict with $27$.
• The deposit of $1$ becomes $5$.
• The $product$ for $1$ to $3$ is $45$. In $[1,45]$, there are $24$ numbers not in conflict with $45$.
• The deposit of $1$ becomes $7$.
• The $product$ for $1$ to $3$ is $63$. In $[1,63]$, there are $36$ numbers not in conflict with $63$.
• The $product$ for $2$ to $3$ is $9$. In $[1,9]$, there are $6$ numbers not in conflict with $9$.

Constraints

All testdata satisfy: $x \geq 1$, $c_i - b_i \geq 0$.

Special property means: all $product \leq 10^{18}$.

Translated by ChatGPT 5