#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using PQR = priority_queue<T, vector<T>, greater<T>>;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 + 99);
const ld PI = acos((ld)-1);
constexpr ll dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
template <typename T, typename U>
inline bool chmin(T& t, const U& u) {
  if (t > u) {
    t = u;
    return 1;
  }
  return 0;
}
template <typename T, typename U>
inline bool chmax(T& t, const U& u) {
  if (t < u) {
    t = u;
    return 1;
  }
  return 0;
}
template <typename T>
inline T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
inline void Yes() { cout << "Yes" << '\n'; }
inline void No() { cout << "No" << '\n'; }
inline void YES() { cout << "YES" << '\n'; }
inline void NO() { cout << "NO" << '\n'; }
template <typename T, typename Y>
inline T mpow(T a, Y n) {
  T res = 1;
  for (; n; n >>= 1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}
template <typename T>
vector<T> finddivisor(T x) {
  vector<T> divisor;
  for (T i = 1; (i * i) <= x; i++) {
    if (x % i == 0) {
      divisor.push_back(i);
      if (i * i != x) {
        divisor.push_back(x / i);
      }
    }
  }
  sort(divisor.begin(), divisor.end());
  return divisor;
}
template <typename T>
V<T> prefix_sum(const V<T>& v) {
  int n = v.size();
  V<T> ret(n + 1);
  for (ll i = 0; i < (ll)(n); ++i) ret[i + 1] = ret[i] + v[i];
  return ret;
}
template <typename T>
T rand(T l, T r) {
  static random_device rd;
  static mt19937 g(rd());
  return uniform_int_distribution<T>(l, r)(g);
}
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (auto&& x : vec) is >> x;
  return is;
}
template <typename T, typename Y>
ostream& operator<<(ostream& os, const pair<T, Y>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <typename T>
ostream& operator<<(ostream& os, const V<T>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
template <typename... Args>
void debug(Args&... args) {
  for (auto const& x : {args...}) {
    cerr << x << ' ';
  }
  cerr << '\n';
}
template <typename T>
struct UnionFind {
  vector<T> Parent;
  UnionFind(T N) { Parent = vector<T>(N, -1); }
  T root(T A) {
    if (Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }
  T size(T A) { return -Parent[root(A)]; }
  bool connect(T A, T B) {
    A = root(A);
    B = root(B);
    if (A == B) return false;
    if (size(A) < size(B)) swap(A, B);
    Parent[A] += Parent[B];
    Parent[B] = A;
    return true;
  }
  bool same(T A, T B) { return root(A) == root(B); }
};
ll f(int rot, V<ll> p) {
  rotate(p.begin(), p.begin() + rot, p.end());
  ll n = (ll)(p).size();
  UnionFind<int> u(n);
  ll ans = 0;
  for (ll i = 0; i < (ll)(n); ++i)
    if (u.connect(i, p[i])) ans++;
  return ans;
}
signed main() {
  cin.tie(0);
  cerr.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int qq;
  cin >> qq;
  while (qq--) {
    ll n, m;
    cin >> n >> m;
    V<ll> p(n);
    cin >> p;
    for (ll i = 0; i < (ll)(n); ++i) p[i]--;
    V<ll> cnt(n, 0);
    for (ll i = 0; i < (ll)(n); ++i) {
      cnt[(i - p[i] + n) % n]++;
    }
    V<ll> ans(0);
    for (ll i = 0; i < (ll)(n); ++i) {
      if (cnt[i] == n)
        ans.push_back(i);
      else if ((n - cnt[i] + 1) / 2 <= m) {
        if (f(i, p) <= m) ans.push_back(i);
      }
    }
    cout << (ll)(ans).size() << " ";
    for (auto&& i : ans) cout << i << " ";
    cout << '\n';
  }
}

### Prompt

Please create a solution in CPP to the following problem:

An identity permutation of length n is an array [1, 2, 3, ..., 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 ≤ k ≤ 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 ≤ t ≤ 10^5) — the number of test cases.

Each test case consists of two lines. The first line contains two integers n and m (3 ≤ n ≤ 3 ⋅ 10^5; 0 ≤ m ≤ n/3).

The second line contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ 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 ⋅ 10^5.

Output

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

  * firstly, print one integer r (0 ≤ r ≤ n) — the number of possible values of k for the cyclic shift operation; 
  * secondly, print r integers k_1, k_2, ..., k_r (0 ≤ k_i ≤ 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]. 

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using PQR = priority_queue<T, vector<T>, greater<T>>;
constexpr ll mod = 1000000007;
constexpr ll INF = 1000000099;
constexpr ll LINF = (ll)(1e18 + 99);
const ld PI = acos((ld)-1);
constexpr ll dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
template <typename T, typename U>
inline bool chmin(T& t, const U& u) {
  if (t > u) {
    t = u;
    return 1;
  }
  return 0;
}
template <typename T, typename U>
inline bool chmax(T& t, const U& u) {
  if (t < u) {
    t = u;
    return 1;
  }
  return 0;
}
template <typename T>
inline T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
inline void Yes() { cout << "Yes" << '\n'; }
inline void No() { cout << "No" << '\n'; }
inline void YES() { cout << "YES" << '\n'; }
inline void NO() { cout << "NO" << '\n'; }
template <typename T, typename Y>
inline T mpow(T a, Y n) {
  T res = 1;
  for (; n; n >>= 1) {
    if (n & 1) res = res * a;
    a = a * a;
  }
  return res;
}
template <typename T>
vector<T> finddivisor(T x) {
  vector<T> divisor;
  for (T i = 1; (i * i) <= x; i++) {
    if (x % i == 0) {
      divisor.push_back(i);
      if (i * i != x) {
        divisor.push_back(x / i);
      }
    }
  }
  sort(divisor.begin(), divisor.end());
  return divisor;
}
template <typename T>
V<T> prefix_sum(const V<T>& v) {
  int n = v.size();
  V<T> ret(n + 1);
  for (ll i = 0; i < (ll)(n); ++i) ret[i + 1] = ret[i] + v[i];
  return ret;
}
template <typename T>
T rand(T l, T r) {
  static random_device rd;
  static mt19937 g(rd());
  return uniform_int_distribution<T>(l, r)(g);
}
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (auto&& x : vec) is >> x;
  return is;
}
template <typename T, typename Y>
ostream& operator<<(ostream& os, const pair<T, Y>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <typename T>
ostream& operator<<(ostream& os, const V<T>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
template <typename... Args>
void debug(Args&... args) {
  for (auto const& x : {args...}) {
    cerr << x << ' ';
  }
  cerr << '\n';
}
template <typename T>
struct UnionFind {
  vector<T> Parent;
  UnionFind(T N) { Parent = vector<T>(N, -1); }
  T root(T A) {
    if (Parent[A] < 0) return A;
    return Parent[A] = root(Parent[A]);
  }
  T size(T A) { return -Parent[root(A)]; }
  bool connect(T A, T B) {
    A = root(A);
    B = root(B);
    if (A == B) return false;
    if (size(A) < size(B)) swap(A, B);
    Parent[A] += Parent[B];
    Parent[B] = A;
    return true;
  }
  bool same(T A, T B) { return root(A) == root(B); }
};
ll f(int rot, V<ll> p) {
  rotate(p.begin(), p.begin() + rot, p.end());
  ll n = (ll)(p).size();
  UnionFind<int> u(n);
  ll ans = 0;
  for (ll i = 0; i < (ll)(n); ++i)
    if (u.connect(i, p[i])) ans++;
  return ans;
}
signed main() {
  cin.tie(0);
  cerr.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  int qq;
  cin >> qq;
  while (qq--) {
    ll n, m;
    cin >> n >> m;
    V<ll> p(n);
    cin >> p;
    for (ll i = 0; i < (ll)(n); ++i) p[i]--;
    V<ll> cnt(n, 0);
    for (ll i = 0; i < (ll)(n); ++i) {
      cnt[(i - p[i] + n) % n]++;
    }
    V<ll> ans(0);
    for (ll i = 0; i < (ll)(n); ++i) {
      if (cnt[i] == n)
        ans.push_back(i);
      else if ((n - cnt[i] + 1) / 2 <= m) {
        if (f(i, p) <= m) ans.push_back(i);
      }
    }
    cout << (ll)(ans).size() << " ";
    for (auto&& i : ans) cout << i << " ";
    cout << '\n';
  }
}

```