背景

:::info[题目背景]

芙莉莲站在「沉星书库」前，轻轻翻开了那本厚重而古老的 「时间之书」。书页间没有寻常文字，只有一层层如星轨般缓缓流转的术式纹路，仿佛整条时间本身，正安静地沉睡在其中。她抬起手，指尖的魔力一点点没入书页，淡金色的光随之扩散开来，将菲伦与休塔尔克也一并笼罩进去。

下一刻，四周的一切都开始变得模糊。

风停住了，尘土停住了，远处倾塌的废墟与黯淡的天空，也像被投入水中的倒影一般，缓缓荡漾、扭曲。无数细碎的光点从书页间浮起，沿着他们的脚边与衣角盘旋而上，仿佛正在将某段已经偏离的历史，一寸寸重新拨回原本的位置。

「抓紧我。」芙莉莲轻声说道。

题目描述

「时间之书」的术式是一个巨大的，不断变化的等边三角形。为了方便，可以建立笛卡尔坐标系，则在坐标系中的等边三角形顶点坐标分别为 $(-1, 0), (1, 0), (0, \sqrt{3})$，初始时，该三角形的术式编号为 $1$，且每个顶点的时间权重均为 $1$。

「时间之书」的术式需要进行 $q$ 次操作才能正常发动，每次操作形如：

• query i 代表查询术式编号为 $i$ 的三角形三个顶点的时间权重和，芙莉莲需要向其中输送恰好为权重和的魔力才能正确激活术式；
• update i y 代表将术式编号为 $i$ 的三角形的三个顶点的时间权重都改为 $y$；
• extend i 代表将术式编号为 $i$ 的三角形扩展为四个子三角形，具体地，我们定义：
  • $AB$ 为术式编号为 $i$ 的三角形与 $x$ 轴平行的一条边，且 $A$ 的横坐标小于 $B$ 的横坐标；
  • $C$ 为术式编号为 $i$ 的三角形的第三个顶点，若 $C$ 的纵坐标大于 $A$ 与 $B$ 的纵坐标，则三角形 $i$ 为正三角形，否则为倒三角形；
  • 设 $AB$ 的中点为 $D$，$AC$ 的中点为 $E$，$BC$ 的中点为 $F$，则对于正三角形而言，扩展出的四个子三角形分别是 $\triangle ADE, \triangle DBF, \triangle DEF, \triangle CEF$，它们的术式编号分别为 $4i, 4i+1, 4i+2, 4i+3$；对于倒三角形而言，扩展出的四个子三角形分别是 $\triangle DBF, \triangle ADE, \triangle DEF, \triangle CEF$，它们的术式编号分别为 $4i, 4i+1, 4i+2, 4i+3$；
  • 扩展后，若子三角形的顶点已有时间权重，则权重不变，否则权重为 $1$；
  • 保证扩展后的子三角形的术式编号小于 $10^9$。

下图代表了扩展操作的效果，结合下图与样例输入，你可以更直观地理解到扩展操作的详细过程。对于每次 query i 操作，芙莉莲需要知道术式编号为 $i$ 的三角形三个顶点的时间权重和。

输入格式

输入第一行包含一个整数 $q(1\leq q\leq 10^5)$，表示「时间之书」的术式变换次数。

以下 $q$ 行，每行代表一个操作：

• query i 代表查询术式编号为 $i$ 的三角形三个顶点的时间权重和；
• update i y 代表将术式编号为 $i$ 的三角形的三个顶点的时间权重都改为 $y(1\leq y\leq 10^9)$；
• extend i 代表将术式编号为 $i$ 的三角形扩展为四个子三角形，定义如上。

输入保证所有操作的术式编号均是合法且存在的三角形术式编号。

输出格式

输出若干行，每行一个整数，代表每次 query 操作的结果。

15
query 1
update 1 2
query 1
extend 1
query 6
query 7
update 7 3
query 4
query 1
extend 6
extend 5
update 27 4
query 26
query 22
query 6

3
6
3
4
6
7
9
6
10

提示

:::info[题目背景]

随着最后一道术式纹路完整闭合，「时间之书」上的光辉终于不再向外扩散，而是像归巢的潮汐一般，安静地向着更深处缓缓回流。那一瞬间，偏离的时间线被重新校正，世界仿佛在无人察觉的地方，轻轻呼出了一口漫长的叹息。

紧接着，「沉星书库」中的一切都开始逆着记忆复原。

前庭深处，那些原本沉寂的黑色「列星衡仪」重新解封，沉稳而幽暗的光沿着底部的术式纹路缓缓亮起；曾被击倒的镇守魔物，也在古老魔力的回响中再度苏醒，静静回到了它本该守望的位置。被大战撕裂的大厅一点点恢复如初，倒塌的石柱重新立起，崩裂的地面重新弥合，四散的书页与灰尘安静落回原处。只是，那些无法彻底抹去的风霜与裂痕，仍旧留在石壁与阶梯之间，像是千年岁月从未真正离开过这里。

更远处，曾被破解的「星界碑针」也重新恢复了明暗交替的闪烁，仿佛群星在久远的夜空中一呼一应；而那些被毁坏的「拱辰封仪」，亦在无声之中重新拼合、复原，再一次将「沉星书库」守护在森林中央，不允许任何人轻易抵达它真正的核心。

当最后一点光也沉入时光深处时，芙莉莲一行人已经重新站在了那片熟悉的森林之中。

风穿过高大的树梢，带来潮湿而清新的草木气息。晨雾仍旧缓慢地缠绕在林间，像什么都没有发生过一样。菲伦怔了怔，低头看向背包，里面的聚魔石依旧安静地躺着，内部封存的魔力完整而温暖，没有被消耗哪怕一丝一毫。仿佛先前那场漫长而艰难的旅途，那些苦战、那些机关、那些一度触碰到千年以前的谜题，都只是从时间的缝隙间短暂映出来的一场幻梦。

可他们都知道，那不是梦。

因为芙莉莲的怀中，已经没有「时间之书」了。

那本承载着无数可能性的古老典籍，终究回到了它本该停留的地方。它不再是可以被谁带走的书，而是重新化作那团浓重而沉静的古代魔法，静静悬浮在「沉星书库」最深处的王座中央，等待着下一位能够抵达此处的探险者，去与千年之前的大图书管理员对话。也许，对那位守望了太久的古人而言，真正重要的，从来都不只是某一种术式，或者某一本珍贵的典籍；而是让后来者有机会见证千年的历史更迭，窥见不同人生在时光中的聚散离合，明白魔法、文明与记忆究竟为何被传承下来。

或许，这才是「沉星书库」真正的意义。

林间安静了片刻。随后，休塔尔克长长地松了一口气；菲伦也轻轻笑了起来，像终于把某种沉重而正确的选择，好好放回了心里。芙莉莲抬头望向树隙间落下的天光，银白色的发梢被风轻轻吹起，神情依旧平静，却也比平时多出了一点极淡的柔和。

「如果是勇者辛美尔的话……或许也会做出这样的选择吧。」