Problem F
Split Median

Finding the median in a sorted array is a simple task, and all you have to do in this assignment. From the lectures you can recall that it is sufficient to simply take the middle element of the array and you are done!

But woe is upon you! Láki has snuck in and ruined everything for you. He separated your sequence into two sorted sequences and then hid those sequences away. Then he hid the sequences with imp magic. Now you can only look at one element at a time, making you unable to see the sequences in full easily.

The assignment deadline is coming up so you better find the median as quickly as possible!

Interactivity

This is an interactive problem. Your solution will be tested against an interactive judge which reads the output of your solution and prints the input your solution receives. This interaction follows certain rules:

First, your program should read a line with two strictly positive integers $n$ and $m$, where $2 \leq n+m \leq 100\, 000$. The grader program will have two hidden sequences $a_1, a_2, \dotsc , a_n$ and $b_1, b_2, \dotsc , b_m$. You will then repeat multiple rounds. In each round, you can choose one of three operations:

• Write ? A i where $i$ is a $1$-based index of the first sequence. You can then read the value $a_i$ given by the grader program.

• Write ? B i where $i$ is a $1$-based index of the second sequence. You can then read the value $b_i$ given by the grader program.

• Write ! x where $x$ is the value you have determined to be the median. After this operation, your program should exit.

Each integer in the two sequences is between $-10^9$ and $10^9$, inclusive on both ends. If $n + m$ is even there will be two middle elements, and either of them will be accepted as an answer.

Make sure to flush after each guess, for example using

• print(..., flush=True) in Python,

• cout << ... << endl; in C++,

• System.out.flush(); in Java.

Scoring

You must find a correct median using less than $2 \cdot (n + m)$ operations. The final operation, where you report your answer, is not included in the count. If you use $n + m$ operations, then you will get a score of $10$ out of a possible $100$ total. Using fewer operations will result in a higher score, but the score does not scale linearly.

3 4

? A 3

8

? B 1

2

? B 3

7

? A 1

1

? B 2

 5

! 5