SP15074 TOURNEY - Tourney

Don Cherry 被聘请来负责一系列家具拆卸锦标赛的全程报道。这些比赛是单败淘汰制的分组赛，每位参赛者的家具拆卸技能等级是一个在 $1$ 到 $10^9$ 之间的整数。在每场对决中，技能等级较高的参赛者获胜并晋级，而失败者则被淘汰。可以保证，任何时候所有参赛者的技能等级都各不相同，因此不会出现平局。 锦标赛使用一棵参赛图，共有 $2^N$ 个位置（$1 \leq N \leq 20$），从左到右编号为 $1, 2, \ldots, 2^N$。在首轮比赛中，参赛者1与2对决，3与4对决，以此类推。在后面的每轮比赛中，上轮比赛的胜者一一对决，最终经过 $N$ 轮比赛，决出最终的冠军。例如，当 $N=2$ 时，比赛结构如下：  其中，A 是参赛者 1 和 2 中的胜者，B 是参赛者 3 和 4 中的胜者，而 C 则是 A 和 B 中的胜者。C 是本场比赛的最终赢家。 由于赞助合同的原因，部分参赛者可能会被替换。每当有新参赛者加入时，需要重新进行比赛。 为了协助 Don Cherry，你需要编写一个程序，来计算每个时间节点上的比赛情况，给定如下 $M$ 条指令（$1 \leq M \leq 10^6$）。

第一行包含两个整数 $N$ 和 $M$。 接下来的 $2^N$ 行，每行包含一个整数 $S_i$，表示在比赛开始时，参赛者在位置 $i$ 的技能等级。 接下来的 $M$ 行，每行包含以下三种格式之一的指令： - “**R** $i$ $s$” 表示位置 $i$ 的参赛者被替换成一个新参赛者，其技能等级为 $s$。随后需要重新进行比赛。 - “**W**” 指令要求输出当前比赛的优胜者位置 $i$，这个位置在 $1$ 到 $2^N$ 之间。 - “**S** $i$” 要求输出当前比赛中位置 $i$ 的参赛者赢得的轮数。

对于每个“**W**”或“**S** $i$”指令，单独输出相应的结果。 **本翻译由 AI 自动生成**