Description

New issue of Bunbunmaru Newspaper is on sale!

$n$ youkais numbered $1$ to $n$ waits in a line buying the newspaper. Each of them may buy multiple pieces, one single piece or none, depending on their goal — Instead of buying to read, they buy the newspaper to share. One will give a piece of newspaper to everyone whose ID is a multiple of her own ID, even without leaving herself one piece. Youkais numbered $1$ to $n$ will follow this process in sequence: If the number of newspaper pieces she have is sufficient, she will proceed directly to the giveaway. If not, she will purchase the exact number of newspapers needed before completing the giveaway.

To maximize her profit, Syameimaru Aya, the writer of Bunbunmaru Newspaper, is planning to make a pricing scheme. The scheme is described by two 1-indexed arrays of positive integers $a,b$, which have a length of $10^6+1$ each. When a youkai with ID $i$ holding $j$ pieces of newspaper buy one another piece of newspaper, she should pay $a_i\times b_{j+1}$ yen.

Now Aya needs a fair pricing scheme. She chose to begin adjusting the sequences starting when all elements in $a$ and $b$ are initialized to $1$. And then there's three types of $T$ operations:

• 1 x Aya asks you how much revenue she can make in the current state of sequences $a$ and $b$. Since the answer could be too large, you should output the answer $\bmod~ 2^{32}$.

• 2 x y Aya changes the $x$-th element of array $a$ to $y$.

• 3 x y Aya changes the $x$-th element of array $b$ to $y$.

Can you answer all of her questions?

Input Format

The first line of input contains an integer $T$ — the amount of operations.

The following $T$ rows each contain $2$ or $3$ integers, representing an operation as described in the problem.

Output Format

For each operation of the first type, print the answer, modulo 2^{32.

5
1 5
2 2 5
3 1 3
1 5
1 6

4
6
12

Hint

Sample Explanation

In the first question, $n=5$, all the elements in two arrays equal to $1$. the youkai with ID $1$ need to buy $4$ pieces of newspaper and cost $1$ yen for each piece. Other youkais don't need to buy any newspaper. the revenue in total will be $4$ yen.

In the second question, $n=5,a_2=5,b_1=3$, other elements in two arrays equal to $1$. the youkai with ID $1$ need to buy $4$ pieces of newspaper and cost $3$ yen for the first piece, $1$ yen for the other pieces. Other youkais don't need to buy any newspaper. the revenue in total will be $6$ yen.

In the third question, $n=6,a_2=5,b_1=3$, other elements in two arrays equal to $1$. Let's check out the details in this question:

• The youkai with ID $1$ needs to give other youkais one pieces of newspaper each, but she has none, so she needs to buy $5$ pieces of newspaper. the first piece costs $a_1\times b_1=3$ yen and the others cost $1$ yen each.

• The youkai with ID $2$ needs to give youkais with ID $4$ or $6$ one pieces of newspaper each. She has got a piece from the youkai with ID $1$, so she needs to buy $1$ piece of newspaper which costs $a_2\times b_1=5$ yen.

• The youkai with ID $3$ needs to give youkai with ID $6$ one piece of newspaper, she has got a piece from the youkai with ID $1$, so she doesn't need to buy newspaper.

• the youkais with ID $4,5,6$ don't need to give out newspaper, so they doesn't need to buy newspaper.

the revenue in total will be $12$ yen.

Constraints

Subtasks applied. You can only gain the score of the subtask if you accepted all the tests in the subtask.

For all tests, it is guaranteed that $1 \leq T \leq 10^6$，$1 \leq x,n\leq 10^5$.