#include <bits/stdc++.h>
using namespace std;
vector<int> pat[500000];
vector<int> rev[500000];
vector<bool> flag[500000];
int pt[500000];
void adde(int a, int b) {
  pat[a].push_back(b);
  flag[a].push_back(false);
}
vector<int> euler;
void calceuler(int node) {
  for (;;) {
    if (pt[node] == pat[node].size()) break;
    if (!flag[node][pt[node]]) {
      flag[node][pt[node]] = true;
      pt[node]++;
      calceuler(pat[node][pt[node] - 1]);
    } else
      pt[node]++;
  }
  euler.push_back(node);
}
class unionfind {
 public:
  int par[500000];
  int ran[500000];
  int ren[500000];
  void init() {
    for (int i = 0; i < 500000; i++) {
      par[i] = i;
      ran[i] = 0;
      ren[i] = 1;
    }
  }
  int find(int a) {
    if (a == par[a])
      return a;
    else
      return par[a] = find(par[a]);
  }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (ran[a] > ran[b]) {
      par[b] = a;
      ren[a] += ren[b];
    } else {
      par[a] = b;
      ren[b] += ren[a];
    }
    if (ran[a] == ran[b]) ran[b]++;
  }
};
unionfind uf;
int dat[204020];
int cnt[204020];
int kou[504020];
bool isok[204020];
int zat[202020];
int curr[202020];
void check(vector<vector<int> > v, int num) {
  for (int p = 0; p < v.size(); p++) {
    vector<int> zi = v[p];
    int t = curr[zi[zi.size() - 1]];
    for (int i = 0; i < zi.size(); i++) {
      int s = curr[zi[i]];
      curr[zi[i]] = t;
      t = s;
    }
  }
  for (int i = 0; i < num - 1; i++)
    if (curr[i] > curr[i + 1]) abort();
}
int main() {
  int num, gen;
  scanf("%d%d", &num, &gen);
  for (int i = 0; i < num; i++) scanf("%d", &dat[i]), zat[i] = curr[i] = dat[i];
  sort(zat, zat + num);
  for (int i = 0; i < num; i++)
    dat[i] = 1 + lower_bound(zat, zat + num, dat[i]) - zat;
  for (int i = 0; i < num; i++) cnt[dat[i]]++;
  for (int j = 1; j < 202020; j++) cnt[j] += cnt[j - 1];
  uf.init();
  int opes = 0;
  for (int i = 0; i < num; i++)
    isok[i] = (cnt[dat[i] - 1] <= i && i < cnt[dat[i]]);
  for (int i = 0; i < num; i++)
    if (!isok[i]) uf.unite(i, num + dat[i]), opes++;
  for (int i = 1; i < 202020; i++)
    for (int j = cnt[i - 1]; j < cnt[i]; j++)
      if (!isok[j]) uf.unite(j, num + i);
  fill(kou, kou + 502020, -1);
  for (int i = 0; i < num; i++)
    if (!isok[i]) kou[uf.find(i)] = i;
  int rr = 0;
  for (int i = 0; i < 502020; i++)
    if (kou[i] != -1) rr++;
  vector<vector<int> > ret;
  if (opes > gen) {
    printf("-1\n");
    return 0;
  }
  vector<int> zi;
  for (int i = 0; i < 502020; i++)
    if (kou[i] != -1 && zi.size() < gen - opes) zi.push_back(kou[i]);
  if (zi.size() >= 3) {
    int t = dat[zi[zi.size() - 1]];
    for (int i = 0; i < zi.size(); i++) {
      int s = dat[zi[i]];
      dat[zi[i]] = t;
      t = s;
    }
    ret.push_back(zi);
  }
  uf.init();
  for (int i = 0; i < num; i++)
    if (!isok[i]) uf.unite(i, num + dat[i]);
  for (int i = 1; i < 202020; i++)
    for (int j = cnt[i - 1]; j < cnt[i]; j++)
      if (!isok[j]) uf.unite(j, num + i);
  fill(kou, kou + 502020, -1);
  for (int i = 0; i < num; i++)
    if (!isok[i]) kou[uf.find(i)] = i;
  for (int i = 0; i < num; i++)
    if (!isok[i]) adde(i, num + dat[i]);
  for (int i = 1; i < 202020; i++)
    for (int j = cnt[i - 1]; j < cnt[i]; j++)
      if (!isok[j]) adde(num + i, j);
  for (int i = 0; i < 502020; i++) {
    if (kou[i] == -1) continue;
    euler.clear();
    calceuler(i);
    reverse(euler.begin(), euler.end());
    vector<int> z;
    for (int j = 0; j < euler.size() - 1; j++)
      if (euler[j] < num) z.push_back(euler[j]);
    ret.push_back(z);
  }
  int sum = 0;
  for (int i = 0; i < ret.size(); i++) sum += ret[i].size();
  printf("%d\n", ret.size());
  for (int i = 0; i < ret.size(); i++) {
    printf("%d\n", ret[i].size());
    for (int j = 0; j < ret[i].size(); j++) printf("%d ", ret[i][j] + 1);
    printf("\n");
  }
  check(ret, num);
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
vector<int> pat[500000];
vector<int> rev[500000];
vector<bool> flag[500000];
int pt[500000];
void adde(int a, int b) {
  pat[a].push_back(b);
  flag[a].push_back(false);
}
vector<int> euler;
void calceuler(int node) {
  for (;;) {
    if (pt[node] == pat[node].size()) break;
    if (!flag[node][pt[node]]) {
      flag[node][pt[node]] = true;
      pt[node]++;
      calceuler(pat[node][pt[node] - 1]);
    } else
      pt[node]++;
  }
  euler.push_back(node);
}
class unionfind {
 public:
  int par[500000];
  int ran[500000];
  int ren[500000];
  void init() {
    for (int i = 0; i < 500000; i++) {
      par[i] = i;
      ran[i] = 0;
      ren[i] = 1;
    }
  }
  int find(int a) {
    if (a == par[a])
      return a;
    else
      return par[a] = find(par[a]);
  }
  void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (ran[a] > ran[b]) {
      par[b] = a;
      ren[a] += ren[b];
    } else {
      par[a] = b;
      ren[b] += ren[a];
    }
    if (ran[a] == ran[b]) ran[b]++;
  }
};
unionfind uf;
int dat[204020];
int cnt[204020];
int kou[504020];
bool isok[204020];
int zat[202020];
int curr[202020];
void check(vector<vector<int> > v, int num) {
  for (int p = 0; p < v.size(); p++) {
    vector<int> zi = v[p];
    int t = curr[zi[zi.size() - 1]];
    for (int i = 0; i < zi.size(); i++) {
      int s = curr[zi[i]];
      curr[zi[i]] = t;
      t = s;
    }
  }
  for (int i = 0; i < num - 1; i++)
    if (curr[i] > curr[i + 1]) abort();
}
int main() {
  int num, gen;
  scanf("%d%d", &num, &gen);
  for (int i = 0; i < num; i++) scanf("%d", &dat[i]), zat[i] = curr[i] = dat[i];
  sort(zat, zat + num);
  for (int i = 0; i < num; i++)
    dat[i] = 1 + lower_bound(zat, zat + num, dat[i]) - zat;
  for (int i = 0; i < num; i++) cnt[dat[i]]++;
  for (int j = 1; j < 202020; j++) cnt[j] += cnt[j - 1];
  uf.init();
  int opes = 0;
  for (int i = 0; i < num; i++)
    isok[i] = (cnt[dat[i] - 1] <= i && i < cnt[dat[i]]);
  for (int i = 0; i < num; i++)
    if (!isok[i]) uf.unite(i, num + dat[i]), opes++;
  for (int i = 1; i < 202020; i++)
    for (int j = cnt[i - 1]; j < cnt[i]; j++)
      if (!isok[j]) uf.unite(j, num + i);
  fill(kou, kou + 502020, -1);
  for (int i = 0; i < num; i++)
    if (!isok[i]) kou[uf.find(i)] = i;
  int rr = 0;
  for (int i = 0; i < 502020; i++)
    if (kou[i] != -1) rr++;
  vector<vector<int> > ret;
  if (opes > gen) {
    printf("-1\n");
    return 0;
  }
  vector<int> zi;
  for (int i = 0; i < 502020; i++)
    if (kou[i] != -1 && zi.size() < gen - opes) zi.push_back(kou[i]);
  if (zi.size() >= 3) {
    int t = dat[zi[zi.size() - 1]];
    for (int i = 0; i < zi.size(); i++) {
      int s = dat[zi[i]];
      dat[zi[i]] = t;
      t = s;
    }
    ret.push_back(zi);
  }
  uf.init();
  for (int i = 0; i < num; i++)
    if (!isok[i]) uf.unite(i, num + dat[i]);
  for (int i = 1; i < 202020; i++)
    for (int j = cnt[i - 1]; j < cnt[i]; j++)
      if (!isok[j]) uf.unite(j, num + i);
  fill(kou, kou + 502020, -1);
  for (int i = 0; i < num; i++)
    if (!isok[i]) kou[uf.find(i)] = i;
  for (int i = 0; i < num; i++)
    if (!isok[i]) adde(i, num + dat[i]);
  for (int i = 1; i < 202020; i++)
    for (int j = cnt[i - 1]; j < cnt[i]; j++)
      if (!isok[j]) adde(num + i, j);
  for (int i = 0; i < 502020; i++) {
    if (kou[i] == -1) continue;
    euler.clear();
    calceuler(i);
    reverse(euler.begin(), euler.end());
    vector<int> z;
    for (int j = 0; j < euler.size() - 1; j++)
      if (euler[j] < num) z.push_back(euler[j]);
    ret.push_back(z);
  }
  int sum = 0;
  for (int i = 0; i < ret.size(); i++) sum += ret[i].size();
  printf("%d\n", ret.size());
  for (int i = 0; i < ret.size(); i++) {
    printf("%d\n", ret[i].size());
    for (int j = 0; j < ret[i].size(); j++) printf("%d ", ret[i][j] + 1);
    printf("\n");
  }
  check(ret, num);
}

```