A + B

Time limit8sMemory limit512 MB

Summary

Given binary numbers A and B, answer the maximum popcount of x in [A, A+B) after bit flips to A or B.

Level: Hard8 of 10
Topics: Bit manipulation, Segment tree
Solved: No attempts yet

Problem

Given binary numbers $A$ and $B$ , process the following queries.

Output query: print $\max\{\text{the number of 1 bits in } x \mid A \leq x < A+B\}$ , where $x$ is written in binary.
A change query: flip bit $i$ of $A$ , counting from the least significant bit as bit 0.
B change query: flip bit $i$ of $B$ , counting from the least significant bit as bit 0.

Bit indices are 0-origin. Bit 0 of $A$ is the least significant bit.

Input

The input is given in the following format.

$N$ $A$ $B$ $Q_1$ ... $Q_N$

The first line contains the number of queries $N$ , and the binary numbers $A$ and $B$ . Lines 2 to $N+1$ contain the queries. $Q$ is an output query. "A $i$ " and "B $i$ " are change queries that flip bit $i$ of $A$ and bit $i$ of $B$ , counting from the least significant bit.

Output

For each output query, print the answer on its own line.

Constraints

$1 \leq N < 300000$
$1 \leq |A|, |B| \leq 300000$ , where $|A|$ is the length of $A$
For a query "A $i$ ", $0 \leq i < |A|$
For a query "B $i$ ", $0 \leq i < |B|$
$B$ is never 0

Examples2

Example 1
Input
```
4 10000 00101
Q
A 0
B 1
Q
```
Expected output
```
3
4
```

Example 2

Input

9 0110111101 0010100111
Q
B 4
Q
A 4
Q
B 9
Q
A 8
Q

Expected output