Игра для двух игроков определяется её деревом. Соперники делают ходы по очереди. Первый игрок начинает игру. Игра кончается или вничью, или победой одного из игроков. Листья дерева этой игры могут иметь значения, равные одному из трёх чисел: +1 - победа первого игрока, -1 - победа второго игрока, 0 - ничья. Ваша задача - определить, кто выиграет, если оба противника следуют правильной стратегии.
Входные данные
Узлы дерева пронумерованы последовательными целыми числами. Корень дерева всегда имеет номер 1. Первая строка входного файла содержит целое N - число узлов в дереве игры. Следующая N - 1 строка описывает узлы - одна строка для каждого узла (за исключением первого). Вторая строка содержит описание второго узла дерева, третья - третьего узла и т.д. Если узел является листом, первый символ строки - L, затем идёт пробел, затем номер родительского узла, ещё пробел и результат игры (+1 - победа первого игрока, -1 - победа второго, 0 - ничья). Если узел внутренний, то строка содержит N - первый символ, затем пробел и номер родительского узла. 2 <= N <= 1000.
Выходные данные
Выводится +1, если выигрывает первый игрок, -1, если второй, и 0 - в случае ничейного исхода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 +1
|
+1
|
|
2
|
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 0
|
0
|
|
3
|
7
N 1
N 1
L 2 -1
L 2 +1
L 3 +1
L 3 -1
|
-1
|