有 $N$ 张牌排成一排。每张牌都有红色的正面和蓝色的背面。第 $i$ 张牌的红色面写有一个整数 $R_i$，蓝色面写有一个整数 $B_i$。初始时，每张牌要么红色朝上，要么蓝色朝上。

对区间 $[l, r]$ 的一次操作定义如下：

• 对于每个满足 $l \le i \le r$ 的 $i$，令 $c_i$ 为满足 $l \le j < i$ 且在当前操作开始时第 $j$ 张牌与第 $i$ 张牌朝上颜色相同的下标 $j$ 的数量。
• 操作后，如果 $c_i$ 为偶数，则第 $i$ 张牌红色朝上；如果 $c_i$ 为奇数，则蓝色朝上。
• 区间 $[l, r]$ 中的所有牌同时更新。

你需要处理以下 $Q$ 次询问：

• 1 i — 翻转第 $i$ 张牌。
• 2 i k — 将第 $i$ 张牌红色面的值修改为 $k$。
• 3 i k — 将第 $i$ 张牌蓝色面的值修改为 $k$。
• 4 l r T — 计算对区间 $[l, r]$ 进行 $T$ 次操作后，该区间内所有牌朝上面数字的和。此询问不会改变牌的实际状态。

输入格式

第一行包含一个整数 $N$，表示牌的数量。

第二行包含一个长度为 $N$ 的字符串 $s$，由字符 R 和 B 组成。$s$ 的第 $i$ 个字符表示第 $i$ 张牌的初始朝向（R 表示红色朝上，B 表示蓝色朝上）。

第三行包含 $N$ 个整数 $R_1, R_2, \dots, R_N$，表示每张牌红色面的值。

第四行包含 $N$ 个整数 $B_1, B_2, \dots, B_N$，表示每张牌蓝色面的值。

第五行包含一个整数 $Q$，表示询问次数。

接下来的 $Q$ 行，每行描述一个如上所述的四种类型之一的询问。

输出格式

对于每个类型 4 的询问，输出一个整数，表示指定区间的计算和。

数据范围

• $1 \le N, Q \le 2 \cdot 10^5$
• $1 \le R_i, B_i \le 10^9$
• 对于类型 1 的询问：$1 \le i \le N$
• 对于类型 2 或 3 的询问：$1 \le i \le N, 1 \le k \le 10^9$
• 对于类型 4 的询问：$1 \le l \le r \le N, 1 \le T \le 10^9$
• 保证至少存在一个类型 4 的询问。

样例

输入样例 1

5
RRRRR
1 2 3 2 1
5 4 3 4 5
4
4 1 5 1
4 1 5 2
1 2
4 1 4 1

输出样例 1

13
11
8

输入样例 2

8
RBRBRBRB
451 79 882 122 1289 242 2459 262
697 1082 1888 3070 225 410 751 1089
11
1 5
4 1 6 10121
1 3
2 6 803
3 3 741
4 2 7 11104
1 5
3 8 690
2 5 137
3 6 148
4 3 8 20915

输出样例 2

7187
5810
6333