P11772 报社天狗

因为天依想不到新歌歌词怎么写破防了，所以这题的主人公不是天依。

新一期《文文。新闻》开售了！ $n$ 只$^\dag$妖怪排队购买《文文。新闻》，将她们依次编号 $1\sim n$，每一只妖怪会购买若干份。然而，她们购买《文文。新闻》并不是为了阅读，而是是为了送给所有编号是自己倍数的的妖怪一份（自己可以不留）。也就是说，对于 $1\sim n$ 的每只妖怪，依次进行：当手上的《文文。新闻》数量足够时，不进行购买，直接赠送；而不够时便会先向文文购买至刚好足够，再进行赠送。 文文为了使收益最大化，为每只妖怪详细制定了价格方案。具体地，第 $i$ 只妖怪在已有 $j$ 份《文文。新闻》时再买一份花费的价钱是 $a_i\times b_{j+1}$，其中 $a,b$ 是两个从 $1$ 开始的长为 $10^6+1$ 的正整数序列。 现在文文需要一个合理的定价方案，她决定从 $a,b$ 全为 $1$ 时开始调整。具体地，有以下三种操作： - `1 x` 询问以当前的 $a,b$ 数组，$n=x$ 时文文能有多少营业额，因为结果可能很大，你需要求出答案对 $2^{32}$ 取模后的结果。 - `2 x y` 适当地调整 $a$ 数组的值：令 $a_x=y$； - `3 x y` 适当地调整 $b$ 数组的值：令 $b_x=y$。 $\dag$：经查证，量词为『只』和『个』的情况均有出现，THBwiki 中『一只妖怪』的匹配量显著多于『一个妖怪』，于是本题中采用『只』，并不是出题人的种族歧视。

无

无

### 样例解释 第一个询问中，$n=5$，两个序列中所有的元素均为 $1$。$1$ 号妖怪买了 $4$ 份报纸，每份报纸的收益都是 $1$，其他的妖怪都没有买报纸，总收益为 $4$。 第二个询问中，有 $n=5,a_2=3,b_1=5$，序列中其他元素均为 $1$。$1$ 号妖怪买了 $4$ 份报纸，其中第 $1$ 份报纸的收益是 $3$，第 $2$ 份到第 $4$ 份报纸的收益都是 $1$，其他的妖怪都没有买报纸，总收益为 $6$。 第三个询问中，有 $n=6,a_2=3,b_1=5$，序列中其他元素均为 $1$。让我们具体来看看这次询问中的过程： + $1$ 号妖怪需要送其他每个妖怪各一份报纸，但是她没有报纸。于是她需要买 $5$ 份报纸。其中第一份报纸的收益是 $a_1\times b_1=3$，第 $2$ 份到第 $5$ 份报纸的收益都是 $1$。然后她给了其他每个妖怪各一份报纸。 + $2$ 号妖怪需要送 $4$ 号妖怪和 $6$ 号妖怪各一份报纸，她已经从 $1$ 号妖怪手中获得了一份报纸。于是她还需要买 $1$ 份报纸，这份报纸的收益是 $a_2\times b_2=5$。 + $3$ 号妖怪需要送 $6$ 号妖怪一份报纸，她已经从 $1$ 号妖怪手中获得了一份报纸，不需要再买报纸。 + $4$ 号妖怪到 $6$ 号妖怪都不需要送出报纸，也不需要再买报纸。 总收益为 $12$。 ### 数据规模与约定 **本题采用捆绑测试。** 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。 对于 $100\%$ 的数据，$1 \leq T \leq 10^5$，$1 \leq x,n\leq 10^6$，$1\le y\le 10^9$。 对于不同的子任务，作如下约定： | 子任务编号 | 特殊性质 | 子任务分值 | | :-----: | :----------------------------------: | :----: | | $1$ | 没有修改操作 | $10$ | | $2$ | 第一种操作中的每个 $n$ 都相等 | $20$ | | $3$ | $n,T \leq 10^5$ | $30$ | | $4$ | 无 | $40$ |