Many computer strategy games require building cities, recruiting army, conquering tribes, collecting resources. Sometimes it leads to interesting problems. 

Let's suppose that your task is to build a square city. The world map uses the Cartesian coordinates. The sides of the city should be parallel to coordinate axes. The map contains mines with valuable resources, located at some points with integer coordinates. The sizes of mines are relatively small, i.e. they can be treated as points. The city should be built in such a way that all the mines are inside or on the border of the city square. 

Building a city takes large amount of money depending on the size of the city, so you have to build the city with the minimum area. Given the positions of the mines find the minimum possible area of the city.


-----Input-----

The first line of the input contains number n — the number of mines on the map (2 ≤ n ≤ 1000). Each of the next n lines contains a pair of integers x_{i} and y_{i} — the coordinates of the corresponding mine ( - 10^9 ≤ x_{i}, y_{i} ≤ 10^9). All points are pairwise distinct.


-----Output-----

Print the minimum area of the city that can cover all the mines with valuable resources.


-----Examples-----
Input
2
0 0
2 2

Output
4

Input
2
0 0
0 3

Output
9

Difficulty: interview

Starter code:

Solutions:
n = int(input())
xa = []
ya = []
for _ in range(n):
	x, y = map(int,input().split())
	xa.append(x)
	ya.append(y)
print(max(max(xa)-min(xa),max(ya)-min(ya))**2)

n = int(input())
x = [0]*n
y = [0]*n
for i in range(n):
    x[i],y[i] = map(int,input().split())
x.sort()
y.sort()
res = (max(x[-1]-x[0],y[-1]-y[0]))**2
print(res)

from fractions import gcd
from sys import stdin

lines = list([_f for _f in stdin.read().split('\n') if _f])

def parseline(line):
	return list(map(int, line.split()))

lines = list(map(parseline, lines))

n, = lines[0]

INF = 10**9 + 1

maxx = -INF
maxy = -INF
minx = INF
miny = INF

for xi,yi in lines[1:n+1]:
	maxx = max(maxx, xi)
	minx = min(minx, xi)
	maxy = max(maxy, yi)
	miny = min(miny, yi)

print( max(maxx - minx, maxy - miny) ** 2)


ps = [tuple(map(int, str.split(input()))) for _ in range(int(input()))]
lx = rx = ty = by = None
foo = lambda v, cv, f: cv if v is None else f(v, cv)
for x, y in ps:

    lx = foo(lx, x, min)
    rx = foo(rx, x, max)
    by = foo(by, y, min)
    ty = foo(ty, y, max)

print(max(abs(lx - rx), abs(by - ty)) ** 2)


n = int(input())
maxx = maxy = -10 ** 10
minx = miny = 10 ** 10
for i in range(n):
    x, y = list(map(int, input().split()))
    if x > maxx:
        maxx = x

    if y > maxy:
        maxy = y

    if y < miny:
        miny = y

    if x < minx:
        minx = x

print(max((maxx - minx), (maxy - miny)) ** 2)



#!/usr/bin/env python3

number_of_mines = int(input())
x_coords = []
y_coords = []
for _ in range(number_of_mines):
    x, y = (int(value) for value in input().split())
    x_coords.append(x)
    y_coords.append(y)
print(max(abs(max(x_coords) - min(x_coords)), abs(max(y_coords) - min(y_coords))) ** 2)
    



n = int(input())
minx, maxx, miny, maxy = (10**10), -(10**10), (10**10), -(10**10)
for i in range(n):
    x, y = list(map(int, input().split()))
    if x > maxx:
        maxx = x
    if y > maxy:
        maxy = y
    if x < minx:
        minx = x
    if y < miny:
        miny = y
print(max(maxx - minx, maxy - miny)**2)

#fin = open("input.txt")
n = int(input())
#n = int(fin.readline())
X1, Y1, X2, Y2 = 10 ** 9 * 2, 10 ** 9 * 2, -10 ** 9 * 2, -10 ** 9 * 2
for i in range(n):
	x, y = list(map(int, input().split()))
	#x, y = map(int, fin.readline().split())
	X1, Y1, X2, Y2 = min(X1, x), min(Y1, y), max(X2, x), max(Y2, y)
print(max((X2 - X1), (Y2 - Y1)) ** 2)



n = int(input())


max_r = 0

x, y = map(int, input().split())
minX = x
maxX = x
minY = y
maxY = y
for i in range(n - 1):
    x, y = map(int, input().split())
    minX = min(minX, x)
    maxX = max(maxX, x)
    minY = min(minY, y)
    maxY = max(maxY, y)

print(max(maxX- minX, maxY - minY)** 2)

n = int(input())
x = []
y = []
for i in range(n):
    p, q = list(map(int, input().split()))
    x.append(p)
    y.append(q)
dx = max(x) - min(x)
dy = max(y) - min(y)
print(max(dx, dy) ** 2)




n = int(input())
mx=10000000000
my=10000000000
vx=-10000000000
vy=-10000000000
for i in range(n):
    a, b = map(int, input().split())
    mx = min(mx,a)
    vx = max(vx,a)
    my = min(my,b)
    vy = max(vy,b)
print(max(vx-mx,vy-my)*max(vx-mx,vy-my))

n = int(input())
x, y = map(int,input().split())
xmin = x
xmax = x
ymin = y
ymax = y
for i in range(n-1):
    x, y = map(int,input().split())
    xmin = min(xmin, x)
    xmax = max(xmax, x)
    ymin = min(ymin, y)
    ymax = max(ymax, y)
print(max(ymax - ymin, xmax - xmin) ** 2)

n = int(input())
x = []
y = []
for i in range(n):
    a, b = list(map(int, input().split()))
    x.append(a)
    y.append(b)

x.sort()
y.sort()

print(max(x[-1] - x[0], y[-1] - y[0]) ** 2)


n=int(input(""))
a=[]
b=[]
for i in range(n):
    x,y=input("").split()
    a.append(int(x))
    b.append(int(y))
max=0
for i in range(n):
    for j in range(i+1,n):
        if (a[i]-a[j])**2>max:
            max=(a[i]-a[j])**2
            d={"a":max}
        if (b[i]-b[j])**2>max:
            max=(b[i]-b[j])**2
            d={"a":max}
        

            
print(d["a"])


n = int(input())
minX = 1000000005
minY = minX
maxX = -1000000005
maxY = maxX

for i in range(n):
    t, t2 = list(map(int, input().split()))
    minY = min(minY, t2)
    maxY = max(maxY, t2)
    minX = min(minX, t)
    maxX = max(maxX, t)

print(max(maxX-minX,maxY-minY)**2)


def shag (x,y,xmin,ymin):
    a, b = list(map(int, input(). split()))
    x=max(a,x)
    y=max(b,y)
    xmin=min (a,xmin)
    ymin=min (b,ymin)
    return x, y, xmin, ymin

k=int(input())
x, y = list(map(int, input().split()))
xmin=x
ymin=y
for i in range (1,k,1):
   x,y,xmin,ymin = shag (x,y,xmin,ymin)

print(pow(max(x-xmin,y-ymin),2))


a1 = []
a2 = []
x = int(input())
for i in range(x):
    a, b = map(int, input().split(' '))
    a1.append(a)
    a2.append(b)
print(max(max(a1)-min(a1), max(a2)-min(a2))**2)

#!/bin/env python3
n=int(input())
x,y=input().split(' ')
x,y=int(x),int(y)
min_y=y
max_y=y
min_x=x
max_x=x

for x in range(n-1):
    x,y=input().split(' ')
    x,y=int(x),int(y)
    if x>max_x:
        max_x=x
    if x<min_x:
        min_x=x
    if y>max_y:
        max_y=y
    if y<min_y:
        min_y=y

print(max((max_y-min_y),(max_x-min_x))**2)


n = int(input())
xs = []
ys = []
for i in range(n):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)
print(max(max(xs) - min(xs), max(ys) - min(ys)) **2)

a = int(input(""))
XlistOfCoordinates = []
YlistOfCoordinates = []
for value in range(a):
    y = input("").split(" ")
    XlistOfCoordinates.append(int(y[0]))
    YlistOfCoordinates.append(int(y[1]))
print(max(max(XlistOfCoordinates)-min(XlistOfCoordinates),max(YlistOfCoordinates)-min(YlistOfCoordinates))**2)


n = int (input())
pointx,pointy=[],[]
for i in range(n):
    x , y = map(int,input().split())
    pointx.append(x)
    pointy.append(y)
ans = max(max(pointx)-min(pointx),max(pointy)-min(pointy))
print(ans  * ans)

n = int(input())
xl, yl = list(map(int, input().split()))
xr, yr = list(map(int, input().split()))
if xl > xr : xl, xr = xr, xl
if yl > yr : yl, yr = yr, yl
for i in range(n-2):
    x, y = list(map(int, input().split()))
    xl = min(xl, x)
    xr = max(xr, x)
    yl = min(yl, y)
    yr = max(yr, y)
print(max(yr-yl, xr-xl)**2)

    


n = int(input())
px, py = [], []
for i in range(n):
    x, y = list(map(int, input().split()))
    px.append(x)
    py.append(y)
print(max(max(px)-min(px), max(py)-min(py))**2)


    


n = int(input())
x, y = (int(x) for x in input().split())
x1, y1, x2, y2 = x, y, x, y
for i in range(n - 1):
    x, y = (int(x) for x in input().split())
    x1 = min(x1, x)
    x2 = max(x2, x)
    y1 = min(y1, y)
    y2 = max(y2, y)
print(max(x2 - x1, y2 - y1) ** 2)

def solve(ps):
    return max(
            max(ps, key=lambda x: x[0])[0] - min(ps, key=lambda x: x[0])[0],
            max(ps, key=lambda x: x[1])[1] - min(ps, key=lambda x: x[1])[1],
           )**2

n = int(input())
ps = [list(map(int, input().split())) for i in range(n)]
print(solve(ps))