#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 200000;
int n, lim;
int a[MAXN];
int b[MAXN];
bool isfixed[MAXN];
pair<int, int> o[MAXN];
int no;
int dst[MAXN];
int cyc[MAXN], ncyc;
int par[MAXN], sz[MAXN];
int find(int a) {
  if (par[a] == a) return a;
  return par[a] = find(par[a]);
}
bool unite(int a, int b) {
  a = find(a), b = find(b);
  if (a == b) return false;
  if (sz[a] < sz[b]) swap(a, b);
  par[b] = a, sz[a] += sz[b];
  return true;
}
bool done[MAXN];
vector<vector<int>> ans;
bool solve() {
  for (int i = (0); i < (n); ++i) b[i] = a[i];
  sort(b, b + n);
  int nfixed = 0;
  for (int i = (0); i < (n); ++i) {
    isfixed[i] = a[i] == b[i];
    if (isfixed[i]) ++nfixed;
  }
  if (n - nfixed > lim) return false;
  no = 0;
  for (int i = (0); i < (n); ++i)
    if (!isfixed[i]) o[no++] = make_pair(a[i], i);
  sort(o, o + no);
  for (int i = (0); i < (n); ++i) dst[i] = isfixed[i] ? i : -1;
  {
    int at = 0;
    for (int i = (0); i < (no); ++i) {
      while (at < n && isfixed[at]) ++at;
      dst[o[i].second] = at++;
    }
  }
  for (int i = (0); i < (n); ++i) cyc[i] = -1;
  ncyc = 0;
  for (int i = (0); i < (n); ++i)
    if (cyc[i] == -1 && dst[i] != i) {
      int at = i;
      while (cyc[at] == -1) {
        cyc[at] = ncyc;
        at = dst[at];
      }
      ++ncyc;
    }
  int expect = ncyc;
  for (int i = (0); i < (ncyc); ++i) par[i] = i, sz[i] = 1;
  for (int l = 0, r = l; l < no; l = r) {
    while (r < no && o[l].first == o[r].first) ++r;
    int cur = o[l].second;
    for (int i = (l + 1); i < (r); ++i) {
      int oth = o[i].second;
      if (unite(cyc[cur], cyc[oth])) {
        swap(dst[cur], dst[oth]);
        --expect;
      }
    }
  }
  for (int i = (0); i < (n); ++i) done[i] = false;
  ans.clear();
  for (int i = (0); i < (n); ++i)
    if (!done[i] && dst[i] != i) {
      ans.push_back(vector<int>());
      int at = i;
      while (!done[at]) {
        done[at] = true;
        ans.back().push_back(at);
        at = dst[at];
      }
    }
  assert(((int)(ans).size()) == expect);
  int rem = lim - (n - nfixed);
  if (((int)(ans).size()) >= 3 && rem >= 3) {
    int cnt = min(rem, ((int)(ans).size()));
    vector<int> fst(cnt);
    for (int i = (0); i < (cnt); ++i) fst[i] = ans[i][0];
    reverse(fst.begin(), fst.end());
    vector<int> snd;
    for (int i = (0); i < (cnt); ++i) {
      snd.push_back(ans[i][0]);
      int j = (i + 1) % cnt;
      for (int k = (1); k < (((int)(ans[j]).size())); ++k)
        snd.push_back(ans[j][k]);
    }
    vector<vector<int>> nans;
    nans.push_back(fst);
    nans.push_back(snd);
    for (int i = (cnt); i < (((int)(ans).size())); ++i) nans.push_back(ans[i]);
    ans = nans;
  }
  return true;
}
bool verify(vector<vector<int>> ans) {
  vector<int> cur(n);
  for (int i = (0); i < (n); ++i) cur[i] = a[i];
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    int val = cur[ans[i][0]];
    for (int j = (1); j < (((int)(ans[i]).size())); ++j)
      swap(val, cur[ans[i][j]]);
    cur[ans[i][0]] = val;
  }
  for (int i = (1); i < (((int)(cur).size())); ++i)
    if (cur[i] < cur[i - 1]) return false;
  return true;
}
void run() {
  scanf("%d%d", &n, &lim);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  if (!solve()) {
    printf("-1\n");
    return;
  }
  printf("%d\n", ((int)(ans).size()));
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    printf("%d\n", ((int)(ans[i]).size()));
    for (int j = (0); j < (((int)(ans[i]).size())); ++j) {
      if (j != 0) printf(" ");
      printf("%d", ans[i][j] + 1);
    }
    puts("");
  }
  assert(verify(ans));
}
int main() {
  run();
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

You are given an array of n positive integers a_1, a_2, ..., a_n. You can perform the following operation any number of times: select several distinct indices i_1, i_2, ..., i_k (1 ≤ i_j ≤ n) and move the number standing at the position i_1 to the position i_2, the number at the position i_2 to the position i_3, ..., the number at the position i_k to the position i_1. In other words, the operation cyclically shifts elements: i_1 → i_2 → … i_k → i_1.

For example, if you have n=4, an array a_1=10, a_2=20, a_3=30, a_4=40, and you choose three indices i_1=2, i_2=1, i_3=4, then the resulting array would become a_1=20, a_2=40, a_3=30, a_4=10.

Your goal is to make the array sorted in non-decreasing order with the minimum number of operations. The additional constraint is that the sum of cycle lengths over all operations should be less than or equal to a number s. If it's impossible to sort the array while satisfying that constraint, your solution should report that as well.

Input

The first line of the input contains two integers n and s (1 ≤ n ≤ 200 000, 0 ≤ s ≤ 200 000)—the number of elements in the array and the upper bound on the sum of cycle lengths.

The next line contains n integers a_1, a_2, ..., a_n—elements of the array (1 ≤ a_i ≤ 10^9).

Output

If it's impossible to sort the array using cycles of total length not exceeding s, print a single number "-1" (quotes for clarity).

Otherwise, print a single number q— the minimum number of operations required to sort the array.

On the next 2 ⋅ q lines print descriptions of operations in the order they are applied to the array. The description of i-th operation begins with a single line containing one integer k (1 ≤ k ≤ n)—the length of the cycle (that is, the number of selected indices). The next line should contain k distinct integers i_1, i_2, ..., i_k (1 ≤ i_j ≤ n)—the indices of the cycle.

The sum of lengths of these cycles should be less than or equal to s, and the array should be sorted after applying these q operations.

If there are several possible answers with the optimal q, print any of them.

Examples

Input

5 5
3 2 3 1 1


Output

1
5
1 4 2 3 5 


Input

4 3
2 1 4 3


Output

-1

Input

2 0
2 2


Output

0

Note

In the first example, it's also possible to sort the array with two operations of total length 5: first apply the cycle 1 → 4 → 1 (of length 2), then apply the cycle 2 → 3 → 5 → 2 (of length 3). However, it would be wrong answer as you're asked to use the minimal possible number of operations, which is 1 in that case.

In the second example, it's possible to the sort the array with two cycles of total length 4 (1 → 2 → 1 and 3 → 4 → 3). However, it's impossible to achieve the same using shorter cycles, which is required by s=3.

In the third example, the array is already sorted, so no operations are needed. Total length of empty set of cycles is considered to be zero.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 200000;
int n, lim;
int a[MAXN];
int b[MAXN];
bool isfixed[MAXN];
pair<int, int> o[MAXN];
int no;
int dst[MAXN];
int cyc[MAXN], ncyc;
int par[MAXN], sz[MAXN];
int find(int a) {
  if (par[a] == a) return a;
  return par[a] = find(par[a]);
}
bool unite(int a, int b) {
  a = find(a), b = find(b);
  if (a == b) return false;
  if (sz[a] < sz[b]) swap(a, b);
  par[b] = a, sz[a] += sz[b];
  return true;
}
bool done[MAXN];
vector<vector<int>> ans;
bool solve() {
  for (int i = (0); i < (n); ++i) b[i] = a[i];
  sort(b, b + n);
  int nfixed = 0;
  for (int i = (0); i < (n); ++i) {
    isfixed[i] = a[i] == b[i];
    if (isfixed[i]) ++nfixed;
  }
  if (n - nfixed > lim) return false;
  no = 0;
  for (int i = (0); i < (n); ++i)
    if (!isfixed[i]) o[no++] = make_pair(a[i], i);
  sort(o, o + no);
  for (int i = (0); i < (n); ++i) dst[i] = isfixed[i] ? i : -1;
  {
    int at = 0;
    for (int i = (0); i < (no); ++i) {
      while (at < n && isfixed[at]) ++at;
      dst[o[i].second] = at++;
    }
  }
  for (int i = (0); i < (n); ++i) cyc[i] = -1;
  ncyc = 0;
  for (int i = (0); i < (n); ++i)
    if (cyc[i] == -1 && dst[i] != i) {
      int at = i;
      while (cyc[at] == -1) {
        cyc[at] = ncyc;
        at = dst[at];
      }
      ++ncyc;
    }
  int expect = ncyc;
  for (int i = (0); i < (ncyc); ++i) par[i] = i, sz[i] = 1;
  for (int l = 0, r = l; l < no; l = r) {
    while (r < no && o[l].first == o[r].first) ++r;
    int cur = o[l].second;
    for (int i = (l + 1); i < (r); ++i) {
      int oth = o[i].second;
      if (unite(cyc[cur], cyc[oth])) {
        swap(dst[cur], dst[oth]);
        --expect;
      }
    }
  }
  for (int i = (0); i < (n); ++i) done[i] = false;
  ans.clear();
  for (int i = (0); i < (n); ++i)
    if (!done[i] && dst[i] != i) {
      ans.push_back(vector<int>());
      int at = i;
      while (!done[at]) {
        done[at] = true;
        ans.back().push_back(at);
        at = dst[at];
      }
    }
  assert(((int)(ans).size()) == expect);
  int rem = lim - (n - nfixed);
  if (((int)(ans).size()) >= 3 && rem >= 3) {
    int cnt = min(rem, ((int)(ans).size()));
    vector<int> fst(cnt);
    for (int i = (0); i < (cnt); ++i) fst[i] = ans[i][0];
    reverse(fst.begin(), fst.end());
    vector<int> snd;
    for (int i = (0); i < (cnt); ++i) {
      snd.push_back(ans[i][0]);
      int j = (i + 1) % cnt;
      for (int k = (1); k < (((int)(ans[j]).size())); ++k)
        snd.push_back(ans[j][k]);
    }
    vector<vector<int>> nans;
    nans.push_back(fst);
    nans.push_back(snd);
    for (int i = (cnt); i < (((int)(ans).size())); ++i) nans.push_back(ans[i]);
    ans = nans;
  }
  return true;
}
bool verify(vector<vector<int>> ans) {
  vector<int> cur(n);
  for (int i = (0); i < (n); ++i) cur[i] = a[i];
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    int val = cur[ans[i][0]];
    for (int j = (1); j < (((int)(ans[i]).size())); ++j)
      swap(val, cur[ans[i][j]]);
    cur[ans[i][0]] = val;
  }
  for (int i = (1); i < (((int)(cur).size())); ++i)
    if (cur[i] < cur[i - 1]) return false;
  return true;
}
void run() {
  scanf("%d%d", &n, &lim);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  if (!solve()) {
    printf("-1\n");
    return;
  }
  printf("%d\n", ((int)(ans).size()));
  for (int i = (0); i < (((int)(ans).size())); ++i) {
    printf("%d\n", ((int)(ans[i]).size()));
    for (int j = (0); j < (((int)(ans[i]).size())); ++j) {
      if (j != 0) printf(" ");
      printf("%d", ans[i][j] + 1);
    }
    puts("");
  }
  assert(verify(ans));
}
int main() {
  run();
  return 0;
}

```