Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Chef has n × n array A of non-negative integers. He wants to divide this array by p-1 horizontal dividers and p-1 vertical dividers into p^{2} blocks such that maximum sum of elements of each block will be the smallest. 

More formally, Chef want to choose p-1 horizontal dividers 0 = h_{0} < h_{1} < ... < h_{p} = n and  p-1 vertical dividers 0 = v_{0} < v_{1} < ... < v_{p} = n to minimize the next value: 

------ Input ------ 

The first line of each test file contains two space-separated integers n and p denoting the size of array A and the number of horizontal and vertical dividers.
Each of next n lines contains n space-separated integers A_{i, 1}, A_{i, 2}, ..., A_{i, n} denoting the i^{th} row of the array A. 

------ Output ------ 

The first line of output should contain p-1 space-separated integers h_{1}, h_{2}, ... h_{p-1} denoting the horizontal dividers.

The second line of output should contain p-1 space-separated integers v_{1}, v_{2}, ... v_{p-1} denoting the vertical dividers.

------ Scoring ------ 

Your score for each test case will be calculated by formula described above. Your goal is to minimize this score.
Your total score for the problem will be the sum of scores on all the test cases.
Your solution will be tested only on 20% of the test files during the contest and will be rejudged against 100% after the end of competition.

------ Constraints ------ 

$2 ≤ p ≤ n ≤ 500 $
$1 ≤ A_{i, j} ≤ 10^{9} $

------ Example ------ 

Input:
4 3
1 1 2 2
2 1 2 2
3 1 4 2
4 4 2 2

Output:
2 3
1 3

------ Explanation ------ 

As you can see at the picture below, this array is divided into p^{2} = 9 blocks by p-1 horizontal(red lines) and p-1 vertical(green lines) dividers. Also there are two vertical (v_{0} = 0 and v_{3} = 4) dividers and two horizontal (h_{0} = 0 and h_{3} = 4) for better understanding of this division.

Your score for this test case will be 6 / (4 / 3)^{2} (there are two blocks with sum of elements 6).
This test case won't be in the test data because n ∉ [450..500]. It just for let you understand how scoring works. Also there are another ways to divide this array into 9 parts. All of them will be accepted, but with different scores. 

------ Test data generation ------ 

There will be 20 test files.
For each test file the number n is chosen from the range [450..500] with equal probability. All elements of A are also chosen randomly. For each test case p will be manually selected.

Source: codechef | Difficulty: VERY_HARD


Solutions:
import random
(N, p) = map(int, input().strip().split())
A = [None] * N
for i in range(N):
	A[i] = list(map(int, input().strip().split()))
if p == N:
	for i in range(1, N):
		print(i, end=' ')
	print()
	for i in range(1, N):
		print(i, end=' ')
	print()
F = [False] * N
a = 0
while a != p - 1:
	b = random.randrange(1, N)
	if not F[b]:
		a += 1
		F[b] = True
for i in range(N):
	if F[i]:
		print(i, end=' ')
print()
F = [False] * N
a = 0
while a != p - 1:
	b = random.randrange(1, N)
	if not F[b]:
		a += 1
		F[b] = True
for i in range(N):
	if F[i]:
		print(i, end=' ')


(n, p) = [int(i) for i in input().split()]
arr = []
for _ in range(n):
	arr.append([int(i) for i in input().split()])
hori = []
dhori = {}
for i in arr:
	for j in range(len(i) - 1):
		hori.append(i[j] + i[j + 1])
		if dhori.get(i[j] + i[j + 1], -1) == -1:
			dhori[i[j] + i[j + 1]] = [j + 1]
		else:
			dhori[i[j] + i[j + 1]].append(j + 1)
hori.sort(reverse=True)
veri = []
dveri = {}
for i in range(n - 1, -1, -1):
	for j in range(n - 1):
		x = arr[j][i] + arr[j + 1][i]
		veri.append(x)
		if dveri.get(x, -1) == -1:
			dveri[x] = [j + 1]
		else:
			dveri[x].append(j + 1)
veri.sort(reverse=True)
donex = {}
s = ''
i = 1
cnt = 0
doney = {}
x = []
while i < p:
	for j in dveri[veri[cnt]]:
		if i < p and doney.get(j, -1) == -1:
			x.append(j)
			doney[j] = 1
			i += 1
		if i > p:
			break
	cnt += 1
x.sort()
print(' '.join([str(i) for i in x]))
i = 1
cnt = 0
y = []
while i < p:
	for j in dhori[hori[cnt]]:
		if i < p and donex.get(j, -1) == -1:
			y.append(j)
			donex[j] = 1
			i += 1
		if i > p:
			break
	cnt += 1
y.sort()
print(' '.join([str(i) for i in y]))


import random

def fun(D):
	S = 0
	B = [None] * N
	for i in range(N):
		s = sum(D[i])
		S += s
		B[i] = s
	x = S / N
	f = 0.9
	X = f * x
	s = 0
	c = 0
	for i in range(N):
		if s > X:
			s = 0
			print(i, end=' ')
			c += 1
			if c == p - 1:
				break
		if p - 1 - c == N - i:
			for j in range(i, N):
				print(j, end=' ')
		s += B[i]
	print()
(N, p) = map(int, input().strip().split())
A = [None] * N
for i in range(N):
	A[i] = list(map(int, input().strip().split()))
if p == N:
	for i in range(1, N):
		print(i, end=' ')
	print()
	for i in range(1, N):
		print(i, end=' ')
	print()
else:
	fun(A)
	AT = [[A[j][i] for j in range(N)] for i in range(N)]
	fun(AT)


def div_matrix(sum_matrix, sum_avg):
	size = len(sum_matrix)
	res = list()
	count = 0
	current = 0
	prev = 0
	last = -1
	i = 0
	while i < size:
		if count == p - 2:
			new_avg = 0
			current = 0
			prev = 0
			for j in range(i, size):
				new_avg += sum_matrix[j]
			new_avg //= 2
			for j in range(i, size):
				current += sum_matrix[j]
				if prev <= new_avg <= current:
					if new_avg - prev < current - new_avg and last != j - 1:
						res.append(j)
					else:
						res.append(j + 1)
					return res
				prev = current
		current += sum_matrix[i]
		if prev <= sum_avg <= current:
			if sum_avg - prev < current - sum_avg and last != i - 1:
				res.append(i)
				last = i - 1
				i -= 1
			else:
				res.append(i + 1)
				last = i
			count += 1
			sum_avg = 0
			for j in range(i + 1, size):
				sum_avg += sum_matrix[j]
			sum_avg //= p - count
			prev = 0
			current = 0
			i += 1
			continue
		prev = sum_matrix[i]
		if size - i - 1 == p - count - 1:
			return res + list(range(i + 1, size))
		i += 1
	return res
(n, p) = map(int, input().split())
a = list()
row_sum = list()
for i in range(n):
	temp = map(int, input().split())
	temp = list(temp)
	row_sum.append(sum(temp))
	a.append(temp)
col_sum = [sum(x) for x in zip(*a)]
avg = sum(row_sum) // p
for pos in div_matrix(row_sum, avg):
	print(pos, end=' ')
print()
for pos in div_matrix(col_sum, avg):
	print(pos, end=' ')


import random
(n, p) = list(map(int, input().split()))
A = []
for i in range(n):
	A.append(list(map(int, input().split())))
mv = 0
mc = None
for i in range(n):
	for j in range(n):
		if A[i][j] > mv:
			mv = A[i][j]
			mc = (i, j)
perm1 = list(range(1, n))
perm2 = list(range(1, n))
random.shuffle(perm1)
random.shuffle(perm2)
perm1 = perm1[:p - 1]
perm2 = perm2[:p - 1]
if p > 2:
	if n - p > 1:
		if i + 1 < n and i + 1 in perm1:
			ind = perm1.index(i + 1)
			for newind in range(1, n):
				if newind not in perm1:
					perm1[ind] = newind
		if j + 1 < n and j + 1 in perm2:
			ind = perm2.index(j + 1)
			for newind in range(1, n):
				if newind not in perm2:
					perm2[ind] = newind
	if n - p > 2:
		if i and i in perm1:
			ind = perm1.index(i)
			for newind in range(1, n):
				if newind not in perm1:
					perm1[ind] = newind
		if j and j in perm2:
			ind = perm2.index(j)
			for newind in range(1, n):
				if newind not in perm2:
					perm2[ind] = newind
perm1.sort()
perm2.sort()
print(' '.join([str(x) for x in perm1]))
print(' '.join([str(x) for x in perm2]))


import random
(n, p) = list(map(int, input().split()))
A = []
for i in range(n):
	A.append(list(map(int, input().split())))
perm1 = list(range(1, n))
perm2 = list(range(1, n))
random.shuffle(perm1)
random.shuffle(perm2)
perm1 = perm1[:p - 1]
perm2 = perm2[:p - 1]
perm1.sort()
perm2.sort()
print(' '.join([str(x) for x in perm1]))
print(' '.join([str(x) for x in perm2]))