#include <bits/stdc++.h>
using namespace std;
using int64 = long long int;
struct Edge {
  int from;
  int to;
  int to_index;
};
class Graph {
 public:
  explicit Graph(const int n) : edges_(n) {}
  void AddEdge(Edge e) { edges_[e.from].push_back(e); }
  vector<vector<int>> FindCycles() {
    current_edge_.assign(edges_.size(), 0);
    vector<vector<int>> result;
    for (size_t i = 0; i < edges_.size(); ++i) {
      Dfs(i);
      if (!cycle_.empty()) {
        result.push_back(move(cycle_));
        cycle_.clear();
      }
    }
    return result;
  }

 private:
  void Dfs(const int node) {
    while (current_edge_[node] < edges_[node].size()) {
      const Edge& e = edges_[node][current_edge_[node]++];
      Dfs(e.to);
      cycle_.push_back(e.to_index);
    }
  }
  vector<vector<Edge>> edges_;
  vector<size_t> current_edge_;
  vector<int> cycle_;
};
void solve() {
  int n, s;
  scanf("%d %d", &n, &s);
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a.begin(), a.end());
  vector<int> group(n);
  int current_group = -1;
  for (int i = 0; i < n; ++i) {
    if (i == 0 || a[i].first != a[i - 1].first) {
      ++current_group;
    }
    group[i] = current_group;
  }
  Graph graph(current_group + 1);
  for (int i = 0; i < n; ++i) {
    const int gi = group[i];
    const int gj = group[a[i].second];
    if (gi != gj) {
      graph.AddEdge({gi, gj, a[i].second});
    }
  }
  vector<vector<int>> cycles = graph.FindCycles();
  int cycles_size = 0;
  for (const vector<int>& cycle : cycles) {
    cycles_size += cycle.size();
  }
  if (s < cycles_size) {
    cout << -1 << "\n";
    return;
  }
  if (s >= cycles_size + 2 && cycles.size() >= 2) {
    const int num_cycles = cycles.size();
    const int cycles_to_merge = min(s - cycles_size, num_cycles);
    vector<int> merged_cycle;
    for (int i = num_cycles - cycles_to_merge; i < num_cycles; ++i) {
      merged_cycle.insert(merged_cycle.end(), cycles[i].begin(),
                          cycles[i].end());
    }
    vector<int> additional_cycle;
    for (int i = num_cycles - 1; i >= num_cycles - cycles_to_merge; --i) {
      additional_cycle.push_back(cycles[i][0]);
    }
    cycles.resize(cycles.size() - cycles_to_merge);
    cycles.push_back(move(merged_cycle));
    cycles.push_back(move(additional_cycle));
  }
  cout << cycles.size() << "\n";
  for (const auto& cycle : cycles) {
    cout << cycle.size() << "\n";
    for (const int node : cycle) {
      cout << (node + 1) << " ";
    }
    cout << "\n";
  }
}
int main() {
  solve();
  return 0;
}

### 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;
using int64 = long long int;
struct Edge {
  int from;
  int to;
  int to_index;
};
class Graph {
 public:
  explicit Graph(const int n) : edges_(n) {}
  void AddEdge(Edge e) { edges_[e.from].push_back(e); }
  vector<vector<int>> FindCycles() {
    current_edge_.assign(edges_.size(), 0);
    vector<vector<int>> result;
    for (size_t i = 0; i < edges_.size(); ++i) {
      Dfs(i);
      if (!cycle_.empty()) {
        result.push_back(move(cycle_));
        cycle_.clear();
      }
    }
    return result;
  }

 private:
  void Dfs(const int node) {
    while (current_edge_[node] < edges_[node].size()) {
      const Edge& e = edges_[node][current_edge_[node]++];
      Dfs(e.to);
      cycle_.push_back(e.to_index);
    }
  }
  vector<vector<Edge>> edges_;
  vector<size_t> current_edge_;
  vector<int> cycle_;
};
void solve() {
  int n, s;
  scanf("%d %d", &n, &s);
  vector<pair<int, int>> a(n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i;
  }
  sort(a.begin(), a.end());
  vector<int> group(n);
  int current_group = -1;
  for (int i = 0; i < n; ++i) {
    if (i == 0 || a[i].first != a[i - 1].first) {
      ++current_group;
    }
    group[i] = current_group;
  }
  Graph graph(current_group + 1);
  for (int i = 0; i < n; ++i) {
    const int gi = group[i];
    const int gj = group[a[i].second];
    if (gi != gj) {
      graph.AddEdge({gi, gj, a[i].second});
    }
  }
  vector<vector<int>> cycles = graph.FindCycles();
  int cycles_size = 0;
  for (const vector<int>& cycle : cycles) {
    cycles_size += cycle.size();
  }
  if (s < cycles_size) {
    cout << -1 << "\n";
    return;
  }
  if (s >= cycles_size + 2 && cycles.size() >= 2) {
    const int num_cycles = cycles.size();
    const int cycles_to_merge = min(s - cycles_size, num_cycles);
    vector<int> merged_cycle;
    for (int i = num_cycles - cycles_to_merge; i < num_cycles; ++i) {
      merged_cycle.insert(merged_cycle.end(), cycles[i].begin(),
                          cycles[i].end());
    }
    vector<int> additional_cycle;
    for (int i = num_cycles - 1; i >= num_cycles - cycles_to_merge; --i) {
      additional_cycle.push_back(cycles[i][0]);
    }
    cycles.resize(cycles.size() - cycles_to_merge);
    cycles.push_back(move(merged_cycle));
    cycles.push_back(move(additional_cycle));
  }
  cout << cycles.size() << "\n";
  for (const auto& cycle : cycles) {
    cout << cycle.size() << "\n";
    for (const int node : cycle) {
      cout << (node + 1) << " ";
    }
    cout << "\n";
  }
}
int main() {
  solve();
  return 0;
}

```