Card Operation (Large)

A card game called Operation is played with a deck of operation cards. Each card holds one arithmetic operation $O_i$ (addition, subtraction, multiplication, or division) and one integer right operand $V_i$ for that operation. A card can read + 0, or - -2, or / -4. Operands can be negative or zero, but a division card never has 0 as its operand.

In each round a starting integer $S$ is chosen and a set of $C$ cards is laid out. The player picks an order for the cards and uses each card exactly once. The operations are then applied to $S$ in that order, and a final result comes out.

The operands are integers, but the operations run on rational numbers. Suppose the starting value is 5 and the cards are + 1, - 2, * 3, and / -2. In that order the final result is $(5 + 1 - 2) \times 3 / (-2) = -6$. The cards apply in the chosen order and operator precedence is ignored. With the order - 2, / -2, + 1, * 3 the result is $((5 - 2) / (-2) + 1) \times 3 = -3/2$, which is the largest value this set of cards can reach.

Given the starting value and the cards, find the maximum possible final value. Report it as an irreducible fraction with a positive denominator.

The first line holds the number of test cases $T$. Each test case starts with one line holding two integers $S$ and $C$, the starting value and the number of cards. Then $C$ lines follow. The i-th of those lines describes one card and holds one character $O_i$, which is +, -, *, or /, and one integer $V_i$.

Limits

• $1 \le T \le 100$
• $-1000 \le S \le 1000$
• $O_i$ is one of +, -, *, /, for all i.
• $-1000 \le V_i \le 1000$, for all i.
• If $O_i$ is /, then $V_i \ne 0$, for all i.
• $1 \le C \le 1000$

For each test case, print one line holding Case #x: y z, where $x$ is the test case number starting from 1, and $y$ and $z$ are integers such that $y/z$ is the maximum possible final value, $y$ and $z$ have no common divisor other than 1 and -1, and $z$ is strictly greater than 0.

The numerator can run far past the range of a 64-bit integer, so the answer needs arbitrary precision arithmetic.

Zero has exactly one valid form here, 0 1. The form 0 2 is invalid because it reduces, and 0 -1 is invalid because the denominator must be positive.