시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 1 1 50.000%

문제

You, Mr. Hackerman, have gained access to the servers of a secure messaging app. They use a new ciphering method based on the difficulty of factoring the numbers that are products of three big primes.

You are reading the source code and found out how they actually generate these numbers. They define three recurrences:

  • $x_n = (11 \cdot x_{n-1} + 7) \bmod 611\,953 \quad \forall n > 0$
  • $y_n = (13 \cdot y_{n-1} + 5) \bmod 746\,773 \quad \forall n > 0$
  • $z_n = (53 \cdot z_{n-1} + 3) \bmod 882\,389 \quad \forall n > 0$

The seeds $x_0, y_0, z_0$ seem to be stored in a secure file.

Now they get the three primes $p_k, q_k, r_k$ for the $k$-th user:

  • $p_k$ is $x_k$-th number in a secure file X.axx (all its numbers are different primes with exactly $31$ decimal digits).
  • $q_k$ is $y_k$-th number in a secure file Y.axx (all its numbers are different primes with exactly $32$ decimal digits).
  • $r_k$ is $z_k$-th number in a secure file Z.axx (all its numbers are different primes with exactly $33$ decimal digits).

Then, they compute the public key $n_k = p_k \cdot q_k \cdot r_k$.

You have temporary access to the public key database, and you can query up to 5 public keys for any user.

You are given two integers $u$ and $v$. You have to intercept communications between the $u$-th user and the $v$-th user. For this task, you will need to compute $p_u, q_u, r_u, p_v, q_v, r_v$; having these values will allow you to completely manipulate communication.

For the sake of input/output simplicity, we ask you to output $p_u + q_u + r_u + p_v + q_v + r_v$ as your answer.

프로토콜

First, you must read a line containing two integers $u$ and $v$ ($0 \le u, v < 7 \cdot 10^{12}$).

To ask for the public key ($n_k$) of the $k$-th user, print "? $k$", where $k$ is the user index. Remember that you can do at most 5 queries of this type.

The first user has index $0$, and there are exactly $7 \cdot 10^{12}$ users, so make sure $0 \le k < 7 \cdot 10^{12}$ in all your questions.

When you have computed the solution, print "! $a$", where $a = p_u + q_u + r_u + p_v + q_v + r_v$. Remember it's safer to stop your code after this query.

Don't forget to flush the output after printing each line!

The files X.axx, Y.axx, and Z.axx are the same for the whole problem.

예제 입력 1

10 20

192279309409462992645482090330404758368400469722499925076043266903464961794187094077107243967491

274848544065337166381629952590164863776020394941410553373502453263042134278227621768923600557617

61991716112162091571854380103197141133071202062437636592434396525428433284775254050695414158203

예제 출력 1


? 10

? 20

? 3

! 1188670725123074098790368447122696

힌트

Solution to the example ($u = 10$ and $v = 20$):

$p_{10} = 6745719728113484794920696767881$

$q_{10} = 54398126832702965410665141463513$

$r_{10} = 523986762172023700466774225430947$

$p_{20} = 6899037085323900149383957179569$

$q_{20} = 76607972465670150189802211467309$

$r_{20} = 520033106839239897778822214813477$

$p_{10} + q_{10} + r_{10} + p_{20} + q_{20} + r_{20} = 1188670725123074098790368447122696$

채점 및 기타 정보

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