Recently Pashmak has been employed in a transportation company. The company has k buses and has a contract with a school which has n students. The school planned to take the students to d different places for d days (each day in one place). Each day the company provides all the buses for the trip. Pashmak has to arrange the students in the buses. He wants to arrange the students in a way that no two students become close friends. In his ridiculous idea, two students will become close friends if and only if they are in the same buses for all d days.

Please help Pashmak with his weird idea. Assume that each bus has an unlimited capacity.


-----Input-----

The first line of input contains three space-separated integers n, k, d (1 ≤ n, d ≤ 1000; 1 ≤ k ≤ 10^9).


-----Output-----

If there is no valid arrangement just print -1. Otherwise print d lines, in each of them print n integers. The j-th integer of the i-th line shows which bus the j-th student has to take on the i-th day. You can assume that the buses are numbered from 1 to k.


-----Examples-----
Input
3 2 2

Output
1 1 2 
1 2 1 

Input
3 2 1

Output
-1



-----Note-----

Note that two students become close friends only if they share a bus each day. But the bus they share can differ from day to day.

Difficulty: interview

Starter code:

Solutions:
3

import sys

# 1 <= n, d <= 1000, 1 <= k <= 10**9
n, k, d = list(map(int, sys.stdin.readline().split()))

no_sol = False
solution = [[1 for j in range(n)] for i in range(d)]


def schedule(i, j, level):
    nonlocal no_sol
    if level >= d:
        no_sol = True
        return
    count = j - i
    chunk = count // k
    extra = count % k
    r = i
    for t in range(min(k, count)):
        size = chunk + (1 if t < extra else 0)
        for z in range(size):
            solution[level][r+z] = t+1
        if size > 1:
            schedule(r, r + size, level + 1)
        r += size

if k == 1:
    if n > 1:
        no_sol = True
else:
    schedule(0, n, 0)

if no_sol:
    print(-1)
else:
    for l in solution:
        print(' '.join(str(x) for x in l))


n, k, d = list(map(int, input().split()))
if k < n ** (1 / d):
    print(-1)
else:
    k1 = 1
    for i in range(d):
        print(" ".join(map(str, [(j // k1 % k) + 1 for j in range(n)])))
        k1 = k * k1


n,k,d = map(int, input().split())
if (n > k ** d):
    print(-1)
    return
for i in range(d):
    power = k**i
    resArray = [((j // power) % k +1) for j in range(n)]
    #for j in range(n//(k**i)+1):
    #    resArray.extend([(j % k) + 1] * (k ** i))
    print(' '.join(map(str,resArray)))

In = lambda :  list(map(int,input().split()))
n , k ,d = In()
if(n > k**d):
    print(-1)
else :
    k1 = 1
    for i in range(d):
        print(" ".join(map(str, [(j // k1 % k) + 1 for j in range(n)])))
        k1 = k1 * k;


n,k,d = map(int, input().split())
if (n > k ** d):
    print(-1)
    return
for i in range(d):
    power = k**i
    resArray = [((j // power) % k +1) for j in range(n)]
    print(' '.join(map(str,resArray)))

import fileinput
import math

for line in fileinput.input():   
    inp = [ int(i) for i in line.split()]

n = inp[0]
k = inp[1]
d = inp[2]


if n > k ** d:
    print(-1)
else:
    for i in range(d):
        pr = k**i
        results = [(j//pr % k) + 1 for j in range(n)]
        print(' '.join(map(str,results)))

def f(t):
    i = -1
    t[i] += 1
    while t[i] > k:
        t[i] = 1
        i -= 1
        t[i] += 1
    return list(map(str, t))
n, k, d = map(int, input().split())
if k ** d < n: print(-1)
else:
    t = [1] * d
    t[-1] = 0
    s = [f(t) for i in range(n)]
    print('\n'.join([' '.join(t) for t in zip(*s)]))

m=list(input().split())
n=int(m[0])
k=int(m[1])
d=int(m[2])

if n==1:
    for i in range(d):
        print("1")
    return
if k==1:
    print("-1")
    return
if k>=n:
    m=list(i for i in range(n))
    o=""
    for j in range(1,n+1):
        o+=" "+str(j)
    o=o[1:] 
    for i in range(d):
        print(o)
    return
if d==1:
    print('-1')
    return
if d>=n:
    m=list("1" for i in range(n))
    for i in range(n):
        m[i]="2"
        #print(m)
        o=str(m[0])
        for j in range(1,n):
            o+=" "+str(m[j])
        print(o)
        #m[i]="1"
    for i in range(n,d):
        #print(m)
        print(o)
    return

from math import ceil, floor
tc=ceil(n/k) #days
tf=floor(n/k) #len k

if n>(k**d):
    print('-1')
    return

sc=1
for stp in range(1,d+1):
    o=""
    kc=0
    
    while kc<n:
        for kk in range(1,k+1):
            for i in range (sc):
                if kc<n:
                    o+=' '+str(kk)
                    kc+=1
                else:
                    break
    sc*=k #change from 2
    print(o[1:])


#!/usr/bin/env python3

n, k, d = list(map(int, input().split()))
if k ** d < n:
    print(-1)
else:
    for i in range(d):
        p = k ** i
        arr = [j // p % k + 1 for j in range(n)]
        print(' '.join(map(str, arr)))


#http://codeforces.com/problemset/problem/459/C

# Input of the values
n, k, d = list(map(int, input().split()))

#Convention : 	Busses are numbered from 1 to k
#				Students are numbered from 0 to k - 1
# 				Days are numbered from 0 to k - 1

# Variable for success
success = True

# answer is a  2-d array that stores the bus number each student used on a particular day
# Students are numbered from 0 to n-1
answer = [[] for x in range(n)]

# Initialising the first students details manually
# The first student uses the bus 1 for all of the days
answer[0] = [1 for x in range(d)]

# we will be filling the details for each and every student and 
# would print -1 only if we cannot allot any bus number to the next student
for i_th_student in range(1,n):
	
	#answer for previous value
	i_minus_one_student = answer[i_th_student - 1]

	# Answer to the current student
	current_student = list(i_minus_one_student)

	# Days are also numbered from 0 to d-1
	for i_th_day in reversed(list(range(d))):

		# the condition to change the bus number 
		if i_minus_one_student[i_th_day] < k :

			current_student[i_th_day] += 1

			# all the numbers next to it are reset
			for i in range(i_th_day + 1, d):
				current_student[i] = 1
			
			break
	
	#Save the value
	answer[i_th_student] = current_student
	
	#Failed
	if current_student == i_minus_one_student:
		success = False
		break

# printing the output
if not(success):
	print ("-1")

else:
	# ans_trans is used for giving the output fast
	answer_trans= [[] for i in range(d)]
	for y in range(n):
		i = 0
		for x in answer[y]:
			answer_trans[i].append(x)
			i += 1
	for bla in answer_trans:
		print(' '.join(map(str, bla)))


load = [int(i) for i in input().split()]

n = load[0]
k = load[1]
d = load[2]

p = 1
for i in range(d):
    p *= k
    if p >= n:
        break

if n > p:
    print(-1)
else:
    nums = [i for i in range(n)]
    for i in range(d):
        buff = ""
        for j in range(n):
            buff += str(nums[j] % k + 1) + ' '
            nums[j] //= k
        print(buff)

    


def f(t):
    i = -1
    t[i] += 1
    while t[i] > k:
        t[i] = 1
        i -= 1
        t[i] += 1
    return list(map(str, t))
n, k, d = map(int, input().split())
if k ** d < n: print(-1)
else:
    t = [1] * d
    t[-1] = 0
    s = [f(t) for i in range(n)]
    print('\n'.join([' '.join(t) for t in zip(*s)]))

3

import sys

n, k, d = list(map(int, sys.stdin.readline().split()))

x = 1
while x ** d < n:
    x += 1
    
if x > k:
    sys.stdout.write("-1\n")
    return
    
ans = [[1 for i in range(d)] for j in range(n)]
for i in range(1, n):
    for j in range(d): 
        ans[i][j] = ans[i - 1][j]
    ans[i][d - 1] += 1
    memo = 0
    for j in range(d - 1, -1, -1):
        ans[i][j] += memo
        memo = 0
        if ans[i][j] > x:
            memo = ans[i][j] - x
            ans[i][j] = 1
            
for i in range(d):
    sys.stdout.write(' '.join([str(ans[j][i]) for j in range(n)]) + '\n')

3

import sys

n, k, d = list(map(int, sys.stdin.readline().split()))

x = 1
while x ** d < n:
    x += 1
    
if x > k:
    sys.stdout.write("-1\n")
    return
    
ans = [[1 for i in range(n)] for j in range(d)]
for i in range(1, n):
    for j in range(d): 
        ans[j][i] = ans[j][i - 1]
    ans[d - 1][i] += 1
    memo = 0
    for j in range(d - 1, -1, -1):
        ans[j][i] += memo
        memo = 0
        if ans[j][i] > x:
            memo = ans[j][i] - x
            ans[j][i] = 1
            
for i in range(d):
    sys.stdout.write(' '.join(map(str, ans[i])) + '\n')

n, k, d = [int(k) for k in input().split()]
base_rep = [[0 for _ in range(d)] for _ in range(n)]


if k**d  < n:
    print(-1)
else:
    for j in range(n):
        num = j
        i=0
        while num >= k**i:
           i+=1
        i-=1
        #print(i)
        while num:
            base_rep[j-1][i] = num//k**i
            num = num % k**i
            i -=1
    for i in range(d):
        s =""
        for j in range(n):
            s += str(base_rep[j][i]+1) + " "
        print(s)

def add1(array, base):
    array[-1] += 1
    array = [0] + array
    k= len(array)-1
    while array[k]>=base:
        array[k] -= base
        array[k-1] += 1
        k -= 1
    if array[0] == 0:
        return array[1:]
    return array


n, k, d = list(map(int, input().split(' ')))
if n == 1:
    for i in range(d):
        print(1)
    quit()
if n > k**d:
    print("-1")

    quit()
arr = []
array = [0]*d
for i in range(n):
    arr.append(array)
    array = add1(array[:], k)

new = [[0]*len(arr) for _ in range(len(arr[0]))]
for i in range(len(arr)):
    for j in range(len(arr[0])):
        new[j][i] = arr[i][j]+1

for i in new:
    print(' '.join([str(x) for x in i]))


n,k,d=list(map(int,input().split()))
if n>k**d:print((-1));return
K=1
for j in range(d):
    print(" ".join([str(i//K%k +1) for i in range(n)]))
    K*=k


a = input()
b = a.split()
n = int(b[0])
k = int(b[1])
d = int(b[2])
if n > k**d:
    print(-1)
    return
table = [[1]*d]
for i in range(n - 1):
    v = list(table[-1])
    j = len(v)-1
    while v[j]==k:
        v[j]=1
        j = j - 1
    v[j] = v[j] + 1
    table.append(v)
current_power = 1
answer = [0] * n
for m in range(0, d):
    current_value = 1
    for s in range(0, n):
        if s % current_power == 0 and s > 0:
            current_value = current_value % k + 1
        answer[s] = str(current_value)
    current_power *= k
    print(" ".join(answer))


a = input()
b = a.split()
n = int(b[0])
k = int(b[1])
d = int(b[2])
raw = [' ']*n
if n > k**d:
	print(-1)
	return
table = [[1]*d]
p = 1
for i in range(d):
	cv = 1
	for j in range(n):
		if j % p == 0 and j != 0:
			cv = cv + 1
			if cv == k+1:
				cv = 1
		raw[j]= str(cv)
	print(' '.join(raw))
	p = p * k

n,k,d=map(int,input().split())
if n>k**d:print(-1);return
K=1
for j in range(d):
    print(" ".join([str(i//K%k +1) for i in range(n)]))
    K*=k

# -*- coding: utf-8 -*-
import sys

def main():
    n,k,d = map(int,sys.stdin.readline().split())

    blocksize = n

    for i in range(d):
        blocksize = blocksize//k + (blocksize%k != 0)
    # print(blocksize)

    if(blocksize > 1):
        print("-1")
        return

    for days in range(d):
        i = 0
        bus = 1
        while i < n:
            for j in range(blocksize):
                sys.stdout.write(str(bus) + ' ')
                i += 1
                if i == n: break
            bus += 1
            if(bus > k): bus = 1
        blocksize *= k
        sys.stdout.write('\n')


def __starting_point():
    main()
__starting_point()

n,k,d=map(int,input().split())
if n>k**d:print(-1);return
K=1
for j in range(d):
    print(" ".join([str(i//K%k +1) for i in range(n)]))
    K*=k

import math 
n,k,d = list(map(int,input().split()))
# if math.log(n)>d*math.log(k): chadar%
if n>k**d:
	print(-1)
else:
	# no pgh shit 
	t = 1
	for i in range(d):
		li = []
		for j in range(n):
			li.append((j//t)%k+1)
		print(*li)
		t*=k


n,k,d=list(map(int,input().split()))
if n>k**d:print((-1));return
K=1
for j in range(d):
    print(" ".join([str(i//K%k +1) for i in range(n)]))
    K*=k



n,k,d=list(map(int,input().split()))
if n>k**d:print((-1));return
K=1
for j in range(d):
    print(" ".join([str(i//K%k +1) for i in range(n)]))
    K*=k