У журі є старі терези і два секретні цілі числа та , де 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
Приклад 2
У прикладах у стовпчику вхідних даних наведено рядки, які виводить журі, а у стовпчику вихідних даних — рядки, які виводить ваша програма, у тому порядку, в якому відбувається обмін. Порожні рядки додано лише для вирівнювання стовпчиків; вони не є частиною взаємодії.
У першому прикладі 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, відповідь >.
Використано три зважування, тобто в межах ліміту .