有一天,Ikta 无法想出一个在编程竞赛训练营中提出问题的想法,因此他咨询了一位朋友。
Ikta-kun:“我想问一个不使用这种算法就无法解决的问题。你有什么想法吗?”
朋友:“那为什么不考虑这样的事情呢?”
就这样,朋友想出了一个想法,成为下面问题的基础。 给定
2進数A,B,处理以下查询。
输出查询:max{x 用二进制表示时1的个数 | 输出 A \leq x < A+B }
更改查询: 从 A的最低有效位开始i反转位(0-原点)
B变更查询: B的最低有效位开始i反转位(0-原点)
i请注意,第 th 位以 0 为起点表示。 换句话说,A从最低有效位开始的第 0 位表示最低有效位。
输入
输入按以下格式给出。
N A B
Q1
...
QN
第一行给出了查询数N和二进制数A和B。
以下查询在第 2 行到第 N+1 行中给出。
Q
A i
B i
Q 输出查询,A i,B i分别是A的最低有效位开始i位,B的最低有效位开始i表示反转位的更改查询。
约束
输入中的每个变量都满足以下约束。
1 \leq N < 300,000
1 \leq |A|,|B| \leq 300,000 (|A|是A长度) 在查询
A i 中 0 \leq i < |A|
B i 中 0 \leq i < |B|
B永远不会是 0
输出
将每个输出查询的答案打印在一行上。
样本输入 1
4 10000 00101 Q A 0 B 1 Q
样本输入 1 的输出
3 4
在第一个输出查询中 A=10000, B=00101, A+B=10101因此,找到x是 10011
在以下输出查询中 A=10001, B=00111, A+B=11000因此,找到x是 10111
示例输入 2
9 0110111101 0010100111 Q B 4 Q A 4 Q B 9 Q A 8 Q
样本输入 2 的输出
9 9 9 10 9