Неочікувана перемога#13000

Неочікувана перемога

2 секунди
512 мегабайтів
Дуже складна

Спайк і Джеррі вирішили організувати тенісний турнір серед котів, щоб визначити найкращого гравця. Кожна пара котів грає рівно один матч, і в кожному матчі рівно один кіт перемагає.

Кожен кіт має прихований рівень майстерності a_v, де масив є перестановкою чисел від до . Масив вам заздалегідь невідомий.

Використовуючи не більше ніж запитів, знайдіть будь-яку пару котів таку, що:

Якщо такої пари не існує, потрібно вивести .

Необхідно знайти пару для турнірів.

Вхідні дані

Взаємодія починається зі зчитування одного цілого числа — кількості турнірів.

Далі для кожного турніру:

У першому рядку задано ціле число — кількість котів.

У наступних рядках задано результати турніру 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.

Приклади

Приклад

Loading
Loading

Примітка

У наведеному нижче прикладі взаємодії n = 3, p = [1, 3, 2], g = {{010}, {001}, {100}}.

Ввід

Вивід

Пояснення

1

Задано .

3

Задано .

010

001

100

Задано .

? 1 3

Запитати, чи p_1 = 3.

0

Система перевірки відповідає «Ні».

? 1 1

Запитати, чи p_1 = 1.

1

Система перевірки відповідає «Так».

? 2 3

Запитати, чи p_2 = 3.

1

Система перевірки відповідає «Так».

! 1 2

Вивести відповідь. Неочікуваною перемогою є пара .

1

Система перевірки повідомляє, що відповідь правильна.