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.

Line: 1 Col: 1
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score