{"problem":{"name":"K. Kostly Cueries","description":{"content":"_This is an interactive problem._ Lowie went to a Science fair. His favorite section in the fair is the \"interaction\" zone, where people spend money to play games and win prizes in different booths. ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10227K"},"statements":[{"statement_type":"Markdown","content":"_This is an interactive problem._\n\nLowie went to a Science fair. His favorite section in the fair is the \"interaction\" zone, where people spend money to play games and win prizes in different booths.\n\nLowie went to the _Prime_ booth, where he can win *sorted* prime array. The boothkeeper B21 kept a prime array secret from Lowie, and he have to guess the whole array by buying queries from B21.\n\nFor each queries, Lowie can ask for a subsegment (i.e.: a series of consecutive elements) $[ l, r ]$ in the array, B21 will return him with the product of all elements in the subsegment, modulo $10^9 + 9$. A query for a subsegment $[ l, r ]$ will cost Lowie exactly $frac(1, (r -l + 1)^2)$ BTC.\n\nLowie only have $0. 45$ BTC, help him win the Prime array. Please notice that the array is _sorted_, and you can ask as many queries as you want, as long as the total cost doesn't exceed the amount that Lowie has.\n\nOh, and the boothkeeper B21 doesn't like big numbers, so his array will consists only primes in the range of $[ 1, 10^4 ]$.\n\nRead an integer $N$ - length of the array. $2 <= N <= 500$.\n\nYou can make queries of type \"_? l r_\" to ask B21 the product of all elements in the segment $[ l, r ]$ ($1 <= l <= r <= N$) modulo $10^9 + 9$.\n\nAfter the query read its result as an integer. If you read $-1$, that means your query is not correct, or you have exceeded the total amount of money that you have. Exit the program immediately to get the verdict \"Wrong answer\". If you don't, you might get an arbitrary verdicts.\n\nWhen you find out the array, print \"$!$\" followed by a space. Then, print $N$ integers, separated by spaces. This is not counted as a query and will have the cost of $0$, but you only have one guess. If you failed to get the answer right, your verdict will be \"Wrong answer\".\n\nAfter printing any query do not forget to output end of line and flush the output. Otherwise you will get _Idleness limit exceeded_. To do this, use:\n\n_fflush(stdout)_ or _cout.flush()_ in C++;\n\n_System.out.flush()_ in Java;\n\n_flush(output)_ in Pascal;\n\n_stdout.flush()_ in Python.\n\n*Example 1:*\n\nAsk for query: $[ 1, 5 ]$, get the answer of $14322$. \n\nAsk for query: $[ 4, 5 ]$, get the answer of $341$.\n\nSomehow got the answer right :/\n\n## Input\n\nRead an integer $N$ - length of the array. $2 <= N <= 500$.\n\n## Interaction\n\nYou can make queries of type \"_? l r_\" to ask B21 the product of all elements in the segment $[ l, r ]$ ($1 <= l <= r <= N$) modulo $10^9 + 9$.After the query read its result as an integer. If you read $-1$, that means your query is not correct, or you have exceeded the total amount of money that you have. Exit the program immediately to get the verdict \"Wrong answer\". If you don't, you might get an arbitrary verdicts.When you find out the array, print \"$!$\" followed by a space. Then, print $N$ integers, separated by spaces. This is not counted as a query and will have the cost of $0$, but you only have one guess. If you failed to get the answer right, your verdict will be \"Wrong answer\".After printing any query do not forget to output end of line and flush the output. Otherwise you will get _Idleness limit exceeded_. To do this, use:_fflush(stdout)_ or _cout.flush()_ in C++;_System.out.flush()_ in Java;_flush(output)_ in Pascal;_stdout.flush()_ in Python.\n\n[samples]\n\n## Note\n\n*Example 1:*Ask for query: $[ 1, 5 ]$, get the answer of $14322$. Ask for query: $[ 4, 5 ]$, get the answer of $341$.Somehow got the answer right :/","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the length of the secret array $ A = (a_1, a_2, \\dots, a_N) $, where each $ a_i $ is a prime number in $ [2, 10^4] $, and $ A $ is sorted: $ a_1 \\leq a_2 \\leq \\dots \\leq a_N $.  \nLet $ M = 10^9 + 9 $.  \nLet $ Q $ be the set of queries made, each query is a subsegment $ [l, r] $ with cost $ \\frac{1}{(r - l + 1)^2} $.  \nTotal cost constraint: $ \\sum_{[l,r] \\in Q} \\frac{1}{(r - l + 1)^2} \\leq 0.45 $.  \n\n**Constraints**  \n1. $ 2 \\leq N \\leq 500 $  \n2. Each $ a_i $ is prime and $ 2 \\leq a_i \\leq 10^4 $  \n3. $ A $ is non-decreasing  \n4. For any query $ [l, r] $, the response is $ \\prod_{i=l}^r a_i \\mod M $  \n5. Total query cost $ \\leq 0.45 $ BTC  \n\n**Objective**  \nRecover the exact array $ A $ using queries such that the total cost does not exceed 0.45 BTC, then output $ !\\ a_1\\ a_2\\ \\dots\\ a_N $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10227K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}