Since Sonya has just learned the basics of matrices, she decided to play with them a little bit.

Sonya imagined a new type of matrices that she called rhombic matrices. These matrices have exactly one zero, while all other cells have the Manhattan distance to the cell containing the zero. The cells with equal numbers have the form of a rhombus, that is why Sonya called this type so.

The Manhattan distance between two cells ($x_1$, $y_1$) and ($x_2$, $y_2$) is defined as $|x_1 - x_2| + |y_1 - y_2|$. For example, the Manhattan distance between the cells $(5, 2)$ and $(7, 1)$ equals to $|5-7|+|2-1|=3$. [Image] Example of a rhombic matrix. 

Note that rhombic matrices are uniquely defined by $n$, $m$, and the coordinates of the cell containing the zero.

She drew a $n\times m$ rhombic matrix. She believes that you can not recreate the matrix if she gives you only the elements of this matrix in some arbitrary order (i.e., the sequence of $n\cdot m$ numbers). Note that Sonya will not give you $n$ and $m$, so only the sequence of numbers in this matrix will be at your disposal.

Write a program that finds such an $n\times m$ rhombic matrix whose elements are the same as the elements in the sequence in some order.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 10^6$) — the number of cells in the matrix.

The second line contains $t$ integers $a_1, a_2, \ldots, a_t$ ($0\leq a_i< t$) — the values in the cells in arbitrary order.


-----Output-----

In the first line, print two positive integers $n$ and $m$ ($n \times m = t$) — the size of the matrix.

In the second line, print two integers $x$ and $y$ ($1\leq x\leq n$, $1\leq y\leq m$) — the row number and the column number where the cell with $0$ is located.

If there are multiple possible answers, print any of them. If there is no solution, print the single integer $-1$.


-----Examples-----
Input
20
1 0 2 3 5 3 2 1 3 2 3 1 4 2 1 4 2 3 2 4

Output
4 5
2 2

Input
18
2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1

Output
3 6
2 3

Input
6
2 1 0 2 1 2

Output
-1



-----Note-----

You can see the solution to the first example in the legend. You also can choose the cell $(2, 2)$ for the cell where $0$ is located. You also can choose a $5\times 4$ matrix with zero at $(4, 2)$.

In the second example, there is a $3\times 6$ matrix, where the zero is located at $(2, 3)$ there.

In the third example, a solution does not exist.

Difficulty: HARD
Tags: Complete search

Implementation

Constructive algorithms
Skill types: Complete search

Starter code:

Solutions:
import functools
import time

def timer(func):

	@functools.wraps(func)
	def wrapper(*args, **kwargs):
		stime = time.perf_counter()
		res = func(*args, **kwargs)
		elapsed = time.perf_counter() - stime
		print(f'{func.__name__} in {elapsed:.4f} secs')
		return res
	return wrapper

class solver:

	def __init__(self):
		t = int(input())
		a = list(map(int, input().strip().split()))

		def build(n, m, r, c):
			if not (0 <= r and r < n and (0 <= c) and (c < m)):
				return []
			ret = [0] * t
			for i in range(n):
				for j in range(m):
					ret[abs(r - i) + abs(c - j)] += 1
			return ret
		a.sort()
		h = [0] * t
		amax = 0
		for ai in a:
			h[ai] += 1
			amax = max(amax, ai)
		r = 0
		while r + 1 < t and h[r + 1] == (r + 1) * 4:
			r += 1
		n = 1
		while n * n <= t:
			for transposed in [False, True]:
				if t % n == 0:
					m = t // n
					c = n - 1 - r + (m - 1 - amax)
					f = build(n, m, r, c) if not transposed else build(n, m, c, r)
					if h == f:
						print(f'{n} {m}')
						if not transposed:
							print(f'{r + 1} {c + 1}')
						else:
							print(f'{c + 1} {r + 1}')
						exit(0)
			n += 1
		print('-1')
solver()


from collections import Counter as c

def maker(m, n, x, y, a):
	(small, larg) = (min(x, y), max(x, y))
	k1 = [i + 1 for i in range(small)] + [small for i in range(small, larg)] + [small + larg - i - 1 for i in range(larg, small + larg)] + [0 for i in range(small + larg, a + 1)]
	(small, larg) = (min(x, n - y + 1), max(x, n - y + 1))
	k2 = [i + 1 for i in range(small)] + [small for i in range(small, larg)] + [small + larg - i - 1 for i in range(larg, small + larg)] + [0 for i in range(small + larg, a + 1)]
	(small, larg) = (min(m - x + 1, n - y + 1), max(m - x + 1, n - y + 1))
	k3 = [i + 1 for i in range(small)] + [small for i in range(small, larg)] + [small + larg - i - 1 for i in range(larg, small + larg)] + [0 for i in range(small + larg, a + 1)]
	(small, larg) = (m - x + 1, y)
	k4 = [i + 1 for i in range(small)] + [small for i in range(small, larg)] + [small + larg - i - 1 for i in range(larg, small + larg)] + [0 for i in range(small + larg, a + 1)]
	k = [k1[i] + k2[i] + k3[i] + k4[i] for i in range(a + 1)]
	for i in range(x):
		k[i] -= 1
	for i in range(y):
		k[i] -= 1
	for i in range(m - x + 1):
		k[i] -= 1
	for i in range(n - y + 1):
		k[i] -= 1
	k[0] = 1
	return k
(t, d) = (int(input()), dict(c(map(int, input().split()))))
if t == 1:
	if 0 in d:
		print(1, 1)
		print(1, 1)
	else:
		print(-1)
elif any([i not in d for i in range(max(d))]):
	print(-1)
else:
	(n, a, l, flag) = (int(t ** 0.5) + 1, max(d), [], False)
	d = [d[i] for i in range(a + 1)]
	if d[0] != 1:
		print(-1)
		flag = True
	if not flag:
		for index in range(1, a + 1):
			if d[index] > 4 * index:
				print(-1)
				flag = True
			if d[index] < index * 4:
				break
		if not flag:
			for m in range(2 * index - 1, n):
				if not t % m:
					n = t // m
					if (m + n) // 2 <= a <= m + n - 2 and 2 * index - 1 <= n:
						l.append((m, n))
			for (m, n) in l:
				t = [(m - index + 1, a + index + 1 - m), (a + index + 1 - n, n - index + 1)]
				for (x, y) in t:
					if m // 2 < x <= m and n // 2 < y <= n:
						if d == maker(m, n, x, y, a):
							print(m, n)
							print(x, y)
							flag = True
							break
				if flag:
					break
			else:
				print(-1)


from math import sqrt
from collections import Counter

def f(h, w, y, x):
	return h * w * (h + w - (x + y + 1) * 2) // 2 + h * x * (x + 1) + w * y * (y + 1)

def check(h, w, y, x, cnt):
	for i in range(1, y + 1):
		for j in range(i + 1, i + x + 1):
			cnt[j] -= 1
		for j in range(i, i + w - x):
			cnt[j] -= 1
	for i in range(h - y):
		for j in range(i + 1, i + x + 1):
			cnt[j] -= 1
		for j in range(i, i + w - x):
			cnt[j] -= 1
	if any(cnt.values()):
		return
	print(f'{h} {w}\n{y + 1} {int(x) + 1}')
	raise TabError

def getyx(h, w, tot, cnt):
	b = (w - 1) * 0.5
	c = h * (tot - h * (w * w - 2 * w * (1 - h) - 1) * 0.25)
	for y in range((h + 3) // 2):
		d = c - h * y * (w * y - h * w + w)
		if d >= 0:
			x = b - sqrt(d) / h
			if x.is_integer() and x >= 0.0:
				check(h, w, y, int(x), cnt.copy())

def main():
	(n, l) = (int(input()), list(map(int, input().split())))
	(cnt, r, R, tot) = (Counter(l), 1, max(l), sum(l))
	for r in range(1, R + 1):
		if cnt[r] < r * 4:
			break
	try:
		for h in range(r * 2 - 1, int(sqrt(n)) + 1):
			if not n % h:
				w = n // h
				if f(h, w, h // 2, w // 2) <= tot <= f(h, w, 0, 0):
					getyx(h, w, tot, cnt)
	except TabError:
		return
	print(-1)
main()


def get(n, m, a, b, t):
	freq = [0] * (t + 1)
	for i in range(n):
		for j in range(m):
			val = abs(i - a) + abs(j - b)
			freq[val] += 1
	return freq
t = int(input())
a = list(map(int, input().split()))
mx = max(a)
f = [0] * (t + 1)
for i in a:
	f[i] += 1
b = 1
for i in range(1, mx + 1):
	if f[i] != 4 * i:
		b = i
		break
n = 1
a = -1
x = 0
y = 0
mila = False
while n * n <= t:
	if t % n == 0:
		m = t // n
		a = n + m - mx - b
		(x, y) = (n, m)
		if a > 0 and a <= n and (b > 0) and (b <= m) and (f == get(n, m, a - 1, b - 1, t)):
			mila = True
			break
		if a > 0 and a <= m and (b > 0) and (b <= n) and (f == get(n, m, b - 1, a - 1, t)):
			mila = True
			(a, b) = (b, a)
			break
	n += 1
if not mila:
	print(-1)
else:
	print(x, y)
	print(a, b)


import sys
from collections import Counter
from itertools import chain

def i_ints():
	return map(int, sys.stdin.readline().split())

def check(w, h, x, y, c):
	counts = Counter(chain.from_iterable((range(abs(i - x), abs(i - x) + y) for i in range(1, w + 1))))
	counts += Counter(chain.from_iterable((range(abs(i - x) + 1, abs(i - x) + 1 + (h - y)) for i in range(1, w + 1))))
	return c == counts
(t,) = i_ints()
a = Counter(i_ints())
i = 0
for i in range(1, t + 1):
	if a[i] != 4 * i:
		break
x = i
B = max(a)

def main():
	for w in range(2 * x - 1, int(t ** 0.5) + 2):
		if t % w:
			continue
		h = t // w
		y = w + h - B - x
		if y >= x and h >= 2 * y - 1 and check(w, h, x, y, a):
			return '%s %s\n%s %s' % (w, h, x, y)
		(w, h) = (h, w)
		y = w + h - B - x
		if y >= x and h >= 2 * y - 1 and check(w, h, x, y, a):
			return '%s %s\n%s %s' % (w, h, x, y)
	return -1
print(main())


import math
t = int(input())
L = [int(x) for x in input().split()]
L.sort()
ma = max(L)
S = 2 * sum(L)
Div = []
for i in range(1, int(math.sqrt(t)) + 1):
	if t % i == 0:
		Div.append(i)
		Div.append(t // i)
if len(Div) >= 2:
	if Div[-1] == Div[-2]:
		Div.pop()
Div.sort()
D = {}
for i in L:
	if i in D:
		D[i] += 1
	else:
		D[i] = 1
Candidates = []
for i in range(len(Div)):
	n = Div[i]
	m = Div[-i - 1]
	for j in range(ma, ma - m, -1):
		if D.get(j, -1) > ma - j + 1:
			break
	else:
		j -= 1
	good = ma - j
	y = 1 + (m - good) // 2
	x = m + n - ma - y
	T = x + y
	if y >= 1:
		if y <= (m + 1) // 2:
			if x <= (n + 1) // 2:
				if m * (x * (x - 1) + (n - x) * (n - x + 1)) + n * ((T - x) * (T - x - 1) + (m - T + x) * (m - T + x + 1)) == S:
					temp = []
					for j in range(m * n):
						temp.append(abs(1 + j % n - x) + abs(1 + j // n - y))
					temp.sort()
					if temp == L:
						print(n, m)
						print(x, y)
						break
else:
	print(-1)