Это интерактивная задача!
Настя загадала перестановку \(p\) длины \(n\), состоящую из элементов от \(1\) до \(n\). Неизвестно по какой причине вы хотите восстановить перестановку. Для того, чтобы сделать это, вы даете Насте целое число \(t\) (\(1 \le t \le 2\)), два различных индекса \(i\) и \(j\) (\(1 \le i, j \le n\), \(i \neq j\)) и целое число \(x\) (\(1 \le x \le n - 1\)).
В зависимости от \(t\) она ответит:
- \(t = 1\): \(\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}\);
- \(t = 2\): \(\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}\).
Вы можете спросить Настю не более \(\lfloor \frac {3 \cdot n} { 2} \rfloor + 30\) раз. Гарантируется, что она не будет менять перестановку в зависимости от ваших вопросов. Удастся ли вам восстановить перестановку?
Протокол взаимодействия
Чтобы задать вопрос, выведите «? \(t\) \(i\) \(j\) \(x\)» (\(t = 1\) или \(t = 2\), \(1 \le i, j \le n\), \(i \neq j\), \(1 \le x \le n - 1\)). Затем вы должны считать ответ.
Если мы ответим \(−1\) вместо правильного ответа, это означает, что вы превысили количество запросов или сделали неверный запрос. Завершите программу сразу после получения \(−1\), и вы увидите вердикт Неправильный ответ. В противном случае вы можете получить произвольный вердикт, потому что ваше решение будет продолжать читать из закрытого потока.
Чтобы дать ответ, выведите «! \(p_1\) \(p_2\) \(\ldots\) \(p_{n}\)» (без кавычек). Заметьте, что вывод ответа не считается одним из \(\lfloor \frac {3 \cdot n} {2} \rfloor + 30\) запросов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- Cмотрите документацию для других языков.
Взломы
Чтобы сделать взлом, используйте следующий формат теста:
В первой строке должно находиться единственное целое число \(T\) (\(1 \le T \le 10\,000\)) — количество наборов входных данных.
Для каждого набора входных данных в первой строке выведите целое число \(n\) (\(3 \le n \le 10^4\)) — длина загаданной перестановки \(p\).
Во второй строке выведите \(n\) разделенных пробелами целых чисел \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\)), где \(p\) является перестановкой.
При этом сумма \(n\) по всем наборам должна не превосходить \(2 \cdot 10^4\).
Примечание
Рассмотрим первый набор входных данных. Загаданной перестановкой является \([3, 1, 4, 2]\).
Мы выводим «? \(2\) \(4\) \(1\) \(3\)» и получаем в ответ \(\min{(\max{(3, p_4}), \max{(4, p_1)})} = 3\).
Мы выводим «? \(1\) \(2\) \(4\) \(2\)» и получаем в ответ \(\max{(\min{(2, p_2)}, \min{(3, p_4)})} = 2\).
Рассмотрим второй набор входных данных. Загаданной перестановкой является \([2, 5, 3, 4, 1]\).
Мы выводим «? \(2\) \(3\) \(4\) \(2\)» и получаем в ответ \(\min{(\max{(2, p_3}), \max{(3, p_4)})} = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
3
2
5
3
|
? 2 4 1 3
? 1 2 4 2
! 3 1 4 2
? 2 3 4 2
! 2 5 3 4 1
|