Problem J
Jumper

Image by Joan Rocaguinard; license: CC BY-SA 3.0.

You lost your favourite jumper during last night’s pub crawl with your fifteen friends. You remember very little, but thanks to some selfies on your phone you have been able to identify a pub $p$ where you already lost the jumper. Moreover, from another selfie’s timestamp it is clear that you still wore the jumper at the pub immediately before pub $p$, but you are unable to determine which pub that is from the photo.

Your group of friends always visits the pubs in the same order, but you have never paid any attention to this—you just tend to keep up with the group. Unlike you, all your friends know the pub crawl order by heart. To avoid appearing too absent-minded, you will ask them each of them a question of the form “What is the name of the pub that we always visit $k$ pubs after pub $q$?” Here, $q$ is a name of a pub, and $k$ is a positive integer. Surely you can recover your jumper with some well-chosen questions!

The town has $100$ pubs named $1,\dots ,100$. Formally, the pub crawl order is a permutation $\pi$ on these numbers with $\pi (i)\ne i$; after visiting pub $i$ the group always proceeds to pub $\pi (i)$. The permutation need not be cyclic. A pub crawl starts at an arbitrary pub, and then continues visiting pubs according to $\pi$ until you get weary and go home.

Interaction

This is an interactive problem. Your submission will be run against an interactor program, which reads the standard output of your submission and writes to the standard input of your submission. The interactor begins by writing a single integer $p\in \{1,\dots ,100\}$, the name of the pub visited immediately after losing your jumper. This will never be the first pub your group visited last night. You can then make up to $15$ questions. Each questions must be in the format “? $q$ $k$”, where $q,k\in \{1,\dots ,100\}$. The interactor will respond with the name of the pub that is $k$ pubs along the pub crawl from pub $q$. After the at most $15$ questions, you must finish by writing a string on the format “! $j$”, such that $j$ is the pub where you lost your jumper, i.e., $\pi (j)=p$.

For each test case, the pub crawl permutation $\pi$ and the index $j$ are fixed in advance by the interactor.

4

? 10 4

8

? 54 9

4

? 54 8

42

! 42