문제

This problem is interactive. Refer to the Interaction section below for a better understanding.

Today was the first class of CS999.

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

The homework is to compare two fractions $\frac{A}{B}$ and $\frac{C}{D}$. Professor told you that you can solve homework only using classroom materials.

You are only allowed to use the following operations:

• Addition: For two integers $a$ and $b,ドル you can calculate $a+b$. The result should be less than or equal to 4ドル \times 10^{18}$.
• Subtraction: For two integers $a$ and $b,ドル you can calculate $a-b$. The result should be non-negative.
• Comparison: For two integers $a$ and $b,ドル you can know whether two elements are equal or which one is greater.

By using these operations, you have to compare two fractions.

입력

출력

제한

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

서브태스크 1 (5점)

This subtask has an additional constraint:

• $\{A,B,C,D\} = \{1,2,3,4\}$

Your program should satisfy:

• $n_{op} \le 200,000円$

서브태스크 2 (13점)

This subtask has an additional constraint:

• $A, B, C, D \leq 10,000円$

Your program should satisfy:

• $i_{max} \le 100$
• $n_{op} \le 100,000円$
• $X_{max} \le 10^9$

서브태스크 3 (21점)

This subtask has an additional constraint:

• $A, B, C, D \leq 10^6$

Your program should satisfy:

• $i_{max} \le 100$
• $n_{op} \le 10,000円$
• $X_{max} \le 2 \times 10^9$

서브태스크 4 (22점)

This subtask has no additional constraint.

Your program should satisfy:

• $i_{max} \le 100$
• $n_{op} \le 1,000円$

서브태스크 5 (18점)

This subtask has no additional constraint.

Your program should satisfy:

• $i_{max} \le 100$
• $n_{op} \le 1,000円$
• $X_{max} \le 2 \times 10^9$

서브태스크 6 (21점)

This subtask has no additional constraint.

• $i_{max} \le 100$
• $n_{op} \le 1,000円$
• $X_{max} \le 10^9$

노트

Interaction Protocol

You cannot get $A,ドル $B,ドル $C,ドル nor $D$ directly in this problem.
Instead, you can use some operations to a hidden array of length 10ドル^6$; $X_1, X_2, \cdots, X_{10^6}$.

Initially, $X$ satisfies $X_1=A,ドル $X_2=B,ドル $X_3=C,ドル $X_4=D,ドル and $X_i=0$ for $i$ greater than 4ドル$.

You can use the following commands to do operations:

• To add two elements of $X,ドル print a string "+ i j k" (1ドル \le i, j, k \le 10^6$). $X_i$ will be replaced with a value of $X_j+X_k$.
  To perform this operation, $X_j + X_k$ must be less than or equal to 4ドル \times 10^{18}$. If not, you will receive a verdict of "Wrong Answer". Nothing will be given to the input.
• To subtract two elements of $X,ドル print a string "- i j k" (1ドル \le i, j, k \le 10^6$). $X_i$ will be replaced with a value of $X_j-X_k$.
  To perform this operation, $X_j \ge X_k$ must be satisfied. If not, you will receive a verdict of "Wrong Answer". Nothing will be given to the input.
• To compare two elements of $X,ドル print a string "< i j" (1ドル \le i, j \le 10^6$). A line containing one integer will be given to the input.
  • "-1" will be given when $X_i<X_j$.
  • "0" will be given when $X_i=X_j$.
  • "1" will be given when $X_i>X_j$.

After successfully comparing $\frac{A}{B}$ and $\frac{C}{D},ドル

• If $\frac{A}{B} < \frac{C}{D},ドル print "! -1".
• If $\frac{A}{B} = \frac{C}{D},ドル print "! 0".
• If $\frac{A}{B} > \frac{C}{D},ドル print "! 1".

If you ask more than 200ドル,001円$ commands or make an invalid query, the interactor will terminate immediately and your program will receive the verdict "Wrong Answer".

Scoring

If your comparison is incorrect, your score will be 0ドル$.

Otherwise, the score of the program will be graded with three factors:

• $i_{max},ドル the maximum index of the array $X$ you have used in operations.
• $n_{op},ドル the number of operations you have done. Answer command will not be counted.
• $X_{max},ドル the maximum number in the array $X$ during operations.