Don't Fight The Music

문제

There are $N$ cards in a row. Each card has a red front side and a blue back side. An integer $R_i$ is written on the red side of the $i$-th card, and an integer $B_i$ is written on the blue side. Initially, every card is facing either red side up or blue side up.

An operation on a range $[l, r]$ is defined as follows:

For each $i$ from $l$ to $r$, let $c_i$ be the number of indices $j$ with $l \le j < i$ such that card $j$ shows the same color as card $i$ at the beginning of the current operation.
After the operation, card $i$ shows its red side if $c_i$ is even, and its blue side if $c_i$ is odd.
All cards in $[l, r]$ are updated simultaneously.

You need to process the following $Q$ queries:

1 i — Flip the $i$-th card.
2 i k — Change the value on the red side of the $i$-th card to $k$.
3 i k — Change the value on the blue side of the $i$-th card to $k$.
4 l r T — Calculate the sum of the numbers on the face-up sides in the range $[l, r]$, when the operation has been applied to this range $T$ times. The state of the cards does not change as a result of this query.

입력

The first line contains a single integer $N$, the number of cards.

The second line contains a string $s$ of length $N$, consisting of characters R and B. The $i$-th character of $s$ denotes the initial side of the $i$-th card (R for red side up, B for blue side up).

The third line contains $N$ integers $R_1, R_2, \cdots, R_N$ — the values on the red sides of the cards.

The fourth line contains $N$ integers $B_1, B_2, \cdots, B_N$ — the values on the blue sides of the cards.

The fifth line contains a single integer $Q$, the number of queries.

Each of the next $Q$ lines describes a query of one of the four types as described above.

출력

For each query of type $4$, output a single integer, the calculated sum for the specified range.

제한

$1 \le N, Q \le 2\cdot 10^5$
$1 \le R_i, B_i \le 10^9$
For a query of type $1$: $1 \le i \le N$
For a query of type $2$ or $3$: $1 \le i \le N$, $1 \le k \le 10^9$
For a query of type $4$: $1 \le l \le r \le N$, $1 \le T \le 10^9$
It is guaranteed that there is at least one query of type 4.