Это интерактивная задача.
Игорь хочет найти ключ к сердцу Ольги. Проблема в том, что он находится в корне бинарного дерева.
Есть полное бинарное дерево высотой \(h\), состоящее из \(n = 2^{h} - 1\) вершин. Вершинам были присвоены различные метки от \(1\) до \(n\). Однако Игорь знает только \(h\) и не знает, какой метке соответствует какая вершина.
Чтобы найти ключ к сердцу Ольги, ему нужно найти метку, соответствующую корню, сделав запросы следующего типа не более \(n+420\) раз:
- Игорь выберет три различные метки \(u\), \(v\) и \(w\) (\(1 \leq u,v,w \leq n\)).
- В ответ Ольга (интерактор) скажет ему метку наименьшего общего предка вершин, помеченных \(u\) и \(v\), если бы корнем дерева была вершина, помеченная \(w\).
Помогите Игорю найти метку корня дерева!
Примечание: интерактор не адаптивный: метки фиксируются перед выполнением каких-либо запросов.
Протокол взаимодействия
Вы начинаете взаимодействие с чтения \(h\).
Чтобы сделать запрос для меток \(u, v, w\), в отдельной строке выведите «? u v w».
Числа в запросе должны удовлетворять \(1 \le u, v, w \le n\). Дополнительно \(u \ne v\), \(u \ne w\) и \(v \ne w\).
В ответ вы получите \(1 \le x \le n\) — метку наименьшего общего предка \(u\) и \(v\), если бы корнем дерева была \(w\).
В случае, если ваш запрос некорректен или вы задали более \(n+420\) запросов, вы получите \(-1\) вместо ответа. Вы получите вердикт Неправильный ответ. Убедитесь, что вы немедленно выходите из программы, чтобы избежать получения других вердиктов.
Когда вы определите метку, присвоенную корню, выведите «! r», где \(r\) — метка корня.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Ваша программа должна немедленно завершиться после прочтения ответа «-1», вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.
Формат взломов
Для взлома используйте следующий формат.
Первая строка должна содержать одно целое \(h\) (высоту бинарного дерева).
В следующей строке выведите перестановку \(p\) размером \(n = 2^h - 1\). Она представляет собой бинарное дерево, в котором корень помечен \(p_1\), а для \(1 < i \le n\) непосредственным родителем \(p_i\) является \(p_{ \lfloor{\frac{i}{2}}\rfloor }\).
Примечание
Метки, соответствующие дереву в примере, равны [\(4\),\(7\),\(2\),\(6\),\(1\),\(5\),\(3\)], что означает, что корень обозначен \(4\), а для \(1 < i \le n\) родителем \(p_i\) является \(p_{ \lfloor{\frac{i}{2}}\rfloor }\).