367. Monu bhaiya and Baseball

0

Easy

You are managing the scoring system for a unique baseball game. The game consists of multiple rounds, where the scores from previous rounds can impact the scores of future rounds.
At the start of the game, the record is empty. You are given a list of operations, ops, where each operation must be applied to the record. The operations can be one of the following:
1. An integer x - Add a new score of x to the record.
2. "+" - Add a new score that is the sum of the previous two scores. There will always be at least two previous scores.
3. "D" - Add a new score that is double the previous score. There will always be a previous score.
4. "C" - Invalidate the previous score and remove it from the record. There will always be a previous score.
Calculate and return the sum of all the scores on the record.

Input Format

The first line contains T, the number of test cases.

Each test case consists of two lines: the first line contains an integer N, and the second line contains N elements of the array in space-separated format.

Each test case consists of two lines: the first line contains an integer N, and the second line contains N elements of the array in space-separated format.

Output Format

For each test case, print the sum of all the scores on the record.

Example

Input

1
5
5 2 C D +

Output

30

Constraints

1 <= T <= 1000

1 <= N <= 1000

ops[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 10

For operation "+", there will always be at least two previous scores on the record.

For operations "C" and "D", there will always be at least one previous score on the record.

1 <= N <= 1000

ops[i] is "C", "D", "+", or a string representing an integer in the range [-3 * 10

^{4}, 3 * 10^{4}]For operation "+", there will always be at least two previous scores on the record.

For operations "C" and "D", there will always be at least one previous score on the record.

Loading...

View Submissions

Console