Comparing Fractions

This problem is interactive. See the Interaction Protocol section below.

Today was the first class of CS999.

First, you have learned non-negative integers less than or equal to $4 \times 10^{18}$. You have also learned addition, subtraction, and comparison of two integers.

The homework is to compare two fractions $\frac{A}{B}$ and $\frac{C}{D}$. The professor said you can solve the homework using only classroom material.

You may use only the following operations:

• Addition: For two integers $a$ and $b$, you can calculate $a+b$. The result must be at most $4 \times 10^{18}$.
• Subtraction: For two integers $a$ and $b$, you can calculate $a-b$. The result must be non-negative.
• Comparison: For two integers $a$ and $b$, you can find out whether they are equal or which one is greater.

Using these operations, compare the two fractions.

$1 \leq A, B, C, D \leq 10^9$

You cannot get $A$, $B$, $C$, or $D$ directly. Instead, you apply operations to a hidden array $X_1, X_2, \cdots, X_{10^6}$ of length $10^6$.

Initially $X_1=A$, $X_2=B$, $X_3=C$, $X_4=D$, and $X_i=0$ for $i>4$.

Use these commands:

• To add two elements, print + i j k ($1 \le i, j, k \le 10^6$). $X_i$ becomes $X_j+X_k$. $X_j+X_k$ must be at most $4 \times 10^{18}$, otherwise the verdict is Wrong Answer. Nothing is given as input.
• To subtract two elements, print - i j k ($1 \le i, j, k \le 10^6$). $X_i$ becomes $X_j-X_k$. You must have $X_j \ge X_k$, otherwise the verdict is Wrong Answer. Nothing is given as input.
• To compare two elements, print < i j ($1 \le i, j \le 10^6$). One integer is given as input: -1 if $X_i<X_j$, 0 if $X_i=X_j$, and 1 if $X_i>X_j$.

After comparing $\frac{A}{B}$ and $\frac{C}{D}$, print:

• ! -1 if $\frac{A}{B} < \frac{C}{D}$
• ! 0 if $\frac{A}{B} = \frac{C}{D}$
• ! 1 if $\frac{A}{B} > \frac{C}{D}$

If you use more than 200,001 commands or make an invalid query, the interactor terminates immediately and the verdict is Wrong Answer.

Scoring

If the comparison is wrong, the score is 0. Otherwise the score depends on three factors:

• $i_{max}$: the largest index of $X$ used in an operation
• $n_{op}$: the number of operations performed (the answer command is not counted)
• $X_{max}$: the largest value in $X$ during the operations