분수 비교

이 문제는 대화형(interactive) 문제입니다. 아래 상호작용 절을 참고하세요.

오늘은 CS999의 첫 수업이었습니다.

먼저 $4 \times 10^{18}$ 이하의 음이 아닌 정수를 배웠습니다. 또한 두 정수의 덧셈, 뺄셈, 비교를 배웠습니다.

과제는 분수 $\frac{A}{B}$와 $\frac{C}{D}$를 비교하는 것입니다. 교수님은 수업 자료만으로 과제를 풀 수 있다고 하셨습니다.

다음 연산만 사용할 수 있습니다.

• 덧셈: 두 정수 $a$, $b$에 대해 $a+b$를 계산할 수 있습니다. 결과는 $4 \times 10^{18}$ 이하여야 합니다.
• 뺄셈: 두 정수 $a$, $b$에 대해 $a-b$를 계산할 수 있습니다. 결과는 0 이상이어야 합니다.
• 비교: 두 정수 $a$, $b$에 대해 값이 같은지, 어느 쪽이 큰지 알 수 있습니다.

이 연산들을 사용해 두 분수를 비교하세요.

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

$A$, $B$, $C$, $D$는 직접 얻을 수 없습니다. 대신 길이가 $10^6$인 숨겨진 배열 $X_1, X_2, \cdots, X_{10^6}$에 연산을 적용합니다.

처음에 $X_1=A$, $X_2=B$, $X_3=C$, $X_4=D$이고, $i>4$인 $X_i$는 모두 0입니다.

다음 명령을 사용합니다.

• 두 원소를 더하려면 + i j k를 출력합니다 ($1 \le i, j, k \le 10^6$). 그러면 $X_i$가 $X_j+X_k$가 됩니다. $X_j+X_k$는 $4 \times 10^{18}$ 이하여야 하며, 그렇지 않으면 Wrong Answer 판정을 받습니다. 입력으로는 아무것도 주어지지 않습니다.
• 두 원소를 빼려면 - i j k를 출력합니다 ($1 \le i, j, k \le 10^6$). 그러면 $X_i$가 $X_j-X_k$가 됩니다. $X_j \ge X_k$여야 하며, 그렇지 않으면 Wrong Answer 판정을 받습니다. 입력으로는 아무것도 주어지지 않습니다.
• 두 원소를 비교하려면 < i j를 출력합니다 ($1 \le i, j \le 10^6$). 입력으로 정수 하나가 주어집니다. $X_i<X_j$이면 -1, $X_i=X_j$이면 0, $X_i>X_j$이면 1이 주어집니다.

$\frac{A}{B}$와 $\frac{C}{D}$를 비교한 뒤에는 다음과 같이 출력합니다.

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

명령을 200,001개보다 많이 사용하거나 잘못된 질의를 하면 interactor가 즉시 종료되고 Wrong Answer 판정을 받습니다.

채점

비교 결과가 틀리면 점수는 0입니다. 그렇지 않으면 다음 세 가지 값으로 점수가 정해집니다.

• $i_{max}$: 연산에 사용한 배열 $X$의 최대 인덱스
• $n_{op}$: 수행한 연산 횟수 (답을 출력하는 명령은 세지 않습니다)
• $X_{max}$: 연산 중 배열 $X$에 있던 최댓값