시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB111100.000%

문제

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.

예제 입력 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 756024517
SBSSSBSSBS

예제 출력 2

756024517 959608803 1243024576 1560012972 1893177483 2287313726 2503514053 3151110652 3337768403 3515845875

노트

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