Parencedence!
Parencedence — это новая увлекательная игра для двух игроков, которая завоевывает популярность в Лихтенштейне (хотя это не имеет значения). Правила игры таковы: компьютер генерирует арифметическое выражение, состоящее из целых чисел и бинарных операторов '+', '-' и '*'. В выражении отсутствуют скобки. Если первым ходит Игрок 1, он/она может поставить скобки вокруг любого одного оператора и его двух операндов; выражение в скобках вычисляется, и его значение заменяет исходное. Затем ходит Игрок 2, и игра продолжается, чередуя ходы Игрока 1 и Игрока 2. Цель Игрока 1 — максимизировать итоговое значение, в то время как цель Игрока 2 — минимизировать его. Пример раунда может выглядеть следующим образом:
Игра Parencedence состоит из двух раундов, каждый из которых начинается с одного и того же выражения без скобок: в первом раунде первым ходит Игрок 1, а во втором — Игрок 2 (Игрок 1 всегда стремится максимизировать результат, а Игрок 2 — минимизировать, независимо от того, кто ходит первым). Пусть r_1 будет результатом первого раунда, а r_2 — результатом второго раунда. Если r_1 > -r_2, выигрывает Игрок 1; если r_1 < -r_2, выигрывает Игрок 2; в противном случае игра заканчивается вничью. Ваша задача — написать программу, которая определит окончательный результат, предполагая, что оба игрока играют оптимально.
Входные данные
Первая строка входного файла содержит целое число n, обозначающее количество тестовых случаев. Далее следуют тестовые случаи, каждый на отдельной строке, состоящие из положительного целого числа m ≤ 9 и арифметического выражения. Значение m указывает количество бинарных операторов в выражении. Единственными используемыми операторами будут '+', '-' и '*'. Оператор '-' может быть как унарным, так и бинарным. Все бинарные операторы окружены пробелами с обеих сторон. После унарного '-' пробела нет. Никакая комбинация скобок не приведет к переполнению или недополнению целого числа.
Выходные данные
Для каждого тестового случая выведите номер случая, за которым следуют три строки. Первая строка содержит первый набор операндов и оператор, который будет заключен в скобки в раунде 1 (когда Игрок 1 ходит первым) и r_1. Вторая строка содержит аналогичный вывод для раунда 2. Третья строка содержит либо фразу "Player 1 wins", "Player 2 wins" или "Tie", в зависимости от значений r_1 и r_2. В первых двух строках вывода, если есть выбор, какой оператор заключить в скобки первым, используйте тот, который встречается раньше в исходном выражении. Следуйте формату, использованному в примерах.