쿠키

쿠키 파티를 열려고 합니다! 번호가 1부터 N까지 붙은 쿠키 N개를 준비했습니다. 쿠키 $i$의 달콤함은 $A_i$입니다. 번호가 1부터 M까지 붙은 아이 M명이 파티에 올 것으로 예상합니다. 아이마다 직접 만든 쿠키를 가져오며, 아이 $i$가 가져오는 쿠키의 달콤함은 $B_i$입니다. 각 아이의 취향도 알고 있습니다. 아이 $i$는 $S_i$가 S이면 단 쿠키를 좋아하고, $S_i$가 B이면 쓴 쿠키를 좋아합니다.

파티는 다음 순서로 진행됩니다.

• 먼저 정수 $k$가 주어지고, 쿠키 $1,2,\cdots,k$를 테이블에 올립니다.
• 그다음 아이 $1,2,\cdots,M$이 이 순서대로 테이블에 옵니다. 아이 $i$는 먼저 자신이 가져온 쿠키를 테이블에 올립니다. 그 뒤 단 쿠키를 좋아하면 테이블에서 가장 단 쿠키(달콤함이 가장 큰 쿠키)를 먹고, 쓴 쿠키를 좋아하면 테이블에서 가장 쓴 쿠키(달콤함이 가장 작은 쿠키)를 먹습니다. 각 아이는 정확히 쿠키 한 개를 먹으며, 자신이 가져온 쿠키를 먹을 수도 있습니다.
• 마지막으로 테이블에 남은 쿠키를 모두 먹습니다.

아직 $k$의 값을 정하지 않았습니다. 각 정수 $k=1,2,\cdots,N$에 대해, 여러분이 먹게 되는 쿠키 달콤함의 합을 구하세요.

$k=i$에 대한 답을 구한 뒤에야 $A_{i+1}$의 값을 알 수 있습니다. 자세한 내용은 입력 섹션을 참고하세요.

입력은 표준 입력으로 다음 형식으로 주어집니다.

$N$

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

$M$

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

$S$

여기서 $A'_i$는 $A_i$를 암호화한 값이고, 실제 값은 $A_i=(A'_i+lastans \mod 10^9)$로 계산합니다. $lastans$는 $i>1$이면 $k=i-1$에 대한 답이고, $i=1$이면 $0$입니다.

$N$개의 정수를 한 줄에 출력하세요. $i$번째 정수는 $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$ (이 변수의 정의는 입력 섹션을 참고하세요)
• $1 \leq M \leq 2 \times 10^5$
• $0 \leq B_i \leq 10^9-1$
• $|S|=M$
• $S_i$는 S 또는 B입니다.
• 입력의 모든 값은 정수입니다.

첫 번째 예제에서 $A=(3,1,5)$입니다.

$k=2$일 때 파티는 다음과 같이 진행됩니다.

• 달콤함 $3$과 $1$인 쿠키 2개를 올립니다.
• 아이 1이 달콤함 $4$인 쿠키를 올리고, 달콤함 $1$인 쿠키를 먹습니다.
• 아이 2가 달콤함 $2$인 쿠키를 올리고, 달콤함 $4$인 쿠키를 먹습니다.
• 여러분은 달콤함 $2$와 $3$인 쿠키를 먹습니다.