你要举办一场饼干派对！你准备了 $N$ 块饼干，编号为 $1$ 到 $N$。第 $i$ 块饼干的甜度为 $A_i$。预计将有 $M$ 位编号为 $1$ 到 $M$ 的儿童参加派对。他们每人都会带来一块自制的饼干，其中第 $i$ 位儿童带来的饼干甜度为 $B_i$。此外，你知道每位儿童的口味偏好：如果 $S_i = \text{'S'}$，则该儿童喜欢甜饼干；如果 $S_i = \text{'B'}$，则该儿童喜欢苦饼干。

派对将按以下方式进行：

• 首先，给定一个整数 $k$，你将编号为 $1, 2, \dots, k$ 的饼干放在桌子上。
• 然后，儿童 $1, 2, \dots, M$ 按此顺序来到桌前。当第 $i$ 位儿童来到桌前时，他/她首先将自己带来的饼干放在桌上。接着，如果该儿童喜欢甜饼干，他/她会吃掉桌上最甜的饼干（甜度最大的饼干）；如果该儿童喜欢苦饼干，他/她会吃掉桌上最苦的饼干（甜度最小的饼干）。注意，每位儿童恰好吃掉一块饼干，且儿童可能会吃掉自己带来的那块饼干。
• 最后，你吃掉桌上剩下的所有饼干。

你尚未决定 $k$ 的值。对于每个整数 $k = 1, 2, \dots, N$，求出你吃掉的饼干的甜度之和。

注意：只有在得到 $k = i$ 的答案后，你才能知道 $A_{i+1}$ 的值。详见输入格式部分。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A'_1 \ A'_2 \ \dots \ A'_N$ $M$ $B_1 \ B_2 \ \dots \ B_M$ $S$

其中 $A'_i$ 是 $A_i$ 的加密值，真实值可以通过 $A_i = (A'_i + \text{lastans} \pmod{10^9})$ 计算得出，其中 $\text{lastans}$ 表示 $k = i - 1$ 时的答案（若 $i > 1$），当 $i = 1$ 时 $\text{lastans} = 0$。

数据范围：

• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le 10^9 - 1$
• $0 \le A'_i \le 10^9 - 1$（定义见输入格式）
• $1 \le M \le 2 \times 10^5$
• $0 \le B_i \le 10^9 - 1$
• $|S| = M$
• $S_i$ 为 'S' 或 'B'。
• 输入中的所有值均为整数。

输出格式

在一行中输出 $N$ 个整数。第 $i$ 个整数表示当 $k = i$ 时你吃掉的饼干的甜度之和。

样例

样例输入 1

3
3 999999999 0
2
4 2
BS

样例输出 1

2 5 9

样例输入 2

10
810737462 262894941 12979345 90139935 834123271 768745833 928886601 144082546 35547099 840309069
10
854737038 93768450 848842263 62613614 800833082 316988396 203584286 283415773 762732633 75602451
SBSSSBSSBS

样例输出 2

756024517 959608803 1243024576 1560012972 1893177483 228745833 262894941 2962894941 3296839941 3630784941

说明

在样例 1 中，$A = (3, 1, 5)$。 当 $k = 2$ 时，派对进行如下：

• 你放入甜度为 $3$ 和 $1$ 的饼干。
• 儿童 $1$ 放入甜度为 $4$ 的饼干，并吃掉甜度为 $1$ 的饼干。
• 儿童 $2$ 放入甜度为 $2$ 的饼干，并吃掉甜度为 $4$ 的饼干。
• 你吃掉甜度为 $2$ 和 $3$ 的饼干。