A. Length of the Path
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Your friend has been hiking in Cabezón de cuadrícula (a small village); there, all the paths go from north to south or from east to west.

Your friend says he has walked a lot until he returned to where he started, but he doesn't know exactly how much. After a moment, he remembers that he has a notebook where he has noted down the path he has taken.

The description has the following format:

  • Direction: N (North), S (South), E (East), or O (West)
  • Distance: A positive integer amount in meters.

In the notebook, there are $$$n$$$ descriptions.

Unfortunately, some of the distances in the notebook have been lost due to the notebook getting wet in the rain.

Your friend asks you to find out what the minimum possible distance he has traveled is and what the maximum possible distance he has traveled is.

Input

The first line contains an integer $$$T$$$, the number of cases.

Following are $$$T$$$ cases in the following format:

The first line contains an integer $$$n$$$.

The next $$$n$$$ lines contain the descriptions in order. Each description consists of two elements separated by a space:

  • An uppercase letter $$$d_i$$$ representing the direction (explained in the statement).
  • An integer $$$l_i$$$ representing the distance traveled in that direction; if the number is illegible, it will be $$$-1$$$.
Output

The output consists of two integers separated by a space.

If the notes in the notebook cannot correspond to any path, print "-1 -1" (without quotes).

Otherwise, print the minimum and maximum distances separated by a space.

If the duration of the walk is possibly unlimited, print a $$$-1$$$ for the maximum duration.

Scoring
  1. (14 points) $$$n \leq 2$$$.
  2. (10 points) There are no distances erased.
  3. (15 points) At most, there is $$$1$$$ distance erased.
  4. (15 points) At most, there are $$$2$$$ distances erased.
  5. (16 points) Only North and South directions appear.
  6. (30 points) No additional restrictions.
Example
Input
4
2
N 1
S -1
2
N -1
S -1
1
N -1
4
N 1000000000
S 1000000000
N 1000000000
S 1000000000
Output
2 2
2 -1
-1 -1
4000000000 4000000000
Note
  • $$$1 \leq T \leq 10^5$$$
  • $$$1 \leq n \leq 10^5$$$
  • $$$1 \leq l_i \leq 10^9$$$
  • The sum of $$$n$$$ over all cases is less than or equal to $$$10^5$$$.