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>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class E {

	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		int n=fs.nextInt(), nCopies=fs.nextInt();
		ST st=new ST(0, n*nCopies-1);
		int[] a=fs.readArray(n*nCopies);
		for (int i=0; i<a.length; i++) a[i]--;
		int[] last=new int[n];
		boolean[] used=new boolean[n];
		Arrays.fill(last, -1);
		int[][] answers=new int[n][2];
		int maxThickness=(n+nCopies-2)/(nCopies-1);
//		System.out.println("Max thickness: "+maxThickness);
		for (int i=0; i<a.length; i++) {
			if (used[a[i]]) continue; //handled this color
			if (last[a[i]]==-1) {
				last[a[i]]=i;
				continue;
			}
			int rangeStart=last[a[i]], rangeEnd=i;
//			System.out.println("Considering "+rangeStart+" "+rangeEnd+" "+st.max(rangeStart, rangeEnd));
			if (st.max(rangeStart, rangeEnd)<maxThickness) {
				st.rangeAdd(rangeStart, rangeEnd, 1);
				used[a[i]]=true;
				answers[a[i]]=new int[] {rangeStart, rangeEnd};
			}
			last[a[i]]=i;
		}
		for (int i=0; i<n; i++) if (!used[i]) throw null;
		for (int i=0; i<n; i++) {
			System.out.println(1+answers[i][0]+" "+(1+answers[i][1]));
		}
		
	}

	static class ST {
		int leftmost, rightmost;
		ST lChild, rChild;
		int max, toProp;
		
		public ST(int leftmost, int rightmost) {
			this.leftmost=leftmost;
			this.rightmost=rightmost;
			if (leftmost!=rightmost) {
				int mid=(leftmost+rightmost)/2;
				lChild=new ST(leftmost, mid);
				rChild=new ST(mid+1, rightmost);
			}
		}
		
		int max() {
			return max+toProp;
		}
		
		void recalc() {
			if (leftmost==rightmost) return;
			max=Math.max(lChild.max(), rChild.max());
		}
		void prop() {
			if (leftmost!=rightmost) {
				lChild.toProp+=toProp;
				rChild.toProp+=toProp;
				toProp=0;
			}
			recalc();
		}
		
		void rangeAdd(int l, int r, int d) {
			if (l>rightmost || r<leftmost) return;
			if (l<=leftmost && r>=rightmost) {
				toProp+=d;
				return;
			}
			prop();
			lChild.rangeAdd(l, r, d);
			rChild.rangeAdd(l, r, d);
			recalc();
		}
		int max(int l, int r) {
			if (l>rightmost || r<leftmost) return Integer.MIN_VALUE;
			if (l<=leftmost && r>=rightmost) {
				return max();
			}
			prop();
			return Math.max(lChild.max(l, r), rChild.max(l, r));
		}
	}
	
	static void sort(int[] a) {
		ArrayList<Integer> l=new ArrayList<>();
		for (int i:a) l.add(i);
		Collections.sort(l);
		for (int i=0; i<a.length; i++) a[i]=l.get(i);
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}

	
}
