시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB56171436.842%

## 문제

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점)

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

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

## 서브태스크 2 (13점)

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

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

## 서브태스크 3 (21점)

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

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

## 서브태스크 4 (22점)

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

## 서브태스크 5 (18점)

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

## 서브태스크 6 (21점)

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

## 예제 입력 1

-1


## 예제 출력 1

+ 5 3 1
- 1 2 1
< 1 5
! 0


For the first example, $A=1$, $B=1$, $C=2$, $D=2$. It satisfies the constraint of subtask 2,3,4,5,6.

## 예제 입력 2

1
-1
0


## 예제 출력 2

< 1 2
< 4 3
< 2 2
! -1


For the second example, $A=1$, $B=2$, $C=3$, $D=4$. It satisfies the constraint of every subtask.

# 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.

## 채점 및 기타 정보

• 예제는 채점하지 않는다.