human
PYTHON3 solution for "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:


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:

":



=====
Write me a the Python code you requested?
assistant
#Here is the Python code you requested.
 def solve():
    n, k = map(int, input().split())
    arr = list(map(lambda x:int(x)-1, input().split()))
    t = [[] for i in range(n)]
    for i in range(n*k):
        t[arr[i]].append(i)
    used = [0] * n
    c1 = [0]
    ans = [0] * n
    q = n // (k-1)
    r = n % (k-1)
    for i in range(k-1):
        c1.append(c1[-1] + q + (i<=r))
    for i in range(1, k):
        a = []
        c = q + (i<=r)
        for j in range(n):
            if used[j] == 0:
                a.append((t[j][i], j))
        a = sorted(a)[:c]
        for x, ind in a:
            used[ind] = 1
            ans[ind] = (t[ind][i-1]+1, t[ind][i]+1)
    for a in ans:
        print(*a)


import sys
input = lambda: sys.stdin.readline().rstrip()
solve()