Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Permutation Shift

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAn identity permutation of length $$$n$$$ is an array $$$[1, 2, 3, \dots, n]$$$.

We performed the following operations to an identity permutation of length $$$n$$$:

- firstly, we cyclically shifted it to the right by $$$k$$$ positions, where $$$k$$$ is unknown to you (the only thing you know is that $$$0 \le k \le n - 1$$$). When an array is cyclically shifted to the right by $$$k$$$ positions, the resulting array is formed by taking $$$k$$$ last elements of the original array (without changing their relative order), and then appending $$$n - k$$$ first elements to the right of them (without changing relative order of the first $$$n - k$$$ elements as well). For example, if we cyclically shift the identity permutation of length $$$6$$$ by $$$2$$$ positions, we get the array $$$[5, 6, 1, 2, 3, 4]$$$;
- secondly, we performed the following operation at most $$$m$$$ times: pick any two elements of the array and swap them.

You are given the values of $$$n$$$ and $$$m$$$, and the resulting array. Your task is to find all possible values of $$$k$$$ in the cyclic shift operation.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each test case consists of two lines. The first line contains two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 3 \cdot 10^5$$$; $$$0 \le m \le \frac{n}{3}$$$).

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, each integer from $$$1$$$ to $$$n$$$ appears in this sequence exactly once) — the resulting array.

The sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print the answer in the following way:

- firstly, print one integer $$$r$$$ ($$$0 \le r \le n$$$) — the number of possible values of $$$k$$$ for the cyclic shift operation;
- secondly, print $$$r$$$ integers $$$k_1, k_2, \dots, k_r$$$ ($$$0 \le k_i \le n - 1$$$) — all possible values of $$$k$$$ in increasing order.

Example

Input

4 4 1 2 3 1 4 3 1 1 2 3 3 1 3 2 1 6 0 1 2 3 4 6 5

Output

1 3 1 0 3 0 1 2 0

Note

Consider the example:

- in the first test case, the only possible value for the cyclic shift is $$$3$$$. If we shift $$$[1, 2, 3, 4]$$$ by $$$3$$$ positions, we get $$$[2, 3, 4, 1]$$$. Then we can swap the $$$3$$$-rd and the $$$4$$$-th elements to get the array $$$[2, 3, 1, 4]$$$;
- in the second test case, the only possible value for the cyclic shift is $$$0$$$. If we shift $$$[1, 2, 3]$$$ by $$$0$$$ positions, we get $$$[1, 2, 3]$$$. Then we don't change the array at all (we stated that we made at most $$$1$$$ swap), so the resulting array stays $$$[1, 2, 3]$$$;
- in the third test case, all values from $$$0$$$ to $$$2$$$ are possible for the cyclic shift:
- if we shift $$$[1, 2, 3]$$$ by $$$0$$$ positions, we get $$$[1, 2, 3]$$$. Then we can swap the $$$1$$$-st and the $$$3$$$-rd elements to get $$$[3, 2, 1]$$$;
- if we shift $$$[1, 2, 3]$$$ by $$$1$$$ position, we get $$$[3, 1, 2]$$$. Then we can swap the $$$2$$$-nd and the $$$3$$$-rd elements to get $$$[3, 2, 1]$$$;
- if we shift $$$[1, 2, 3]$$$ by $$$2$$$ positions, we get $$$[2, 3, 1]$$$. Then we can swap the $$$1$$$-st and the $$$2$$$-nd elements to get $$$[3, 2, 1]$$$;

- in the fourth test case, we stated that we didn't do any swaps after the cyclic shift, but no value of cyclic shift could produce the array $$$[1, 2, 3, 4, 6, 5]$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/30/2023 07:12:58 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|