CF2129F2 Top-K Tracker (Hard Version)

This is an interactive problem. This is the hard version of the problem. The only difference is that $ n \le 890 $ in this version. You can make hacks only if all versions of the problem are solved. There is a hidden permutation $ p $ , which is a permutation of $ \{1,2,\ldots,n\} $ . Let $ pos_i $ denote the position of the value $ i $ in $ p $ , i.e., $ pos_{p_i} = i $ . To find this permutation, you can ask four types of queries: - " $ 1\ m\ i_1\ i_2\ \ldots\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1,\ i_2,\ \ldots,\ i_m $ must be distinct). Let $ k = \min(60, m) $ . The jury will return the top $ k $ largest number(s) in $ [p_{i_1}, p_{i_2}, \ldots, p_{i_m}] $ in increasing order. - " $ 2\ m\ i_1\ i_2\ \ldots\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1,\ i_2,\ \ldots,\ i_m $ must be distinct). Let $ k = \min(60, m) $ . The jury will return the top $ k $ largest number(s) in $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ in increasing order. - " $ 3\ m\ i_1\ i_2\ ...\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1,\ i_2,\ ...,\ i_m $ must be distinct). Let $ k = \min(300, m) $ . The jury will return the top $ k $ largest number(s) in $ [p_{i_1}, p_{i_2}, ..., p_{i_m}] $ in increasing order. - " $ 4\ m\ i_1\ i_2\ \ldots\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1,\ i_2,\ \ldots,\ i_m $ must be distinct). Let $ k = \min(300, m) $ . The jury will return the top $ k $ largest number(s) in $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ in increasing order. Let $ c_i $ be the usage count of queries of type $ i $ $ (1 \le i \le 4) $ . Your query count must satisfy the following constraints: - $ c_1+c_2+c_3+c_4 \le 30. $ - $ c_3+c_4 \le 1. $

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 40 $ ). The description of the test cases follows.

The first line of each test case contains one integer $ n $ ( $ 2 \le n \le 890 $ ). At this moment, the permutation $ p $ is chosen. The interactor in this task is not adaptive. In other words, the permutation $ p $ is fixed in every test case and does not change during the interaction. To ask a query of type $ 1 $ , you need to print the line of the following form (without quotes): - " $ 1\ m\ i_1\ i_2\ \ldots\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1, i_2, \ldots, i_m $ must be distinct) After that, you receive $ k=\min(60,m) $ integer(s) — the top $ k $ largest number(s) in $ [p_{i_1}, p_{i_2}, \ldots, p_{i_m}] $ in increasing order. To ask a query of type $ 2 $ , you need to print the line of the following form (without quotes): - " $ 2\ m\ i_1\ i_2\ \ldots\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1, i_2, \ldots, i_m $ must be distinct) After that, you receive $ k=\min(60,m) $ integer(s) — the top $ k $ largest number(s) in $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ in increasing order. To ask a query of type $ 3 $ , you need to print the line of the following form (without quotes): - " $ 3\ m\ i_1\ i_2\ \ldots\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1, i_2, \ldots, i_m $ must be distinct) After that, you receive $ k=\min(300,m) $ integer(s) — the top $ k $ largest number(s) in $ [p_{i_1}, p_{i_2}, \ldots, p_{i_m}] $ in increasing order. To ask a query of type $ 4 $ , you need to print the line of the following form (without quotes): - " $ 4\ m\ i_1\ i_2\ \ldots\ i_m $ " ( $ 1 \leq m \leq n $ , $ i_1, i_2, \ldots, i_m $ must be distinct) After that, you receive $ k=\min(300,m) $ integer(s) — the top $ k $ largest number(s) in $ [pos_{i_1}, pos_{i_2}, \ldots, pos_{i_m}] $ in increasing order. Next, if your program has found the permutation $ p $ , print the line of the following form (without quotes): - " $ !\ p_1\ p_2\ \ldots\ p_n $ " Note that this line is not considered a query and is not taken into account when counting the number of queries asked. After this, proceed to the next test case. After printing a query or the answer for a test case, do not forget to output the end of the line and flush the output. Otherwise, you will get the verdict 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; - see the documentation for other languages. Hacks To hack, follow the test format below. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 40 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 2 \le n \le 890 $ ). The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n $ , which is a permutation of $ \{1,2,\ldots,n\} $ .

In the first test case, the hidden permutation is $ p = [3, 1, 2] $ . Thus, $ pos = [2, 3, 1] $ . For the query "3 2 3 1", the jury returns $ 2 $ and $ 3 $ because $ 2 $ and $ 3 $ are the top $ k $ largest number(s) in $ [p_3, p_1] $ , where $ k = \min(300, m) = \min(300, 2) = 2 $ . For the query "2 1 2", the jury returns $ 3 $ because $ 3 $ is the top $ k $ largest number in $ [pos_2] $ , where $ k = \min(60, m) = \min(60, 1) = 1 $ . Note that the example is only for understanding the statement and does not guarantee finding the unique permutation $ p $ .