카드 연산 (라지)

문제

카드로 하는 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은 분모가 음수이므로 틀린다.