Это интерактивная задача.

Дан отсортированный по возрастанию односвязный список. Необходимо найти в нем минимальное число, большее или равное x.

Более формально, есть односвязный список, построенный на массиве из n элементов. Ячейка с индексом i хранит два целых числа: value_i — значение в данной ячейке, и next_i — индекс следующей ячейки односвязного списка (либо -1, если текущая ячейка последняя). Список отсортирован, то есть если next_i ≠  - 1, то value_nexti > value_i.

Вам дано количество элементов списка n, индекс его первой ячейки start и число x.

Вы можете сделать до 2000 запросов двух типов:

• ? i (1 ≤ i ≤ n) — узнать, чему равны значение value_i и next_i,
• ! ans — выдать ответ на задачу: минимальное число, большее или равное x, либо ! -1, в случае, когда таких чисел нет. После этого запроса необходимо завершить программу.

Напишите программу, которая решает данную задачу.

Чтобы задать запрос первого типа, выведите ? i (1 ≤ i ≤ n), где i — номер ячейки, про которую вы хотите узнать информацию.

После каждого запроса типа ? считайте два целых числа value_i и next_i (0 ≤ value_i ≤ 10⁹,  - 1 ≤ next_i ≤ n, next_i ≠ 0).

Гарантируется, что если next_i ≠  - 1, то value_nexti > value_i, и что массив задает корректный односвязный список с началом в start.

Обратите внимание, что вы можете сделать не более 1999 запросов типа ?.

Если next_i =  - 1 и value_i =  - 1, это означает, что вы превысили максимальное число запросов или сделали некорректный запрос. Ваша программа должна немедленно завершиться (например, вызовом exit(0)). Вы получите вердикт «Неправильный ответ», и это будет означать, что вы превысили максимальное число запросов или задали некорректный запрос. Если вы проигнорируете это, то можете получить любой вердикт, так как ваша программа продолжит читать из закрытого потока ввода.

Выше решение получит вердикт «Решение зависло», если вы не будете ничего выводить или забудете сделать операцию flush после вывода вопроса или ответа.

Чтобы выполнить операцию flush, можете использовать (сразу после вывода запроса и перевода строки):

• fflush(stdout) в C++;
• System.out.flush() в Java;
• stdout.flush() в Python;
• flush(output) в Pascal;
• Для других языков смотрите документацию.

Формат взломов

Для взломов необходимо использовать следующий формат:

В первой строке выведите три числа n, start, x (1 ≤ n ≤ 50000, 1 ≤ start ≤ n, 0 ≤ x ≤ 10⁹).

В следующих n строках выведите описание ячеек списка: в i-й выведите два целых числа value_i и next_i (0 ≤ value_i ≤ 10⁹,  - 1 ≤ next_i ≤ n, next_i ≠ 0).

Данная структура должна быть корректным односвязным списком. В частности, из ячейки start должно было возможно посетить все ячейки, двигаясь в следующую ячейку next_i, а последняя ячейка end должна содержать -1 в качестве next_end.