CF2207H2 Bowser's Castle (Medium Version)

[ Bowser's Castle Corridor — Shiho Fujii, Ryo Nagamatsu, New Super Mario Bros. Wii ](https://www.youtube.com/watch?v=HCTQHn6Tk1o) This is the medium version of the problem. The difference between the versions is that in this version, $ n \leq 200 $ and you may make $ 10^4 $ queries. You can hack only if you solved all versions of this problem. This is an interactive problem. Let $ n $ be a positive integer. A function on $ n $ variables $ x_1, \ldots, x_n $ is called min-max if it can be constructed as writing only $ \min $ and $ \max $ calls around $ x_1, \ldots, x_n $ with each variable appearing exactly once in order from left to right in the expression. For example, $ \min(x_1, x_2, x_3) $ is a min-max function on $ 3 $ variables, but $ \max(\min(x_1, x_3), x_2) $ and $ \min(\max(x_1, x_2), \max(x_2, x_3)) $ are not. Bowser has chosen a min-max function on $ n $ ( $ 2 \leq n \leq 200 $ ) variables and tells you $ n $ . Additionally, he lets you ask queries of the following form: you give Bowser $ n $ integers $ x_1, \ldots, x_n $ ( $ 1 \leq x_i \leq 10^9 $ ) as input, and he tells you $ f(x_1, \ldots, x_n) $ . To escape his castle, you have to deduce his function using at most $ 10^4 $ queries in total. After that, to prove to him that you have learned the function, Bowser will give you up to $ 5000 $ of his own inputs $ x_1, \ldots, x_n $ , to which you must respond with the correct value of $ f(x_1, \ldots, x_n) $ . Since Bowser's castle is very secure, he actually has multiple functions for you to figure out, with a total variable count of at most $ 200 $ . Additionally, he constrains that you use at most $ 10^4 $ queries across all of the functions and that he will also not ask more than $ 5000 $ queries in total.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 200 $ ) — the number of variables in the min-max function. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 200 $ . After you read this line of input, the interaction begins with your first query.

N/A

In the first test case, Bowser's min-max function is $ f := \max(x_1, x_2, x_3) $ . After asking two queries to receive $ f(5, 4, 3) = 5 $ and $ f(1, 2, 1) = 2 $ from the jury, the solution is ready to answer the jury's queries. It correctly deduces that $ f(3, 6, 2) = 6 $ and $ f(3, 5, 7) = 7 $ . In the second test case, Bowser's min-max function is $ f := \min(\max(x_1, x_2), \max(x_3, x_4)) $ . After asking two queries to receive $ f(1, 9, 8, 7) = 8 $ and $ f(5, 10^9, 2, 3) = 3 $ from the jury, the solution is ready to answer the jury's queries. It correctly deduces that $ f(8, 7, 6, 5) = 6 $ . Note that it is not guaranteed that the queries in the example uniquely determine the min-max function. The example is there only to demonstrate how the queries work. Empty lines in the example input and output are given only for better readability; you don't need to output them in your solution.