Параценденція!
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. У перших двох рядках виводу, якщо є вибір між тим, який оператор слід взяти в дужки першим, використовуйте той, який з'являється раніше в початковому виразі. Дотримуйтесь формату, використаного в прикладах.