A. Genius Cirno's Genius Computer
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Cirno's Perfect Math Class is now in session!

This is an interactive problem.

In the year 9999, the genius ice fairy Cirno has built the supercomputer Cirno9 capable of $$$1024$$$-bit integer arithmetic (int1024)! However, because Cirno is a genius, this machine only supports integer operations. Cirno9 has 8 general-purpose registers (variables) named $$$a,b,c,d,r_0,r_1,r_2,r_3$$$.

As a time traveler from 2025, you've obtained temporary access. Cirno9's first four registers $$$a,b,c,d$$$ are initialized with four positive integers $$$a_0,b_0,c_0,d_0$$$ representable by int1024, while the other four registers $$$r_0\cdots r_3$$$ are set to $$$0$$$. Your task is to use Cirno9 to compare the fractions $$$\dfrac{a_0}{b_0}$$$ and $$$\dfrac{c_0}{d_0}$$$.

You cannot directly observe the values of $$$a_0,b_0,c_0,d_0$$$, but you can send at most $$$6666$$$ operation requests to Cirno9 and make judgments based on its responses. See the "Interaction Protocol" section below for details.

Complete this task before Cirno releases "Perfect Freeze"!

Additional Notes

Since you come from an era with only int32 and int64 (and maybe int128), here are extra details about Cirno9's int1024:

  • int1024 operations behave similarly to C/C++ int operations, supporting addition, subtraction, multiplication, division (+ - * /) and comparisons. Like C/C++, integer division truncates toward zero. Examples: $$$100 / 3 = 33$$$, $$$(-5) / 2 = -2$$$, $$$(-10) / (-3) = 3$$$.
  • int1024 can represent integers in $$$[-2^{1023}, 2^{1023})$$$. Operations must not overflow — results must be representable by int1024, otherwise Cirno9 will explode. For division, the divisor cannot be $$$0$$$, or Cirno9 will freeze.
Input

There is no initial input. You must send queries to the interactor.

Interaction

You may use $$$8$$$ int1024 variables named $$$a,b,c,d,r_0,r_1,r_2,r_3$$$ (corresponding strings: a b c d r0 r1 r2 r3).

  • $$$a, b, c, d$$$ are initialized to positive integers $$$a_0,b_0,c_0,d_0$$$
  • $$$r_0, r_1, r_2, r_3$$$ are initialized to $$$0$$$

You can perform the following operations:

  1. op x y z: Compute $$$y\ \mathrm{op}\ z$$$ and store in $$$x$$$ ($$$\mathrm{op}\in\{\texttt{+},\texttt{-},\texttt{*},\texttt{/}\}$$$)
    • Returns ok if successful, otherwise err
  2. ? x y: Compare $$$x$$$ and $$$y$$$
    • Returns >, =, or < indicating the relationship, or err if failed
  3. ! rel: Submit final comparison of $$$\frac{a_0}{b_0}$$$ and $$$\frac{c_0}{d_0}$$$ ($$$\textrm{rel}\in\{\texttt{ \gt },\texttt{=},\texttt{ \lt }\}$$$)
    • Returns ok if correct, otherwise err

Note: For operation types 1 and 2, variable names may be identical (e.g., "+ a a b" or "* r0 r0 r0").

Possible reasons for err responses:

  1. Invalid operation
  2. Nonexistent variable
  3. Arithmetic overflow or division by zero
  4. Exceeding operation limit
  5. Incorrect final answer

When receiving err, your program will be judged as Wrong Answer. You should immediately terminate after reading err to avoid unexpected evaluation results.

You may perform at most $$$6666$$$ operations. The final answer doesn't count toward this limit; other operations count as $$$1$$$ each.

After printing an operation, do not forget to output the end of the line and flush the output. Otherwise you'll receive Time Limit Exceeded. Flushing methods:

  • C++: fflush(stdout) or cout.flush()
  • Pascal: flush(output)
  • Java: System.out.flush()
  • Python: stdout.flush()
Example
Input

ok

ok

ok

>

ok
Output
* r0 a d

* r1 b c

- r0 r0 r1

? r0 r2

! >
Note

In this sample, the initial values inside the interactor are $$$a = 99$$$, $$$b = 999$$$, $$$c = 9$$$, $$$d = 99$$$. We need to compare the sizes of $$$\frac{99}{999}$$$ and $$$\frac{9}{99}$$$.

  1. Operation 1: * r0 a d
    • Compute $$$a \times d = 99 \times 99 = 9801$$$, and store the result in $$$r_0$$$.
    • The interactor returns ok, indicating the operation succeeded.

  2. Operation 2: * r1 b c
    • Compute $$$b \times c = 999 \times 9 = 8991$$$, and store the result in $$$r_1$$$.
    • The interactor returns ok, indicating the operation succeeded.

  3. Operation 3: - r0 r0 r1
    • Compute $$$r_0 - r_1 = 9801 - 8991 = 810$$$, and store the result in $$$r_0$$$.
    • The interactor returns ok, indicating the operation succeeded.

  4. Operation 4: ? r0 r2
    • Compare the values of $$$r_0$$$ and $$$r_2$$$. Since $$$r_0 = 810$$$ and $$$r_2 = 0$$$, we have $$$r_0 \gt r_2$$$.
    • The interactor returns >.

  5. Operation 5: ! >
    • We know that $$$\frac{a_0}{b_0} = \frac{99}{999} \approx 0.0991$$$, and $$$\frac{c_0}{d_0} = \frac{9}{99} \approx 0.0909$$$, so the reported answer is correct.
    • The interactor returns ok, indicating the answer is correct.

The attachment provides a reference implementation of Cirno9, which you can use to test int1024.