카드 연산 (라지)

카드로 하는 Operation이라는 놀이가 있다. 카드 한 장에는 사칙연산 중 하나인 연산 $O_i$(덧셈, 뺄셈, 곱셈, 나눗셈)와 그 연산의 오른쪽 피연산자인 정수 $V_i$가 적혀 있다. + 0, - -2, / -4 같은 카드가 나올 수 있다. 피연산자는 음수나 0일 수 있지만, 나눗셈 카드의 피연산자는 0이 아니다.

한 판에서는 시작 정수 $S$를 정하고 카드 $C$장을 늘어놓는다. 참가자는 카드 순서를 마음대로 정할 수 있고, 각 카드를 정확히 한 번씩 쓴다. 정한 순서대로 $S$에 연산을 차례로 적용하면 최종 결과가 나온다.

카드에 적힌 피연산자는 모두 정수지만, 연산은 유리수에서 이루어진다. 시작값이 5이고 카드가 + 1, - 2, * 3, / -2라고 하자. 적힌 순서 그대로 쓰면 결과는 $(5 + 1 - 2) \times 3 / (-2) = -6$이다. 연산자 우선순위는 무시하고 카드 순서대로만 계산한다. 순서를 - 2, / -2, + 1, * 3으로 고르면 결과는 $((5 - 2) / (-2) + 1) \times 3 = -3/2$이고, 이 카드 묶음으로 얻을 수 있는 최댓값이다.

시작값과 카드가 주어질 때 최종 결과의 최댓값을 구하라. 답은 분모가 양수인 기약분수로 나타낸다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 시작값 $S$와 카드의 개수 $C$가 주어진다. 이어서 $C$개의 줄이 주어지고, 그중 i번째 줄에는 카드 한 장을 나타내는 연산 문자 $O_i$와 피연산자 정수 $V_i$가 주어진다. $O_i$는 +, -, *, / 중 하나다.

제한

• $1 \le T \le 100$
• $-1000 \le S \le 1000$
• 모든 i에 대해 $O_i$는 +, -, *, / 중 하나다.
• 모든 i에 대해 $-1000 \le V_i \le 1000$
• 모든 i에 대해 $O_i$가 /이면 $V_i \ne 0$
• $1 \le C \le 1000$

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$와 $z$는 $y/z$가 최종 결과의 최댓값이 되는 정수다. $y$와 $z$의 공약수는 1과 -1뿐이어야 하고, $z$는 0보다 커야 한다.

분자는 64비트 정수 범위를 훨씬 넘을 수 있으므로 임의 정밀도 연산이 필요하다.

값이 0일 때 올바른 표현은 0 1 하나뿐이다. 0 2는 약분되므로 틀리고, 0 -1은 분모가 음수이므로 틀린다.