It Is Cold

Dr. Ziad Najem is called the godfather of the ACPC. The regional contest was held in Alexandria, Egypt, and the weather was very cold. Inside the contest hall the fans were running anyway. Dr. Ziad wants to know how fast the air arrives at each team.

A team has $N$ fans standing in a straight line to its right. Fan $i$ blows with speed $S_i$ in direction $C_i$. T means the fan blows toward the team, A means it blows away from the team. Fan 0 is the closest to the team and fan $N-1$ is the farthest.

The air starts at the farthest fan and travels along the line, passing one fan at a time. Two flows in the same direction add their speeds.

Two flows facing each other cancel, and the stronger direction survives.

Air that ends up moving away from the team leaves the line and never comes back, so the fans closer to the team start again from speed 0.

The first line contains the number of teams $T$. Each team takes three lines. The first line has the number of fans $N$. The second line has $N$ integers $S_i$ separated by spaces, the speed of the air produced by fan $i$ ($0 \le i < N$). The third line has $N$ characters $C_i$ separated by spaces, the direction of each fan.

• $T \le 100$
• $0 < N \le 1000$
• $0 \le S_i \le 1000000000$

Print $T$ lines, one per team. Each line holds a single integer $S$, the speed of the air that reaches the team. Print 0 when no air reaches the team.