#1514. 报社天狗

报社天狗

题目描述

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

nn 只†^\dag妖怪排队购买《文文。新闻》,将她们依次编号 1∼n1\sim n,每一只妖怪会购买若干份。然而,她们购买《文文。新闻》并不是为了阅读,而是是为了送给所有编号是自己倍数的的妖怪一份(自己可以不留)。也就是说,对于 1∼n1\sim n 的每只妖怪,依次进行:当手上的《文文。新闻》数量足够时,不进行购买,直接赠送;而不够时便会先向文文购买至刚好足够,再进行赠送。

文文为了使收益最大化,为每只妖怪详细制定了价格方案。具体地,第 ii 只妖怪在已有 jj 份《文文。新闻》时再买一份花费的价钱是 ai×bj+1a_i\times b_{j+1},其中 a,ba,b 是两个从 11 开始的长为 106+110^6+1 的正整数序列。

现在文文需要一个合理的定价方案,她决定从 a,ba,b 全为 11 时开始调整。具体地,有以下三种操作:

  • 1 x 询问以当前的 a,ba,b 数组,n=xn=x 时文文能有多少营业额,因为结果可能很大,你需要求出答案对 2322^{32} 取模后的结果。
  • 2 x y 适当地调整 aa 数组的值:令 ax=ya_x=y;
  • 3 x y 适当地调整 bb 数组的值:令 bx=yb_x=y。

†\dag:经查证,量词为『只』和『个』的情况均有出现,THBwiki 中『一只妖怪』的匹配量显著多于『一个妖怪』,于是本题中采用『只』,并不是出题人的种族歧视。

输入格式

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

第 2∼T+12\sim T+1 行,每行 22 或 33 个整数,表示题目中的一次操作。

输出格式

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

样例

5
1 5
2 2 5
3 1 3
1 5
1 6
4
6
12

题目来源:洛谷 P11772