Colors and Intervals solution codeforces

Colors and Intervals solution codeforces



The numbers 1,2,,nk1,2,…,n⋅k are colored with nn colors. These colors are indexed by 1,2,,n1,2,…,n. For each 1in1≤i≤n, there are exactly kk numbers colored with color ii.

Let [a,b][a,b] denote the interval of integers between aa and bb inclusive, that is, the set {a,a+1,,b}{a,a+1,…,b}. You must choose nn intervals [a1,b1],[a2,b2],,[an,bn][a1,b1],[a2,b2],…,[an,bn] such that:

  • for each 1in1≤i≤n, it holds 1ai<bink1≤ai<bi≤n⋅k;
  • for each 1in1≤i≤n, the numbers aiai and bibi are colored with color ii;
  • each number 1xnk1≤x≤n⋅k belongs to at most nk1⌈nk−1⌉ intervals.

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

Input

The first line contains two integers nn and kk (1n1001≤n≤1002k1002≤k≤100) — the number of colors and the number of occurrences of each color.

The second line contains nkn⋅k integers c1,c2,,cnkc1,c2,…,cnk (1cjn1≤cj≤n), where cjcj is the color of number jj. It is guaranteed that, for each 1in1≤i≤n, it holds cj=icj=i for exactly kk distinct indices jj.

Output

Output nn lines. The ii-th line should contain the two integers aiai and bibi.

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

Examples

input

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

output

Copy
4 5
1 7
8 11
6 12

input

Copy
1 2
1 1

output

Copy
1 2

input

Copy
3 3
3 1 2 3 2 1 2 1 3

output

Copy
6 8
3 7
1 4

input

Copy
2 3
2 1 1 1 2 2

output

Copy
2 3
5 6
Note

In the first sample, each number can be contained in at most 431=2⌈43−1⌉=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][1,2], and each number is indeed contained in at most 121=1⌈12−1⌉=1 interval.

In the third sample, each number can be contained in at most 331=2⌈33−1⌉=2 intervals. The output is described by the following picture:

Colors and Intervals solution codeforces

 



Also read : What a Reversal solution codeforces

Leave a Comment