{"raw_statement":[{"iden":"background","content":"译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D1T1。$\\texttt{2s,1G}$。\n\n> Two pharaonic yellow lines turned into an eye..."},{"iden":"statement","content":"Jusuf 手里有 $N$ 张卡牌，从左到右编号为 $1$ 到 $N$。每张卡牌的力量为 $p_i$。由于 Jusuf 即将参加比赛，他想要在脑中想象战斗。有时候，他也会更改卡牌的力量值。Jusuf 总共会做 $Q$ 次操作，每个操作属于以下两种类型之一：\n\n1. `1 i r`：Jusuf 将位于位置 $i$ 的卡牌的力量设为 $r$，即 $p_i\\gets r$。\n\n2. `2 l k`：Jusuf 在脑中想象一场战斗。这场战斗使用从第 $l,l+1,\\cdots,l + 2^k − 1$ 张，共 $2^k$ 张卡牌。\n\n    战斗将会进行 $k$ 轮。每轮中，Jusuf 将第 $(2i-1)$ 和第 $2i$ 张卡牌分成一组（例如第 $1$ 张和第 $2$ 张卡牌为一组）。\n    \n    对于每组卡牌，Jusuf 比较它们的力量。不妨设两张卡牌的力量分别为 $A$ 和 $B$，力量更大的卡牌将获胜，且获胜卡牌的力量变为 $|A − B|$，另一张卡牌被移除。特别地，如果 $A=B$，则这场战斗的结果无法确定，将会随机一张卡牌获胜，力量变为 $0$。\n    \n    注意到，在 $k$ 轮后，只会剩下一张卡牌，Jusuf 想要知道此时它的力量大小。\n\n由于 Jusuf 只是在脑中想象战斗，所以实际上牌的数量不会改变，$p_i$ 也不会改变。\n"},{"iden":"input","content":"第一行，两个正整数 $N,Q$，含义见题面。\n\n第二行，$n$ 个整数，第 $i$ 个整数表示 $p_i$。\n\n接下来 $Q$ 行，每行 $3$ 个正整数，描述一个操作。"},{"iden":"output","content":"对于每个操作 $2$，输出一行一个整数，表示所求的力量大小。"},{"iden":"note","content":"\n#### 样例解释\n\n对于样例 $1$ 的第一个询问，有：\n\n$$(\\bold{\\textcolor{red}{4}},8,\\bold{\\textcolor{red}{2}},0)\\to (\\bold{\\textcolor{red}{4}},2)\\to(2)$$\n\n对于样例 $1$ 的第二个询问，有：\n\n$$ (\\bold{\\textcolor{red}{8}},2)\\to(6)$$\n\n#### 数据范围\n\n对于 $100\\%$ 的数据，保证：\n\n- $2\\le N\\le 200\\, 000$，$1\\le Q\\le 200\\, 000$；\n- $0\\le p_i\\le 10^9$；\n- $1\\le i\\le N$，$0\\le r\\le 10^9$；\n- $1\\le l\\le N$，$1\\le l+{2^k}-1\\le N$。\n\n| 子任务编号 | 分值 | 约束  |\n|:-----:|:------:|:-------:|\n| $1$   | $11$    | $N, Q \\leq 1000$ |\n| $2$    | $13$    | $N=2^k$ |\n| $3$    | $16$    | $0\\le p_i,r\\le 1$ |\n| $4$    | $17$    | 不含修改操作 |\n| $5$    | $43$    | 无额外约束 |\n\n"}],"translated_statement":null,"sample_group":[["5 3\n4 8 2 0 7\n2 1 2\n1 1 9\n2 2 1","2\n6"],["8 6\n1 2 3 4 5 6 7 8\n2 1 3\n1 4 1\n1 7 3\n2 1 3\n1 2 100\n2 2 2","0\n3\n93"],["9 5\n1 0 2 0 4 1 3 2 8\n2 2 3\n2 1 3\n1 5 1\n1 6 4\n2 4 2","2\n1\n0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}