Problem E
Number Colosseum

Picture by Jimmy Walker via Wikimedia Commons, cc by-sa

Welcome to the Number Colosseum, where two teams of integers are preparing to battle! On the left side of the number line we have team Negatives while on the right side we have team Positives. Every integer fighting in the colosseum is on one of these two teams.

At the start of the battle, the contestants line up outside the colosseum. One by one, the contestants enter the colosseum and follow these rules:

• If there are no contestants from the other team, this contestant will wait and become the most recent contestant to have entered the colosseum.

• If at least one contestant of the opposing team is in the colosseum, this contestant will fight the contestant on the opposing team who has most recently entered the colosseum. The winner of a fight between a negative integer and positive integer is the one with the highest absolute value. After a fight occurs, the value of the winner becomes the sum of two fighting integers while the loser leaves. Note that if the two integers have the same absolute value, they both lose and both leave. If there is a winner, they will continue fighting as long as there are more opposing contestants. Otherwise, they will wait.

After all of the integers have entered the colosseum, only one team may be declared the winners of the Number Colosseum! Given the lineup of contestants for the upcoming battle, write a program to determine which team will triumph as well as the state of the colosseum after all fights have occurred.

Input

The first line contains a single integer $N$ ($1 \leq N \leq 5 \cdot 10^5$), which is the number of contestants who will enter the colosseum. The second line contains the lineup of contestants. This will contain $N$ space-separated integers $x_1, x_2, \ldots , x_ N$ ($1 \leq |x_ i| \leq 10^6$ for each $1 \leq i \leq N$), the value of the $i$th contestant entering the colosseum.

Output

Display the winning team with either Positives win! or Negatives win!. On the following line display the list of integers remaining in the colosseum after all fighting has finished. Display these integers in the order of arrival into the colosseum.

If neither team wins, display Tie! instead.

Explanation

In Sample Input $1$, $N = 4$ and the contestants have lined up in this order $[-3, -4, 9, 1]$.

• First, contestant $-3$ enters the colosseum which now contains $(-3)$.

• Next, contestant $-4$ enters the colosseum which now contains $(-3, -4)$.

• Then, $9$ enters and fights $-4$. Contestant $9$ wins and becomes $5$ while contestant $-4$ loses and leaves. Then $5$ fights $-3$, wins, and becomes $2$ while $-3$ loses and leaves. The colosseum now contains $(2)$.

• Finally, $1$ enters the colosseum. The final state of the Colosseum is $(2, 1)$ and Positives win!

4
-3 -4 9 1

Positives win!
2 1

7
4 -2 -2 2 -1 -1 -1

Negatives win!
-1

6
10 -2 -2 -2 -2 -2

Tie!