题目背景

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

题目描述

新一期《文文。新闻》开售了！

$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 中『一只妖怪』的匹配量显著多于『一个妖怪』，于是本题中采用『只』，并不是出题人的种族歧视。

输入格式

第一行一个整数 $T$ 表示操作的数量。

第 $2\sim T+1$ 行，每行 $2$ 或 $3$ 个整数，表示题目中的一次操作。

输出格式

每行一个整数，表示每次询问的获利对 $2^{32}$ 取模后的结果。

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

4
6
12

提示

样例解释

第一个询问中，$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$。

对于不同的子任务，作如下约定：