The numbers $1, \, 2, \, \dots, \, n \cdot k$ are colored with $n$ colors. These colors are indexed by $1, \, 2, \, \dots, \, n$. For each $1 \le i \le 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, \, \dots, \, b\}$. You must choose $n$ intervals $[a_1, \, b_1], \, [a_2, \, b_2], \, \dots, [a_n, \, b_n]$ such that:

for each $1 \le i \le n$, it holds $1 \le a_i < b_i \le n \cdot k$;

for each $1 \le i \le n$, the numbers $a_i$ and $b_i$ are colored with color $i$;

each number $1 \le x \le n \cdot k$ belongs to at most $\left\lceil \frac{n}{k - 1} \right\rceil$ 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 \le n \le 100$, $2 \le k \le 100$) — the number of colors and the number of occurrences of each color.

The second line contains $n \cdot k$ integers $c_1, \, c_2, \, \dots, \, c_{nk}$ ($1 \le c_j \le n$), where $c_j$ is the color of number $j$. It is guaranteed that, for each $1 \le i \le 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\lceil \frac{4}{3 - 1} \right\rceil = 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\lceil \frac{1}{2 - 1} \right\rceil = 1$ interval.

In the third sample, each number can be contained in at most $\left\lceil \frac{3}{3 - 1} \right\rceil = 2$ intervals. The output is described by the following picture:

Source: codeforces | Difficulty: HARD
Tags: Greedy algorithms

Sorting

Data structures

Constructive algorithms


Solutions:
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()


import io, os
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def main(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	indexes = [[] for i in range(n)]
	tot = n * k
	for i in range(tot):
		indexes[arr[i] - 1].append(i)
	bound = (n - 1) // (k - 1) + 1
	ans = [[] for i in range(n)]
	visited = [0] * n
	for p in range(k - 1):
		heap = []
		for c in range(n):
			heapq.heappush(heap, [indexes[c][p + 1], indexes[c][p], c])
		rest = bound
		while heap:
			ele = heapq.heappop(heap)
			[end, front, c] = ele
			if visited[c]:
				continue
			visited[c] = 1
			ans[c] = [front, end]
			rest -= 1
			if rest == 0:
				break
	for ele in ans:
		print(ele[0] + 1, ele[1] + 1)
T = 1
t = 1
while t <= T:
	main(t)
	t += 1


def no_intersections(numbers, colors):
	met_colors = {}
	pairs = []
	for (idx, color) in enumerate(numbers):
		if color in met_colors:
			pairs.append([color, met_colors[color], idx])
			colors.remove(color)
			met_colors = {}
		if color in colors:
			met_colors[color] = idx
	return pairs

def solve():
	(n, k) = (int(x) for x in input().split())
	numbers = [int(x) for x in input().split()]
	repeats = (n + k - 2) // (k - 1)
	pairs = []
	block_size = (n + repeats - 1) // repeats
	colors = list(range(1, n + 1))
	for x in range(repeats):
		pairs += no_intersections(numbers, set(colors[x * block_size:x * block_size + block_size]))
	pairs = sorted(pairs, key=lambda x: x[0])
	assert len(pairs) == n
	for pair in pairs:
		print(pair[1] + 1, pair[2] + 1)
solve()


def naiveSolve():
	return

def main():
	(n, k) = readIntArr()
	c = readIntArr()
	a = [-1] * (n + 1)
	b = [-1] * (n + 1)
	prev = [-1] * (n + 1)
	cnts = [0] * (n * k)
	limit = (n + k - 2) // (k - 1)
	start = 0
	for i in range(n * k):
		if prev[c[i]] >= start and a[c[i]] == -1:
			a[c[i]] = prev[c[i]]
			b[c[i]] = i
			for j in range(prev[c[i]], i + 1):
				cnts[j] += 1
				if cnts[j] == limit:
					start = i + 1
		else:
			prev[c[i]] = i
	for i in range(1, n + 1):
		print('{} {}'.format(a[i] + 1, b[i] + 1))
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(l, r):
	print('? {} {}'.format(l, r))
	sys.stdout.flush()
	return int(input())

def answerInteractive(x):
	print('! {}'.format(x))
	sys.stdout.flush()
inf = float('inf')
MOD = 998244353
from math import gcd, floor, ceil
for _abc in range(1):
	main()


from bisect import bisect_left
(n, k) = map(int, input().split())
c = list(map(int, input().split()))
a = [[] for _ in range(n)]
for i in range(n * k):
	a[c[i] - 1].append(i)
t = -1
d = [0] * n
cnt = 0
resa = [0] * n
resb = [0] * n
while cnt < n:
	mi = 10000
	mj = -1
	midx = 0
	for j in range(n):
		if d[j] == 0:
			idx = bisect_left(a[j], t)
			if idx < k - 1:
				if mi > a[j][idx + 1]:
					mi = a[j][idx + 1]
					mj = j
					midx = idx
	if mj == -1:
		t = -1
	else:
		resa[mj] = a[mj][midx] + 1
		resb[mj] = a[mj][midx + 1] + 1
		cnt += 1
		d[mj] = 1
		t = mi
for i in range(n):
	print(resa[i], resb[i])


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2 * 10 ** 5 + 10)
write = lambda x: sys.stdout.write(x + '\n')
debug = lambda x: sys.stderr.write(x + '\n')
writef = lambda x: print('{:.12f}'.format(x))
(n, k) = list(map(int, input().split()))
c = list(map(lambda i: int(i) - 1, input().split()))
s = {}
done = [0] * n
ng = [0] * (n * k)
ans = [-1] * n
while 1:
	if all(done):
		break
	s = {}
	for i in range(n * k):
		if ng[i] or done[c[i]]:
			continue
		if c[i] in s:
			ans[c[i]] = (s[c[i]], i)
			done[c[i]] = 1
			s = {}
		else:
			s[c[i]] = i
count = [0] * (n * k)
ok = [0] * n
for (u, v) in ans:
	assert c[u] == c[v]
	ok[c[u]] = 1
	for i in range(u, v + 1):
		count[i] += 1
assert all((v <= (n + k - 2) // (k - 1) for v in count))
write('\n'.join([' '.join(map(lambda i: str(i + 1), item)) for item in ans]))


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	p = [None] * (n + 1)
	w = [False] * (n + 1)
	a = []
	r = [None] * n
	i = 0
	b = (n + k - 2) // (k - 1)
	for c in map(int, input().split()):
		if p[c] is not None and (not w[c]):
			(X, Y) = (p[c], i)
			z = 0
			for (x, y) in a:
				L = max(x, X)
				R = min(y, Y)
				if L <= R:
					z += 1
			if z < b:
				a.append((X, Y))
				r[c - 1] = str(X + 1) + ' ' + str(Y + 1)
				w[c] = True
		p[c] = i
		i += 1
	print('\n'.join(r))
solve()


import sys
input = sys.stdin.readline
from operator import itemgetter
(n, k) = map(int, input().split())
C = list(map(int, input().split()))
CLIST = [[] for i in range(n)]
for i in range(n * k):
	CLIST[C[i] - 1].append(i)
SUM = [0] * (n * k)
MAX = (n + (k - 2)) // (k - 1)
C2 = []
for i in range(n):
	for j in range(len(CLIST[i]) - 1):
		(x, y) = (CLIST[i][j], CLIST[i][j + 1])
		C2.append((x, y, i))
C2.sort(key=itemgetter(1))
seg_el = 1 << (n * k + 5).bit_length()
SEG = [0] * (2 * seg_el)
LAZY = [0] * (2 * seg_el)

def indexes(L, R):
	INDLIST = []
	R -= 1
	L >>= 1
	R >>= 1
	while L != R:
		if L > R:
			INDLIST.append(L)
			L >>= 1
		else:
			INDLIST.append(R)
			R >>= 1
	while L != 0:
		INDLIST.append(L)
		L >>= 1
	return INDLIST

def adds(l, r, x):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY[ind] != 0:
			plus_lazy = LAZY[ind]
			SEG[ind << 1] += plus_lazy
			SEG[1 + (ind << 1)] += plus_lazy
			LAZY[ind << 1] += plus_lazy
			LAZY[1 + (ind << 1)] += plus_lazy
			LAZY[ind] = 0
	while L != R:
		if L > R:
			SEG[L] += x
			LAZY[L] += x
			L += 1
			L //= L & -L
		else:
			R -= 1
			SEG[R] += x
			LAZY[R] += x
			R //= R & -R
	for ind in UPIND:
		SEG[ind] = max(SEG[ind << 1], SEG[1 + (ind << 1)])

def getvalues(l, r):
	L = l + seg_el
	R = r + seg_el
	L //= L & -L
	R //= R & -R
	UPIND = indexes(L, R)
	for ind in UPIND[::-1]:
		if LAZY[ind] != 0:
			plus_lazy = LAZY[ind]
			SEG[ind << 1] += plus_lazy
			SEG[1 + (ind << 1)] += plus_lazy
			LAZY[ind << 1] += plus_lazy
			LAZY[1 + (ind << 1)] += plus_lazy
			LAZY[ind] = 0
	ANS = 0
	while L != R:
		if L > R:
			ANS = max(ANS, SEG[L])
			L += 1
			L //= L & -L
		else:
			R -= 1
			ANS = max(ANS, SEG[R])
			R //= R & -R
	return ANS
ANS = [[-1, -1] for i in range(n)]
for (x, y, ind) in C2:
	if ANS[ind] != [-1, -1]:
		continue
	if getvalues(x, y) >= MAX:
		continue
	ANS[ind] = [x, y]
	adds(x, y + 1, 1)
for (x, y) in ANS:
	print(x + 1, y + 1)


import collections
import math
import itertools
import sys

def fast_input():
	return sys.stdin.readline().strip()
input = fast_input

def ints_input():
	return list((int(x) for x in input().split()))

def solve():
	(n, k) = ints_input()
	colours = ints_input()
	colours_done = set()
	ranges = []
	while len(colours_done) < n:
		colours_on_pass = dict()
		for (i, c) in enumerate(colours):
			if c in colours_on_pass:
				ranges.append((c, (colours_on_pass[c], i + 1)))
				colours_done.add(c)
				colours_on_pass = dict()
			elif c not in colours_done:
				colours_on_pass[c] = i + 1
	for (_, r) in sorted(ranges):
		print(' '.join([str(x) for x in r]))
if False:
	for _ in range(int(input())):
		solve()
else:
	solve()


(n, k) = list(map(int, input().split()))
c = list(map(int, input().split()))
p = [(i, c[i] - 1) for i in range(n * k)]

def reduce(p):
	pairs = []
	prev = [-1] * n
	counts = [0] * n
	pair_inds = set()
	pair_colors = set()
	q = 1
	for (index, color) in p:
		if counts[color] == q and color not in pair_colors:
			pairs.append((prev[color], index))
			pair_colors.add(color)
			q += 1
		prev[color] = index
		counts[color] += 1
	p2 = []
	for (index, color) in p:
		if color not in pair_colors:
			p2.append((index, color))
	return (pairs, p2)
p_orig = p[:]
pairs = []
while len(pairs) < n:
	(new_pairs, p2) = reduce(p)
	pairs += new_pairs
	p = p2
for pair in sorted(pairs, key=lambda pair: p_orig[pair[0]][1]):
	print(f'{pair[0] + 1} {pair[1] + 1}')


import sys
from sys import stdin, stdout
try:
	(n, k) = map(int, stdin.readline().split())
	c_a = list(map(int, stdin.readline().split()))
	ceil = (n + k - 2) // (k - 1)
	co_a = [[] for _ in range(n)]
	for i in range(len(c_a)):
		co_a[c_a[i] - 1].append(i)
	kc_a = [[] for _ in range(k)]
	for i in range(1, k):
		for j in range(n):
			kc_a[i].append([j, co_a[j][i - 1], co_a[j][i]])
	res = {}
	for i in range(1, k):
		kc_a[i].sort(key=lambda x: x[2])
		cnt = 0
		for j in range(n):
			(c, l, r) = kc_a[i][j]
			if c in res:
				continue
			res[c] = [l + 1, r + 1]
			cnt += 1
			if cnt >= ceil:
				break
	for i in range(n):
		stdout.write(str(res[i][0]) + ' ' + str(res[i][1]) + '\n')
except:
	print(sys.exc_info()[0])


(N, K) = map(int, input().split())
M = 0 - -N // (K - 1)
A = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for (i, a) in enumerate(A):
	X[a].append(i)
L = [i for i in range(N)]
ANS = [(-1, -1) for _ in range(N)]
c = 1
while L:
	Y = []
	for i in L:
		Y.append((X[i][c], i))
	Y.sort(key=lambda x: x[0])
	for (_, i) in Y[:M]:
		ANS[i] = (X[i][c - 1], X[i][c])
	L = [i for (_, i) in Y[M:]]
	c += 1
for (l, r) in ANS:
	print(l + 1, r + 1)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k) = [int(i) for i in input().split()]
a = [int(i) - 1 for i in input().split()]
vis = [0] * n
cnt = [0] * (n * k)
ind = [[] for i in range(n)]
for i in range(len(a)):
	ind[a[i]].append(i)
b = []
for i in range(n):
	for j in range(1, len(ind[i])):
		b.append([ind[i][j - 1], ind[i][j]])
b.sort(key=lambda x: x[1])
ans = []
maxi = (n + k - 2) // (k - 1)
for i in b:
	if vis[a[i[0]]]:
		continue
	mw = 0
	for j in range(i[0], i[1] + 1):
		mw = max(mw, cnt[j])
	if mw < maxi:
		vis[a[i[0]]] = 1
		for j in range(i[0], i[1] + 1):
			cnt[j] += 1
		ans.append([a[i[0]], i[0] + 1, i[1] + 1])
ans = ans[:n]
ans.sort()
for i in ans:
	print(i[1], i[2])


import sys
from sys import stdin
tt = 1
for loop in range(tt):
	(n, k) = map(int, stdin.readline().split())
	c = list(map(int, stdin.readline().split()))
	for i in range(n * k):
		c[i] -= 1
	last = [None] * n
	RLC = []
	for i in range(n * k):
		if last[c[i]] == None:
			last[c[i]] = i
		else:
			RLC.append((i, last[c[i]], c[i]))
			last[c[i]] = i
	RLC.sort()
	end = [False] * n
	rem = [(n + k - 2) // (k - 1)] * (n * k)
	ans = [None] * n
	for (R, L, C) in RLC:
		if end[C]:
			continue
		elif min(rem[L:R + 1]) == 0:
			continue
		else:
			end[C] = True
			ans[C] = (L, R)
			for i in range(L, R + 1):
				rem[i] -= 1
	for i in ans:
		print(i[0] + 1, i[1] + 1)


import sys
input = sys.stdin.readline
from heapq import *

def main():
	(n, k) = map(int, input().split())
	clst = list(map(int, input().split()))
	max_ = (n + k - 1 - 1) // (k - 1)
	cnt = [0] * (n * k)
	aft = [-1] * n
	nex = [-1] * (n * k)
	bef = [-1] * (n * k)
	for i in range(n * k - 1, -1, -1):
		c = clst[i] - 1
		nex[i] = aft[c]
		aft[c] = i
	used = [False] * n
	hq = []
	for i in range(n * k):
		c = clst[i] - 1
		if not used[c]:
			used[c] = True
			j = nex[i]
			bef[j] = i
			heappush(hq, -j)
			for l in range(i, j + 1):
				cnt[l] += 1
		while cnt[i] > max_:
			j = -heappop(hq)
			used[clst[j] - 1] = False
			i = bef[j]
			for l in range(i, j + 1):
				cnt[l] -= 1
	ans = [-1] * n
	for h in hq:
		h = -h
		ans[clst[h] - 1] = (bef[h] + 1, h + 1)
	for row in ans:
		print(*row)
for _ in range(1):
	main()


(n, k) = map(int, input().split(' '))
arr = [int(x) - 1 for x in input().split()]
m = 0 - -n // (k - 1)
gp = [[] for x in range(n)]
ct = 0
for x in arr:
	gp[x].append(ct)
	ct += 1
c = 1
L = [x for x in range(n)]
ans = [[] for x in range(n)]
while L:
	y = []
	for x in L:
		y.append([gp[x][c], x])
	y.sort(key=lambda x: x[0])
	for x in y[:m]:
		ans[x[1]].append(gp[x[1]][c - 1])
		ans[x[1]].append(x[0])
	L = []
	for x in y[m:]:
		L.append(x[1])
	c += 1
for x in ans:
	print(x[0] + 1, x[1] + 1)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
while False:
	n = random.randint(1, 5)
	k = random.randint(2, 3)
	color = []
	for i in range(1, n + 1):
		color += [i] * k
	random.shuffle(color)
	limit = (n - 1) // (k - 1) + 1
	ans = [-1 for i in range(n + 1)]
	cnt = [[] for i in range(n + 1)]
	g = 0
	for i in range(n * k):
		if ans[color[i]] != -1:
			continue
		if len(cnt[color[i]]) < 2:
			cnt[color[i]].append(i + 1)
			if len(cnt[color[i]]) == 2:
				g += 1
				if g == limit:
					for j in range(1, n + 1):
						if len(cnt[j]) == 2:
							(a, b) = cnt[j]
							ans[j] = (a, b)
					g = 0
					cnt = [[] for j in range(n + 1)]
	for j in range(1, n + 1):
		if len(cnt[j]) == 2:
			(a, b) = cnt[j]
			ans[j] = (a, b)
	for i in range(1, n + 1):
		if ans[i] == -1:
			print(n, k)
			print(*color)
			exit()
(n, k) = mi()
color = li()
limit = (n - 1) // (k - 1) + 1
ans = [-1 for i in range(n + 1)]
cnt = [[] for i in range(n + 1)]
g = 0
for i in range(n * k):
	if ans[color[i]] != -1:
		continue
	if len(cnt[color[i]]) < 2:
		cnt[color[i]].append(i + 1)
		if len(cnt[color[i]]) == 2:
			g += 1
			if g == limit:
				for j in range(1, n + 1):
					if len(cnt[j]) == 2:
						(a, b) = cnt[j]
						ans[j] = (a, b)
				g = 0
				cnt = [[] for j in range(n + 1)]
for j in range(1, n + 1):
	if len(cnt[j]) == 2:
		(a, b) = cnt[j]
		ans[j] = (a, b)
for i in range(1, n + 1):
	print(*ans[i])