A game for two players is determined by its tree. The competitors make moves in turn. The first competitor starts the game. The game ends up with either a draw, or a victory of one of the players. The leaf nodes of the tree of this game may have values equal to one of three numbers: “+1” – victory of the first competitor, “–1” – victory of the second competitor, “0” – draw.
You have to find out who will win if both competitors follow the right strategy.
Input
The nodes of the tree are numbered with successive integer numbers. The root of the tree always has number 1.
The first line contains an integer N (1 < N ≤ 1000) – the number of the nodes in the game tree. Next N-1 lines describe the nodes – one line for each node (with exception for the first node). The second line will contain the description of the second node of the tree, the third line – the description of the third node, and so on.
If the node is a leaf of the tree, the first symbol of the line is “L”, followed by a space, then the number of the ancestor of this node goes, another space, and the result of the game (+1: victory of the first player, –1: victory of the second one, 0: draw).
If the node is an inner one then the line contains the first symbol “N”, a space character and the number of the ancestor of this node.
Output
contains “–1” if the second competitor wins, “+1” if so does the first and “0” if the result is a draw.
Samples
input | output |
---|
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 +1
| +1
|
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 0
| 0
|
18
N 1
N 1
N 2
L 2 +1
N 3
L 3 +1
L 3 +1
L 4 -1
L 4 +1
N 4
N 6
L 6 -1
L 6 -1
L 11 -1
L 11 +1
L 12 +1
L 12 -1
| +1
|
Problem Author: © Sergey G. Volchenkov, 2003(volchenkov@yandex.ru); Vladimir N. Pinaev, 2003(vpinaev@mail.ru; http://www.pic200x.chat.ru); Michael Y. Kopachev, 2003 (mkopachev@krista.ru).
Problem Source: 2003-2004 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 15-16, 2003