23476번 - 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$.

출력

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$.

제한

• 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.

노트

In first sample, $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ドル$.