Parencedence!

Parencedence는 두 명이 번갈아 진행하는 게임입니다. 먼저 정수와 이항 연산자 +, -, * 로 이루어진 산술식이 주어집니다. 처음 식에는 괄호가 없습니다.

두 플레이어는 번갈아 수를 둡니다. 한 번의 수에서 플레이어는 연산자 하나와 그 양쪽 피연산수 둘을 괄호로 묶고, 그 괄호 안 식을 계산한 다음 그 세 항을 계산 결과 값으로 바꿉니다. Player 1은 최종 값을 최대화하려 하고, Player 2는 최소화하려 합니다. 값이 하나만 남을 때까지 게임이 이어집니다.

예를 들어 한 라운드는 다음처럼 진행될 수 있습니다.

초기 식: 3-6*4-7+12
Player 1의 수: 3-6*(4-7)+12 → 3-6*-3+12
Player 2의 수: (3-6)*-3+12 → -3*-3+12
Player 1의 수: (-3*-3)+12 → 9+12
Player 2의 수: (9+12) → 21

한 게임은 같은 초기 식(괄호 없는 식)을 쓰는 두 라운드로 이루어집니다. 첫 번째 라운드에서는 Player 1이 먼저 두고, 두 번째 라운드에서는 Player 2가 먼저 둡니다. 두 라운드 모두에서 누가 먼저 두는지와 관계없이 Player 1은 항상 최대화, Player 2는 항상 최소화를 목표로 합니다. 첫 번째 라운드의 결과를 r1, 두 번째 라운드의 결과를 r2라 하자. r1 > -r2이면 Player 1이 이기고, r1 < -r2이면 Player 2가 이기며, 그 외에는 비김입니다. 두 플레이어가 모두 최선을 다한다고 가정하고 결과를 구하세요.

첫 줄에는 테스트 케이스의 수 n이 주어집니다. 이어지는 n개의 줄에는 각각 하나의 테스트 케이스가 주어지며, 양의 정수 m (m ≤ 9)과 그 뒤에 산술식이 따릅니다. m은 식에 들어 있는 이항 연산자의 개수입니다. 연산자는 +, -, * 만 사용됩니다. - 는 단항 연산자와 이항 연산자로 모두 쓰일 수 있습니다. 모든 이항 연산자는 양쪽에 정확히 한 칸씩 공백을 두며, 단항 - 뒤에는 공백이 없습니다. 어떤 괄호 조합을 썰더라도 정수 오버플로우나 언더플로우는 발생하지 않습니다.

각 테스트 케이스마다 Case k: (k는 1부터 시작하는 테스트 케이스 번호)를 출력한 뒤, 세 줄을 출력합니다.

• 첫 줄은 Player 1이 먼저 두는 라운드 1에서 Player 1의 최선의 첫 수와 그 라운드 결과 r1을 Player 1 (첫 수) leads to r1 형식으로 출력합니다. 여기서 첫 수는 가장 먼저 괄호로 묶은 연산자와 그 두 피연산수를 공백 없이 이어 쓴 것입니다 (예: 7+12, 45--67, -67-3).
• 둘째 줄은 Player 2가 먼저 두는 라운드 2에 대해 같은 형식으로 Player 2 (첫 수) leads to r2를 출력합니다.
• 셋째 줄은 r1과 -r2의 비교에 따라 Player 1 wins, Player 2 wins, 또는 Tie 중 하나입니다.

최적의 라운드 결과를 얻으면서 먼저 괄호로 묶을 수 있는 연산자가 여러 개라면, 원래 식에서 가장 앞서 나오는 연산자를 선택합니다.