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