Hard Performance Measurement (A+B)

题目描述

This is an interactive problem.

The interactor will first give you an integer $n$. You need to output an positive integer $x$ and a strictly increasing positive integer array $a_{1\dots n}$. You must ensure that there do NOT exist two distinct elements in $a_{1\dots n}$ whose sum is $x$.

Then, the interactor will give you an index $i$ between $i$ and $n$, and you need to change $a_i$ to another positive integer, such that after the modification, $a_{1\dots n}$ is still strictly increasing, but there exist two distinct elements whose sum is $x$.

Both $x$ and all the elements in $a_{1\dots n}$ should not exceed $10^9$.

输入格式

The input contains several test cases.

The first line of the input contains a single integer $T$, the number of test cases.

For each test case:

• The interactor provides a line first with integer $n$.
• Your program must output exactly three lines:
  • Line 1: the integer $x$.
  • Line 2: $n$ space-separated integers $a_1,a_2,\dots ,a_n$.
  • After printing the two lines above, the interactor sends a line containing integer $i$. Your program must then output Line 3: a single integer $a_i$, the new value assigned to $a_i$.

Remember to flush the output buffer after each print (e.g., fflush(stdout) in C/C++, sys.stdout.flush() in Python, cout.flush() in C++).

It's guaranteed that $1\leq T\leq 10^6$, $2\leq n\leq 10^6$ and $\sum n\leq 10^6$.

样例输入 #1

2

3
2

4
1

样例输出 #1

6
1 4 9
5

7
1 4 7 10
3