Problem K
Four Questions

It looks like taking the singles line has paid off: you’re stuck on the ski lift with a mathematician. He’s promised to show you his secret powder stash¹ if you’re able to win a game against him. The game is as follows.

He will think of some prime number $p$ ($2\le p< 10^{10}$) and your goal is to figure out what $p$ is. In each round of the game, you pick some number $s$ ($1\le s\le 10^5$) and then he tells you what the remainder is if $s^2$ is divided by $p$.

Oh, and since the ski lift only takes a few minutes to get to the top, there’s only enough time for four rounds. Can you win the game by determining $p$?

Interaction

You may output up to four queries followed by a single answer. After each query the judge will respond with the result of your query. It is important that you flush your output stream after each query, so that the judge receives your output (otherwise, you may recieve a TLE verdict). For example, in Python this can be done with sys.stdout.flush() or in C++ with cout << flush.

A query is performed by printing a line of the form q $s$, where $1\le s\le 10^{5}$. The judge will then output a line with a single integer indicating the remainder if $s^2$ is divided by $p$.

Once you know the value of $p$, print a line of the form a $p$. After you output your answer, your program must terminate immediately.

q 43

3

q 15

12

q 71

0

a 71