1226 . Let the big dog eat
Description
Have you played a board game called "Felix: the cat in the sack"? The rule is so simple that everyone can enjoy it during the leisure time.
In this board game, there are "Cat cards" and "Dog cards" in hands. Each "Cat card" has a score marked on it, while a "Dog card" just effect the "Cat cards" in each round.
In each round, every player lays a card on the desk, and the summation of the scores on those cards will be counted into the player who wins the bid in that round. Every "Dog card" would bite a particular "Cat card" according to its type.
If it is a "Big dog", then one of "Cat cards" with the highest value will be bitten and will not contribute any score to the player if such "Cat card" exists. Otherwise it is a "Little dog", and one of "Cat cards" with the lowest value will be bitten and will not contribute any score to the player if such "Cat card" exists.
But there is a case when too many dogs present on the board. If there are more than one "Dog card" on the desk, they will fight to each other and thus no cat will be harmed. In this case, all the "Cat card" values will be reserved and counted.
Given all laid out cards on the desk in a round, please determine if any "Cat card" should be discarded.
Input Format
The first line of the input contains an integer T<=100 indicating the total number of test cases. For each test case, the first line contains an integer n (1<=n<=10000) indicating how many cards are laid on the desk. Next line contains n integers or strings seperated by white spaces denoting the information of the cards. If it is a number, then it is representing the value of a "Cat card". if it is the string "DOG" then it is a "Big dog card". If it is the string "dog" then it is a "Little dog card". The absolute value to every number will not exceed 109.
Output Format
For each test case please output the value of the "Cat card" that is bitten away or output "SAFE" if all "Cat cards" are reserved.
Sample Input 1
4 3 1 2 3 4 dog 123 234 345 4 5 6 7 DOG 3 DOG dog dog
Sample Output 1
SAFE 123 7 SAFE
Hints
Problem Source
Migrated from old NTUJ.
Tmt
Subtasks
| No. | Testdata Range | Score |
|---|