{"problem":{"name":"E2. Mexness (Hard Version)","description":{"content":"*This is the hard version of the problem. The only difference is the maximum number of queries.* *This is an interactive problem.* There is a secret permutation $p_0, p_1, \\\\dots, p_{n -1}$, which i","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFE2"},"statements":[{"statement_type":"Markdown","content":"*This is the hard version of the problem. The only difference is the maximum number of queries.*\n\n*This is an interactive problem.*\n\nThere is a secret permutation $p_0, p_1, \\\\dots, p_{n -1}$, which is a permutation of ${0, 1, \\\\dots, n -1}$. There is also a variable $m x$. At first, $m x = 4$.\n\nYour task is to guess the permutation by using queries of the following type:\n\nThe $\"mex\"(a)$ of an array $a$ is defined as the smallest non-negative integer that does not appear in $a$. For example, if $a = [ 0, 1, 2, 4 ]$, then $\"mex\"(a) = 3$ because $3$ is the smallest non-negative integer not present in $a$.\n\nFind out the secret permutation using at most $7 n$ queries of the second type.\n\nEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 200$). The description of the test cases follows.\n\nThe first line of each test case contains one integer $n$ ($2 <= n <= 1024$). It is guaranteed that the sum of $n$ over all test cases will not exceed $1024$.\n\nAt this moment, the permutation $p_0, p_1, \\\\dots, p_{n -1}$ is chosen. The interactor in this task is *not adaptive*. In other words, the sequence $p$ is fixed in every test case and does not change during the interaction.\n\nThen you can make queries.\n\nTo make a query of the first type, output a line in the format \"! $i$ $v$\" (without quotes). Note that this line is *not* included in the count of $7 n$ queries of the second type.\n\nTo make a query of the second type, output a line in the format \"? $k$ $j_1$ $j_2$ $\\\\dots$ $j_k$\" (without quotes) ($1 <= k <= n$, $0 <= j_i < n$). After each query, read an integer — the answer to your query.\n\nAfter performing $n$ queries of the first type (in other words, you have guessed the entire permutation $p$), if this is the last test case, the jury will terminate the program. Otherwise, the jury will output the next $n$.\n\nAfter printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the _Idleness limit exceeded verdict_. To flush, use:\n\nIn the first test case, the hidden permutation $p$ is $[ 2, 0, 1 ]$.\n\nFor the query \"_? 2 1 0_\", the jury returns $1$ because $min (m x, \"mex\"(p_1, p_0)) = min (4, 1) = 1$.\n\nThen, for answer \"_! 2 1_\", the jury increases $m x$ by $1$ since the answer is correct and you haven't answered for $p_2$ twice.\n\nFor the query \"_? 1 0_\", the jury returns $0$ because $min (m x, \"mex\"(p_0)) = min (5, 0) = 0$.\n\nNote queries are only for understanding statements and do *not* guarantee finding a unique permutation $p$.\n\n## Input\n\nEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 200$). The description of the test cases follows.\n\n## Interaction\n\nThe first line of each test case contains one integer $n$ ($2 <= n <= 1024$). It is guaranteed that the sum of $n$ over all test cases will not exceed $1024$.At this moment, the permutation $p_0, p_1, \\\\dots, p_{n -1}$ is chosen. The interactor in this task is *not adaptive*. In other words, the sequence $p$ is fixed in every test case and does not change during the interaction.Then you can make queries.To make a query of the first type, output a line in the format \"! $i$ $v$\" (without quotes). Note that this line is *not* included in the count of $7 n$ queries of the second type.To make a query of the second type, output a line in the format \"? $k$ $j_1$ $j_2$ $\\\\dots$ $j_k$\" (without quotes) ($1 <= k <= n$, $0 <= j_i < n$). After each query, read an integer — the answer to your query.After performing $n$ queries of the first type (in other words, you have guessed the entire permutation $p$), if this is the last test case, the jury will terminate the program. Otherwise, the jury will output the next $n$.After printing each line, do not forget to output the end of line and flush the output buffer. Otherwise, you will receive the _Idleness limit exceeded verdict_. To flush, use:  _fflush(stdout)_ or _cout.flush()_ in C++;  _System.out.flush()_ in Java;  _stdout.flush()_ in Python;  see the documentation for other languages. \n\n[samples]\n\n## Note\n\nIn the first test case, the hidden permutation $p$ is $[ 2, 0, 1 ]$.For the query \"_? 2 1 0_\", the jury returns $1$ because $min (m x, \"mex\"(p_1, p_0)) = min (4, 1) = 1$.Then, for answer \"_! 2 1_\", the jury increases $m x$ by $1$ since the answer is correct and you haven't answered for $p_2$ twice.For the query \"_? 1 0_\", the jury returns $0$ because $min (m x, \"mex\"(p_0)) = min (5, 0) = 0$.Note queries are only for understanding statements and do *not* guarantee finding a unique permutation $p$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"*Это сложная версия задачи. Единственное различие между двумя версиями — ограничение на количество различных $a$ в запросах. В этой версии различных чисел $a$ в запросах может быть не более двух.*\n\n*Это интерактивная задача.*\n\nВы с Эйприл О'Нил оказались в лаборатории Бакстера Стокмана и попали в ловушку. На вас наступает армия зубастых мышеловов. Единственный способ спастись: отгадать секретный код — число $p$ ($3 lt.eq p lt.eq 10^6$), с помощью которого их можно деактивировать. Эйприл работала в этой лаборатории, поэтому помнит, что число $p$ обязательно *простое*, ведь самые надёжные криптографические алгоритмы используют простые числа.\n\nВ панели управления мышеловами нашлась уязвимость. Она позволяет вам делать запросы «Сравнимо ли число $p$ по модулю $a$ с $d$?». Другими словами: «Верно ли, что $p -d$ делится нацело на $a$?». При этом $a$ и $d$ вы задаёте сами в каждом запросе.\n\nЕсли вы нарушите формат взаимодействия или сделаете *более* $1000$ запросов или спросите *более* двух различных чисел $a$, сработает защитный протокол _самоуничтожения_ мышеловов, и вам не поздоровится.\n\nПомогите Эйприл взломать панель управления и деактивировать мышеловов.\n\nВы можете сделать *не более* $1000$ запросов, включая вывод ответа.\n\nИнтерактор *не является* адаптивным, то есть число $p$ зафиксировано и *не меняется* с запросами.\n\nИнтерактор принимает запросы в следующем формате: \n\nВаши запросы должны содержать *не более* двух различных чисел $a$.\n\nПосле вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт _Решение «зависло»_. Если вы пишете на _C++_, жюри советует не подключать ускорение ввода/вывода и использовать _std::endl_ в качестве перевода строки.\n\nИнтерактор будет выдавать в ответ одно число: \n\nКогда вы готовы назвать число $p$ ($3 lt.eq p lt.eq 10^6$), выведите его в формате: \n\nПосле вывода секретного кода ваша программа должна немедленно завершиться, в противном случае жюри не гарантирует корректность вердикта.\n\n## Пример\n\nВходные данные\n? 2 1\n\n? 3 1\n\n? 3 2\n\n! 3\nВыходные данные\n1\n\n0\n\n0\n\n## Протокол Взаимодействия\n\nВы можете сделать *не более* $1000$ запросов, включая вывод ответа. Интерактор *не является* адаптивным, то есть число $p$ зафиксировано и *не меняется* с запросами. Интерактор принимает запросы в следующем формате:   _?_ $a$ $d$ ($2 lt.eq a lt.eq 2 dot.op 10^6$, $0 lt.eq d < a$) Ваши запросы должны содержать *не более* двух различных чисел $a$. После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт _Решение «зависло»_. Если вы пишете на _C++_, жюри советует не подключать ускорение ввода/вывода и использовать _std::endl_ в качестве перевода строки. Интерактор будет выдавать в ответ одно число:   $0$, если число $p$ *не сравнимо* с $d$ по модулю $a$;  $1$, в противном случае. Когда вы готовы назвать число $p$ ($3 lt.eq p lt.eq 10^6$), выведите его в формате:   _!_ $p$ После вывода секретного кода ваша программа должна немедленно завершиться, в противном случае жюри не гарантирует корректность вердикта.\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ p \\in \\mathbb{Z} $ be the secret prime number such that $ 3 \\leq p \\leq 10^6 $.  \nLet $ Q $ be the set of queries, each of the form $ (a, d) $, asking whether $ p \\equiv d \\pmod{a} $.  \n\n**Constraints**  \n1. At most **two distinct values** of $ a $ may be used across all queries.  \n2. Total number of queries (including final answer) is at most **1000**.  \n3. $ p $ is fixed and non-adaptive.  \n\n**Objective**  \nDetermine $ p $ using at most two distinct moduli $ a_1, a_2 $ and at most 1000 queries of the form $ p \\stackrel{?}{\\equiv} d \\pmod{a} $, then output $ p $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFE2","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}