406861: GYM102586 A Cookies

You are to hold a cookie party! You have prepared $$$N$$$ cookies numbered from $$$1$$$ through $$$N$$$. The **sweetness** of the cookie $$$i$$$ is $$$A_i$$$. You expect that $$$M$$$ children numbered from $$$1$$$ to $$$M$$$ will attend the party. All of them will bring their homemade cookies, and the child $$$i$$$ will bring a cookie of sweetness $$$B_i$$$. Besides, you know the taste preference of each child. The child $$$i$$$ loves sweet cookies if $$$S_i=$$$'S' and loves bitter cookies if $$$S_i=$$$'B'.

The party will proceed in the following manner:

• First, you are given an integer $$$k$$$ and put cookies $$$1,2,\cdots,k$$$ on the table.
• Then, children $$$1,2,\cdots,M$$$, in this order, come to the table. When the child $$$i$$$ comes to the table, the child first put his/her homemade cookie on the table. Then, if the child loves sweet cookies, he/she eats the sweetest cookie (a cookie with the largest sweetness) on the table. If the child loves bitter cookies, he/she eats the bitterest cookie (a cookie with the smallest sweetness) on the table. Note that each child eats exactly one cookie, and a child may eat his/her cookie.
• Finally, you eat all the cookies left on the table.

You have not yet decided the value of $$$k$$$. For each integer $$$k=1,2,\cdots,N$$$, find the sum of the sweetness of cookies you will eat.

Note that only after you get the answer for $$$k=i$$$ can you know the value of $$$A_{i+1}$$$. See the input section for more details.

Input is given from Standard Input in the following format:

$$$N$$$

$$$A'_1$$$ $$$A'_2$$$ $$$\cdots$$$ $$$A'_N$$$

$$$M$$$

$$$B_1$$$ $$$B_2$$$ $$$\cdots$$$ $$$B_M$$$

$$$S$$$

Here $$$A'_i$$$ is the encrypted value of $$$A_i$$$, and the real value can be calculated as $$$A_i=(A'_i+lastans \mod 10^9)$$$, where $$$lastans$$$ denotes the answer for $$$k={i-1}$$$ if $$$i>1$$$ and $$$0$$$ if $$$i=1$$$.

Constraints:

• $$$1 \leq N \leq 2 \times 10^5$$$
• $$$0 \leq A_i \leq 10^9-1$$$
• $$$0 \leq A'_i \leq 10^9-1$$$ (see the input section for the definition of this variable)
• $$$1 \leq M \leq 2 \times 10^5$$$
• $$$0 \leq B_i \leq 10^9-1$$$
• $$$|S|=M$$$
• $$$S_i$$$ is either 'S' or 'B'.
• All values in input are integers.

Print $$$N$$$ integers in one line. The $$$i$$$-th integer should be the sum of the sweetness of cookies you will eat when $$$k=i$$$.

3
3 999999999 0
2
4 2
BS

2 5 9

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

756024517 959608803 1243024576 1560012972 1893177483 2287313726 2503514053 3151110652 3337768403 3515845875

In the example $$$1$$$, $$$A=(3,1,5)$$$.

When $$$k=2$$$, the party proceeds as follows:

• You put $$$2$$$ cookies of sweetness $$$3$$$ and $$$1$$$.
• The child $$$1$$$ puts the cookie of sweetness $$$4$$$ and eats the cookie of sweetness $$$1$$$.
• The child $$$2$$$ puts the cookie of sweetness $$$2$$$ and eats the cookie of sweetness $$$4$$$.
• You eat cookies of sweetness $$$2$$$ and $$$3$$$.