Programmer Sasha is a student at MIPT (Moscow Institute of Physics and Technology) and he needs to make a laboratory work to pass his finals.

A laboratory unit is a plane with standard coordinate axes marked on it. Physicists from Moscow Institute of Physics and Technology charged the axes by large electric charges: axis X is positive and axis Y is negative.

Experienced laboratory worker marked n points with integer coordinates (xi, yi) on the plane and stopped the time. Sasha should use "atomic tweezers" to place elementary particles in these points. He has an unlimited number of electrons (negatively charged elementary particles) and protons (positively charged elementary particles). He can put either an electron or a proton at each marked point. As soon as all marked points are filled with particles, laboratory worker will turn on the time again and the particles will come in motion and after some time they will stabilize in equilibrium. The objective of the laboratory work is to arrange the particles in such a way, that the diameter of the resulting state (the maximum distance between the pairs of points of the set) is as small as possible.

Since Sasha is a programmer, he naively thinks that all the particles will simply "fall" into their projections on the corresponding axes: electrons will fall on axis X, while protons will fall on axis Y. As we are programmers too, we will consider the same model as Sasha. That is, a particle gets from point (x, y) to point (x, 0) if it is an electron and to point (0, y) if it is a proton.

As the laboratory has high background radiation and Sasha takes care of his laptop, he did not take it with him, and now he can't write a program that computes the minimum possible diameter of the resulting set. Therefore, you will have to do it for him.

Print a square of the minimum possible diameter of the set.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of points marked on the plane.

Each of the next n lines contains two integers xi and yi ( - 108 ≤ xi, yi ≤ 108) — the coordinates of the i-th point. It is guaranteed that no two points coincide.

Output

Print a single integer — the square of the minimum possible diameter of the set.

Examples

Input

3
1 10
1 20
1 30


Output

0


Input

2
1 10
10 1


Output

2

Note

In the first sample Sasha puts electrons at all points, all particles eventually fall at a single point (1, 0).

In the second sample Sasha puts an electron at point (1, 10), and a proton at point (10, 1). The result is a set of two points (1, 0) and (0, 1), which has a diameter of <image>.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            CElectricCharges solver = new CElectricCharges();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class CElectricCharges {
        Point[] pts;
        int[] preMin;
        int[] preMax;
        int[] postMin;
        int[] postMax;
        long inf = (long) 1e9;
        int n;

        public void solve(int testNumber, FastInput in, FastOutput out) {
            n = in.readInt();
            Point[] pts = new Point[n];
            for (int i = 0; i < n; i++) {
                pts[i] = new Point(in.readInt(), in.readInt());
            }

            Arrays.sort(pts, (a, b) -> Integer.compare(a.y, b.y));
            this.pts = pts;
            preMax = new int[n];
            preMin = new int[n];
            postMax = new int[n];
            postMin = new int[n];
            for (int i = 0; i < n; i++) {
                preMin[i] = preMax[i] = pts[i].x;
                if (i > 0) {
                    preMin[i] = Math.min(preMin[i - 1], preMin[i]);
                    preMax[i] = Math.max(preMax[i - 1], preMax[i]);
                }
            }
            for (int i = n - 1; i >= 0; i--) {
                postMax[i] = postMin[i] = pts[i].x;
                if (i + 1 < n) {
                    postMin[i] = Math.min(postMin[i + 1], postMin[i]);
                    postMax[i] = Math.max(postMax[i + 1], postMax[i]);
                }
            }

            LongBinarySearch lbs = new LongBinarySearch() {

                public boolean check(long mid) {
                    long ans = Math.min(pow2(preMax[n - 1] - preMin[n - 1]),
                            pow2(pts[n - 1].y - pts[0].y));
                    for (int i = 0, j = 0; i < n && pts[i].y <= 0; i++) {
                        j = Math.max(i, j);
                        while (j + 1 < n && Math.abs(pts[j + 1].y) <= Math.abs(pts[i].y) && pow2(pts[j + 1].y - pts[i].y) <= mid) {
                            j++;
                        }
                        while (j > i && Math.abs(pts[j].y) > Math.abs(pts[i].y)) {
                            j--;
                        }
                        ans = Math.min(ans, interval(i, j));
                    }
                    for (int i = n - 1, j = n - 1; i >= 0 && pts[i].y >= 0; i--) {
                        j = Math.min(i, j);
                        while (j - 1 >= 0 && Math.abs(pts[j - 1].y) <= Math.abs(pts[i].y) && pow2(pts[i].y - pts[j - 1].y) <= mid) {
                            j--;
                        }
                        while (j < i && Math.abs(pts[j].y) > Math.abs(pts[i].y)) {
                            j++;
                        }
                        ans = Math.min(ans, interval(j, i));
                    }
                    return ans <= mid;
                }
            };


            lbs.check(10);
            long ans = lbs.binarySearch(0, (long) 1e18);
            out.println(ans);
        }

        public long interval(int l, int r) {
            long dy = pts[r].y - pts[l].y;
            long lx = inf;
            long rx = -inf;

            if (l > 0) {
                lx = Math.min(lx, preMin[l - 1]);
                rx = Math.max(rx, preMax[l - 1]);
            }
            if (r + 1 < n) {
                lx = Math.min(lx, postMin[r + 1]);
                rx = Math.max(rx, postMax[r + 1]);
            }
            long ans = pow2(dy);
            if (lx <= rx) {

                long dx = rx - lx;
                ans = Math.max(ans, pow2(dx));
                long h = Math.max(Math.abs(lx), Math.abs(rx));
                long v = Math.max(Math.abs(pts[r].y), Math.abs(pts[l].y));
                ans = Math.max(ans, dist2(h, v));
            }
            return ans;
        }

        public long pow2(long x) {
            return x * x;
        }

        public long dist2(long x, long y) {
            return pow2(x) + pow2(y);
        }

    }

    static class FastInput {
        private final InputStream is;
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

    }

    static abstract class LongBinarySearch {
        public abstract boolean check(long mid);

        public long binarySearch(long l, long r) {
            return binarySearch(l, r, false);
        }

        public long binarySearch(long l, long r, boolean lastFalse) {
            if (l > r) {
                throw new IllegalArgumentException();
            }
            while (l < r) {
                long mid = DigitUtils.floorAverage(l, r);
                if (check(mid)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (lastFalse) {
                if (check(l)) {
                    l--;
                }
            }
            return l;
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static long floorAverage(long x, long y) {
            return (x & y) + ((x ^ y) >> 1);
        }

    }

    static class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 1 << 13;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
                os.append(cache);
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}

