Wenwen News Revenue Maximization

In the new issue of Wenwen.News, n youkai (monsters) line up and each is assigned an index from \(1\) to \(n\). Each youkai intends not to read the magazine but to gift copies of the magazine to all youkai whose indices are multiples of their own index (including possibly themselves). 

The process is performed in order from \(1\) to \(n\): For each youkai \(i\), let \(f=\lfloor n/i\rfloor\) be the total number of copies that need to be distributed (one to each multiple of \(i\)). Each youkai may already have some copies in hand (received from earlier distributions from its divisors; note that for \(i\), the number of copies in hand is \(d(i)-1\) where \(d(i)\) denotes the number of divisors of \(i\), because all divisors less than \(i\) have already made their distributions). If the number of copies \(h\) in hand is less than \(f\), then the youkai purchases exactly \(f-h\) copies. However, the cost of each copy is not constant. The cost for the \((j+1)\)th copy bought by the \(i\)th youkai is given by the formula

[ \text{cost} = a_i \times b_{j+1}, \quad j \geq h \ (0\leq j<f-h) ]

where the pricing arrays \(a = [a_1, a_2, \ldots, a_{10^6+1}]\) and \(b = [b_1, b_2, \ldots, b_{10^6+1}]\) are given (both are initially all ones).

Thus, the cost incurred by the \(i\)th youkai is

[ \text{Cost}i = \begin{cases} a_i \times \displaystyle\sum{j=d(i)}^{\lfloor n/i \rfloor} b_j, & \text{if } d(i) \leq \lfloor n/i \rfloor,\[1mm] 0, & \text{otherwise.} \end{cases} ]

The total revenue earned is the sum of the costs from all youkai \(i=1\) to \(n\). Since the answer might be large, output it modulo \(2^{32}\) (which is 4294967296).

Along with queries asking for the revenue under a current pricing scheme and size \(n\), there are two types of update operations:

• 2 x y: update the pricing array \(a\) so that \(a_x = y\).
• 3 x y: update the pricing array \(b\) so that \(b_x = y\).

An operation of type 1 x asks: With the current arrays \(a\) and \(b\) and \(n=x\), how much revenue is earned (modulo \(2^{32}\))?

Input/Output details: You will be given an integer \(Q\) denoting the number of operations. Then \(Q\) lines follow; each line describes an operation in one of the forms:

• 1 x: query revenue for \(n=x\).
• 2 x y: update \(a_x = y\).
• 3 x y: update \(b_x = y\).

For every query operation (type 1), output the revenue (modulo \(2^{32}\)).

inputFormat

The first line contains an integer \(Q\), the number of operations.

Each of the next \(Q\) lines contains an operation in one of the following formats:

• 1 x : Query for revenue when \(n = x\).
• 2 x y : Update the array \(a\) such that \(a_x = y\).
• 3 x y : Update the array \(b\) such that \(b_x = y\).

outputFormat

For each operation of type 1, output a single line containing the revenue modulo \(2^{32}\) (i.e. modulo 4294967296).

sample

3
1 6
2 1 2
1 6

9
15

</p>