Терези#13077

Терези

0,5 секунди
256 мегабайтів

У журі є старі терези і два секретні цілі числа та , де 0 \le a, b < 2^n, а число вам відоме. Ваше завдання — знайти обидва секретні числа.

Терези трохи незвичайні. Ви можете дати журі два цілі числа та (0 \le x, y < 2^n). Тоді журі кладе на ліву шальку число a \oplus x, а на праву — число b \oplus y, і повідомляє, яка шалька важча, або що терези врівноважені. Іншими словами, ви дізнаєтеся результат порівняння a \oplus x з b \oplus y. Тут позначає побітове виключне АБО (XOR).

Скористатися терезами можна не більше ніж разів.

Вхідні дані

Перший рядок містить одне ціле число (2 \le n \le 60).

Взаємодія

Щоб виконати зважування, виведіть рядок ? x y з двома цілими числами та (0 \le x, y < 2^n). У відповідь журі виведе рядок з одним символом:

  • <, якщо a \oplus x < b \oplus y;

  • =, якщо a \oplus x = b \oplus y;

  • >, якщо a \oplus x > b \oplus y.

Коли ви визначите секретні числа, виведіть рядок ! a b з числами та і завершіть роботу програми. Цей рядок не вважається зважуванням.

Після виведення кожного рядка не забудьте вивести символ кінця рядка та скинути буфер виводу (наприклад, fflush(stdout) або cout.flush() у C++, sys.stdout.flush() у Python, System.out.flush() у Java). Інакше ви можете отримати вердикт «Перевищено ліміт часу». Якщо ви виконаєте більше ніж зважувань, або зважування з числами поза допустимими межами, або виведете рядок у неправильному форматі, ви отримаєте вердикт «Неправильна відповідь».

Журі може бути адаптивним: числа та не зафіксовані заздалегідь і можуть залежати від ваших зважувань. Проте в кожен момент існує принаймні одна пара , яка узгоджується з усіма наданими відповідями. Тому виводьте відповідь лише тоді, коли пара визначена однозначно: якщо з усіма відповідями узгоджується ще якась інша пара, журі може вважати секретною саме її, і вашу відповідь буде визнано неправильною.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У прикладах у стовпчику вхідних даних наведено рядки, які виводить журі, а у стовпчику вихідних даних — рядки, які виводить ваша програма, у тому порядку, в якому відбувається обмін. Порожні рядки додано лише для вирівнювання стовпчиків; вони не є частиною взаємодії.

У першому прикладі n = 3, а секретні числа дорівнюють a = 5 та b = 3.

  • ? 0 0 порівнює a = 5 з b = 3, відповідь >;

  • ? 4 0 порівнює 5 \oplus 4 = 1 з , відповідь <;

  • ? 0 4 порівнює з 3 \oplus 4 = 7, відповідь <;

  • ? 4 2 порівнює 5 \oplus 4 з 3 \oplus 2, тобто з , відповідь =;

  • ? 4 3 порівнює 5 \oplus 4 з 3 \oplus 3, тобто з , відповідь >.

Щоб надати відповідь, програма виводить ! 5 3. Використано п'ять зважувань, тобто в межах ліміту .

У другому прикладі n = 2, a = 1, b = 3.

  • ? 0 0, відповідь <;

  • ? 0 2 порівнює з b \oplus 2, відповідь =;

  • ? 0 3 порівнює з b \oplus 3, відповідь >.

Використано три зважування, тобто в межах ліміту .