Kurumi just found a particularly nasty cipher on the internet and she needs your help!
The cipher takes the shape of a permutation of length
. According to information she got from the dark web, the solution to the cipher revolves around what is known as a
-insert.
Specifically, a -insert of the integer
is a two step process:
- Step 1: the integer
is removed from
.
- Step 2: the integer
is inserted after the
-th element in the modified
. In particular, if
, it is inserted at the beginning.
A solution to the cipher is a sequence of
-inserts that turns
into the identity permutation. In particular, a
-insert of the integer
is performed as the
-th action.
In the interest of time, Kurumi wants to know the shortest possible solution. Can you help Kurumi find the shortest possible ? To ensure the integrity of your solution, there may be up to
test cases.
Constraints
The array forms a permutation of the integers
.
The sum of over all test cases does not exceed
.
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
Input Specification
The first line contains an integer , the number of test cases. The remaining
lines describe the test cases.
The first line of each test case contains integers,
and
.
The second line of each test case contains space-separated integers, representing the permutation
.
Output Specification
For each test case, output two lines.
On the first line, output a single integer , representing the length of
.
On the second line, output space-separated integers, representing the solution
.
If there are multiple possible solutions, output any one of them.
This problem is graded with a standard checker, so if , you may output an empty line, no line, or a line containing just whitespace.
Scoring
For each case within a test, if your output is ill-formatted or your sequence is not a solution, you will receive
of the points for that case.
Otherwise, let be the length of the shortest solution.
- If
, you will receive
of the points for that case.
- If
, you will receive
of the points for that case.
Your score for a case will be the minimum of the scores of all the tests in the case. Your score for a batch is the minimum of the scores of all of the tests in the batch.
Sample Input
1
4 1
2 3 4 1
Sample Output
2
1 2
Explanation for Sample
After the first -insert, the permutation becomes
.
After the second -insert, the permutation becomes
.
It can be proven that a solution of shorter length does not exist, so this solution would receive of the points for this case.
Comments