Kung-Fu Fighting
Iman wants to join the Ninjas of Intellect, Prestige and Honor (NOIPH). Their goal, which surprises many, is to be intellectual, prestigious and honorable ninjas.
To become a full-fledged member, an applicant must perform a sequence of moves flawlessly. Each Kung-Fu move displaces the performer a number of centimeters from the place they started from.
However, Iman generally practices inside a tiny room. And so if he wants to practice a sequence of Kung-Fu moves, he can't go one direction all the time (otherwise he'll smash into the wall, a ninja move that he has yet to learn). Thus he has to vary which directions he takes as he intends to make sure that he covers as little space as possible.
Formally speaking, for each move in the sequence of Kung-Fu moves, Iman can choose to do it east (displaces him to the east by some centimeters, depending on the move) or do it west. He only chooses these two directions as his practice room is narrow and goes from east to west.
After doing the sequence of Kung-Fu moves, Iman can compute the space he used. Since Iman basically only moves within a straight line, we can represent his position by real numbers (in particular, integers, where centimeters is the units).
We measure the space he used by taking the difference of the integer representing the eastmost position he reached with the integer representing the westmost position he reached.
For each move, help Iman decide which direction he should take so that the space he uses is minimal.
Input Format
The first line of input contains , the number of sequences of moves that Iman considers.
The first line of each test case contains , the number of Kung-Fu moves Iman has to do for that sequence. The second line contains integers separated by single spaces, , telling us that the move displaces Iman by centimeters.
Constraints
Subtask 1 (11 points each):
Subtask 2 (16 points each):
Subtask 3 (23 points each):
Output Format
For each test case, output a string of length , where the character of the string is either E
or W
, indicating that Iman must do the Kung-Fu move towards the east or west respectively.
Sample Input
2
3
11 2 7
10
4 3 1 4 1 1 4 1 3 4
Sample Output
EWW
WEEWEWEWWE
or
WEE
WEEWEWEWWE
Explanation
Taking the direction to be WWW
or EEE
makes the space used 20 centimeters.
Taking the direction to be WEW
or EWE
makes the space used 16 centimeters.
Taking the direction to be WWE
or EEW
makes the space used 13 centimeters.
Taking the direction to be WEE
or EWW
makes the space used 11 centimeters.
It can be shown that we have exhausted all possibilities. And so, 11 is the minimum space such that Iman can practice all his moves in sequence.
xxxxxxxxxx
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}