Спайк і Джеррі вирішили організувати тенісний турнір серед котів, щоб визначити найкращого гравця. Кожна пара котів грає рівно один матч, і в кожному матчі рівно один кіт перемагає.
Кожен кіт має прихований рівень майстерності a_v, де масив є перестановкою чисел від до . Масив вам заздалегідь невідомий.
Використовуючи не більше ніж запитів, знайдіть будь-яку пару котів таку, що:
a_x < a_y, і
кіт переміг кота у турнірі.
Якщо такої пари не існує, потрібно вивести .
Необхідно знайти пару для турнірів.
Взаємодія починається зі зчитування одного цілого числа — кількості турнірів.
Далі для кожного турніру:
У першому рядку задано ціле число — кількість котів.
У наступних рядках задано результати турніру g_{i,j}. Кожен рядок містить двійковий рядок довжини , де:
g_{i,j} = \texttt{1} означає, що кіт переміг кота ,
g_{i,i} = \texttt{0} для всіх ,
для кожних i \ne j рівно одне з g_{i,j} та g_{j,i} дорівнює .
Ви можете ставити запити такого вигляду: ? v x, де 1 \le v, x \le n. Після кожного запиту зчитайте ціле число — відповідь системи перевірки:
, якщо a_v = x,
, якщо a_v \ne x,
, якщо ви припустилися помилки.
Після виведення кожного запиту не забудьте вивести символ нового рядка та очистити буфер виведення. Інтерактор є неадаптивним. Результати турніру не змінюються під час взаємодії.
1 \le t, n \le 100.
Для кожного турніру виведіть ! x y, коли знайдете пару . Пара також може дорівнювати .
Система перевірки відповість:
, якщо ваша відповідь правильна,
, якщо ваша відповідь неправильна.
Отже, якщо в будь-який момент ви отримаєте від системи перевірки -1, це означає, що ви припустилися помилки, і ваша програма повинна негайно завершити роботу, щоб отримати вердикт Wrong Answer.
Приклад
У наведеному нижче прикладі взаємодії n = 3, p = [1, 3, 2], g = {{010}, {001}, {100}}.
Ввід | Вивід | Пояснення |
| Задано . | |
| Задано . | |
| ||
| ||
| Задано . | |
| Запитати, чи p_1 = 3. | |
| Система перевірки відповідає «Ні». | |
| Запитати, чи p_1 = 1. | |
| Система перевірки відповідає «Так». | |
| Запитати, чи p_2 = 3. | |
| Система перевірки відповідає «Так». | |
| Вивести відповідь. Неочікуваною перемогою є пара . | |
| Система перевірки повідомляє, що відповідь правильна. |