The numbers 1,   2,   ...,   n ⋅ k are colored with n colors. These colors are indexed by 1,   2,   ...,   n. For each 1 ≤ i ≤ n, there are exactly k numbers colored with color i.

Let [a,   b] denote the interval of integers between a and b inclusive, that is, the set \\{a,   a + 1,   ...,   b\}. You must choose n intervals [a_1,   b_1],   [a_2,   b_2],   ..., [a_n,   b_n] such that: 

  * for each 1 ≤ i ≤ n, it holds 1 ≤ a_i < b_i ≤ n ⋅ k; 
  * for each 1 ≤ i ≤ n, the numbers a_i and b_i are colored with color i; 
  * each number 1 ≤ x ≤ n ⋅ k belongs to at most \left⌈ (n)/(k - 1) \right⌉ intervals. 



One can show that such a family of intervals always exists under the given constraints.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100, 2 ≤ k ≤ 100) — the number of colors and the number of occurrences of each color.

The second line contains n ⋅ k integers c_1,   c_2,   ...,   c_{nk} (1 ≤ c_j ≤ n), where c_j is the color of number j. It is guaranteed that, for each 1 ≤ i ≤ n, it holds c_j = i for exactly k distinct indices j.

Output

Output n lines. The i-th line should contain the two integers a_i and b_i.

If there are multiple valid choices of the intervals, output any.

Examples

Input


4 3
2 4 3 1 1 4 2 3 2 1 3 4


Output


4 5
1 7
8 11
6 12

Input


1 2
1 1


Output


1 2


Input


3 3
3 1 2 3 2 1 2 1 3


Output


6 8
3 7
1 4

Input


2 3
2 1 1 1 2 2


Output


2 3
5 6

Note

In the first sample, each number can be contained in at most \left⌈ (4)/(3 - 1) \right⌉ = 2 intervals. The output is described by the following picture:

<image>

In the second sample, the only interval to be chosen is forced to be [1,   2], and each number is indeed contained in at most \left⌈ (1)/(2 - 1) \right⌉ = 1 interval.

In the third sample, each number can be contained in at most \left⌈ (3)/(3 - 1) \right⌉ = 2 intervals. The output is described by the following picture:

<image>
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int inf = INT_MAX / 2 - 100;
const long long infLL = LLONG_MAX / 3;
mt19937 irand(random_device{}());
mt19937_64 lrand(random_device{}());
default_random_engine drand(random_device{}());
int rnd(int x) { return irand() % x; }
int rand_int(int l, int r) { return uniform_int_distribution<>(l, r)(irand); }
long long rand_ll(long long l, long long r) {
  return uniform_int_distribution<long long>(l, r)(lrand);
}
double rand_db(double l, double r) {
  return uniform_real_distribution<>(l, r)(drand);
}
inline int add(int a, int b) {
  a += b;
  return a >= mod ? a - mod : a;
}
inline int sub(int a, int b) {
  a -= b;
  return a < 0 ? a + mod : a;
}
inline void inc(int& a, int b) { a = add(a, b); }
inline int mul(int a, int b) { return 1LL * a * b % mod; }
template <class t>
inline t ksm(t a, t b) {
  t r = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) r = mul(r, a);
  return r;
}
inline int inv(int a) {
  int b = mod, u = 0, v = 1, t;
  while (a) {
    t = b / a;
    b -= t * a, swap(a, b);
    u -= t * v, swap(u, v);
  }
  return u < 0 ? u + mod : u;
}
template <class t, class u>
bool chmax(t& a, u b) {
  if (a < b) {
    a = b;
    return true;
  } else
    return false;
}
template <class t, class u>
bool chmin(t& a, u b) {
  if (b < a) {
    a = b;
    return true;
  } else
    return false;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pii = pair<int, int>;
using vi = vc<int>;
using ti3 = tuple<int, int, int>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.a << "," << p.b << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
template <class T>
T sq(const T& t) {
  return t * t;
}
int topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
int topbit(long long t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
int botbit(signed a) { return a == 0 ? 32 : __builtin_ctz(a); }
int botbit(long long a) { return a == 0 ? 64 : __builtin_ctzll(a); }
int popcount(signed t) { return __builtin_popcount(t); }
int popcount(long long t) { return __builtin_popcountll(t); }
bool ispow2(int i) { return i && (i & -i) == i; }
long long mask(int i) { return (long long(1) << i) - 1; }
bool inc(int a, int b, int c) { return a <= b && b <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort((v).begin(), (v).end());
  v.erase(unique((v).begin(), (v).end()), v.end());
}
template <class t>
void myshuffle(vc<t>& a) {
  for (int i = 0; i < ((int)(a).size()); i++) swap(a[i], a[rand_int(0, i)]);
}
template <class t>
int lwb(const vc<t>& v, const t& a) {
  return lower_bound((v).begin(), (v).end(), a) - v.bg;
}
int mx[40005], la[40005];
void setv(int p, int v) {
  mx[p] += v;
  la[p] += v;
}
void push(int p) {
  if (!la[p]) return;
  setv(p << 1, la[p]), setv(p << 1 | 1, la[p]);
  la[p] = 0;
}
void modify(int p, int l, int r, int x, int y) {
  if (x <= l && r <= y) return setv(p, 1);
  push(p);
  int mid = l + r >> 1;
  if (x <= mid) modify(p << 1, l, mid, x, y);
  if (mid < y) modify(p << 1 | 1, mid + 1, r, x, y);
  mx[p] = max(mx[p << 1], mx[p << 1 | 1]);
}
int gmax(int p, int l, int r, int x, int y) {
  if (x <= l && r <= y) return mx[p];
  push(p);
  int mid = l + r >> 1, mx = 0;
  if (x <= mid) chmax(mx, gmax(p << 1, l, mid, x, y));
  if (mid < y) chmax(mx, gmax(p << 1 | 1, mid + 1, r, x, y));
  return mx;
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  vi lst(n + 1, 0);
  vc<ti3> seg;
  for (int i = 1; i <= n * k; i++) {
    int x;
    scanf("%d", &x);
    if (lst[x]) seg.push_back(make_tuple(lst[x], i, x));
    lst[x] = i;
  }
  vc<pii> ans(n + 1);
  vi ansd(n + 1, 0);
  sort((seg).begin(), (seg).end(),
       [](ti3 a, ti3 b) { return get<1>(a) < get<1>(b); });
  for (auto [l, r, x] : seg)
    if (!ansd[x]) {
      if (gmax(1, 1, n * k, l, r) > 1) continue;
      ans[x] = make_pair(l, r);
      modify(1, 1, n * k, l, r);
      ansd[x] = 1;
    }
  for (int i = 1; i <= n; i++) printf("%d %d\n", ans[i].first, ans[i].second);
}
