Lib

import java.io.*;
import java.util.*;

public class Lib {
    FastScanner in;
    PrintWriter out;

    void solve() {

    }

    class MinCostMaxFlowGraph {
        int n;
        ArrayList<Edge>[] g;

        class Edge {
            int from, to;
            long cap, flow, cost;
            Edge rev;

            public Edge(int from, int to, long cap, long flow, long cost) {
                super();
                this.from = from;
                this.to = to;
                this.cap = cap;
                this.flow = flow;
                this.cost = cost;
            }
        }

        class Vertex implements Comparable<Vertex> {
            int v;
            Edge e;
            long d;

            public Vertex(int v) {
                super();
                this.v = v;
            }

            @Override
            public int compareTo(Vertex o) {
                return d < o.d ? -1 : d > o.d ? 1 : v - o.v;
            }

        }

        public MinCostMaxFlowGraph(int n) {
            super();
            this.n = n;
            g = new ArrayList[n];
            for (int i = 0; i < n; i++)
                g[i] = new ArrayList<Edge>();
        }

        public void addEdge(int fr, int to, int cap, long cost) {
            Edge e1 = new Edge(fr, to, cap, 0, cost);
            Edge e2 = new Edge(to, fr, 0, 0, -cost);
            e1.rev = e2;
            e2.rev = e1;
            g[fr].add(e1);
            g[to].add(e2);
        }

        public long[] getMinCostMaxFlow(int source, int target) {
            long[] h = new long[n];
            for (boolean changed = true; changed;) {
                changed = false;
                for (int i = 0; i < n; i++) {
                    for (Edge e : g[i]) {
                        if (e.cap > 0 && h[e.to] > h[e.from] + e.cost) {
                            h[e.to] = h[e.from] + e.cost;
                            changed = true;
                        }
                    }
                }
            }
            Vertex[] vertices = new Vertex[n];
            long[] d = new long[n];
            for (int i = 0; i < vertices.length; i++) {
                vertices[i] = new Vertex(i);
            }
            int flow = 0;
            long cost = 0;
            while (true) {
                dijkstra(source, vertices, d, h);
                if (d[target] == Long.MAX_VALUE) {
                    break;
                }
                long addFlow = Long.MAX_VALUE;
                Vertex v = vertices[target];
                while (v != vertices[source]) {
                    addFlow = Math.min(addFlow, v.e.cap - v.e.flow);
                    v = vertices[v.e.from];
                }
                cost += (d[target] + h[target] - h[source]) * addFlow;
                flow += addFlow;
                v = vertices[target];
                while (v != vertices[source]) {
                    v.e.flow += addFlow;
                    v.e.rev.flow -= addFlow;
                    v = vertices[v.e.from];
                }
                for (int i = 0; i < n; i++) {
                    h[i] += d[i] == Long.MAX_VALUE ? 0 : d[i];
                }
            }
            return new long[] { flow, cost };
        }

        void dijkstra(int source, Vertex[] vertices, long[] d, long[] h) {
            TreeSet<Vertex> ts = new TreeSet<Vertex>();
            Arrays.fill(d, Long.MAX_VALUE);
            for (int i = 0; i < vertices.length; i++) {
                vertices[i].d = Long.MAX_VALUE;
            }
            d[source] = 0;
            vertices[source].d = 0;
            ts.add(vertices[source]);
            while (!ts.isEmpty()) {
                Vertex v = ts.pollFirst();
                for (Edge e : g[v.v]) {
                    if (e.flow >= e.cap) {
                        continue;
                    }
                    if (d[e.to] == Long.MAX_VALUE
                            || d[e.to] > d[e.from] + e.cost + h[e.from]
                                    - h[e.to]) {
                        if (e.cost + h[e.from] - h[e.to] < 0) {
                            throw new AssertionError();
                        }
                        if (ts.contains(vertices[e.to])) {
                            ts.remove(vertices[e.to]);
                        }
                        d[e.to] = d[e.from] + e.cost + h[e.from] - h[e.to];
                        vertices[e.to].d = d[e.to];
                        vertices[e.to].e = e;
                        ts.add(vertices[e.to]);
                    }
                }
            }
        }
    }

    class Edge {
        int fr, to;
        long flow, cap;
        Edge rev;

        Edge(int fr, int to, long cap) {
            this.fr = fr;
            this.to = to;
            this.cap = cap;
        }
    }

    class Flow {
        int n;
        ArrayList<Edge>[] g;

        Flow(int n) {
            this.n = n;
            g = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                g[i] = new ArrayList<>();
            }
            q = new int[n];
            h = new int[n];
            cur = new int[n];
        }

        void addEdge(int fr, int to, long cap) {
            Edge e1 = new Edge(fr, to, cap);
            Edge e2 = new Edge(to, fr, 0);
            e1.rev = e2;
            e2.rev = e1;
            g[fr].add(e1);
            g[to].add(e2);
        }

        int[] h;
        int[] cur;
        int[] q;

        boolean bfs() {
            int qIt = 0, qSz = 0;
            q[qSz++] = 0;
            Arrays.fill(h, -1);
            h[0] = 0;
            while (qIt < qSz) {
                int v = q[qIt++];
                for (Edge e : g[v]) {
                    if (e.flow == e.cap)
                        continue;
                    if (h[e.to] == -1) {
                        h[e.to] = h[e.fr] + 1;
                        q[qSz++] = e.to;
                    }
                }
            }
            return h[n - 1] != -1;
        }

        long dfs(int v, long flow) {
            if (v == n - 1 || flow == 0)
                return flow;
            for (; cur[v] < g[v].size(); cur[v]++) {
                Edge e = g[v].get(cur[v]);
                if (h[e.to] != h[e.fr] + 1 || e.flow == e.cap)
                    continue;
                long add = dfs(e.to, Math.min(flow, e.cap - e.flow));
                if (add == 0)
                    continue;
                e.flow += add;
                e.rev.flow -= add;
                return add;
            }
            return 0;
        }

        long flow() {
            long res = 0;
            while (bfs()) {
                Arrays.fill(cur, 0);
                while (true) {
                    long add = dfs(0, Long.MAX_VALUE);
                    if (add == 0)
                        break;
                    res += add;
                }
            }
            return res;
        }
    }

    void FFT(double[] re, double[] im, boolean invert) {
        int n = re.length;
        if (im.length != n)
            throw new AssertionError("Sizes of arrays differ");
        if (Integer.bitCount(n) != 1)
            throw new AssertionError("N is not power of 2");
        if (n != 1) {
            int m = n / 2;
            double[] re1 = new double[m];
            double[] im1 = new double[m];
            double[] re2 = new double[m];
            double[] im2 = new double[m];
            for (int i = 0; i < n; i += 2) {
                re1[i / 2] = re[i];
                im1[i / 2] = im[i];
                re2[i / 2] = re[i + 1];
                im2[i / 2] = im[i + 1];
            }
            FFT(re1, im1, invert);
            FFT(re2, im2, invert);
            double angle = (invert ? -1 : 1) * Math.PI * 2 / n;
            double epsR = Math.cos(angle);
            double epsI = Math.sin(angle);
            double curR = 1;
            double curI = 0;
            for (int i = 0; i < m; i++) {
                double real = curR * re2[i] - curI * im2[i];
                double imag = curI * re2[i] + curR * im2[i];
                re[i] = re1[i] + real;
                im[i] = im1[i] + imag;
                real = -real;
                imag = -imag;
                re[i + m] = re1[i] + real;
                im[i + m] = im1[i] + imag;
                double nR = curR * epsR - curI * epsI;
                double nI = curR * epsI + curI * epsR;
                curR = nR;
                curI = nI;
                if (invert) {
                    re[i] /= 2.;
                    im[i] /= 2;
                    re[i + m] /= 2;
                    im[i + m] /= 2;
                }
            }
        }
    }

    long[] mul(long[] a, long[] b) {
        int len = Math.max(a.length, b.length) * 2;
        int mLen = 1;
        while (mLen < len)
            mLen *= 2;
        double[] r1 = new double[mLen];
        double[] i1 = new double[mLen];
        for (int i = 0; i < a.length; i++)
            r1[i] = a[i];
        double[] r2 = new double[mLen];
        double[] i2 = new double[mLen];
        for (int i = 0; i < b.length; i++)
            r2[i] = b[i];
        FFT(r1, i1, false);
        FFT(r2, i2, false);
        double[] rNew = new double[mLen];
        double[] iNew = new double[mLen];
        for (int i = 0; i < mLen; i++) {
            rNew[i] = r1[i] * r2[i] - i1[i] * i2[i];
            iNew[i] = r1[i] * i2[i] + r2[i] * i1[i];
        }
        FFT(rNew, iNew, true);
        long[] res = new long[mLen];
        for (int i = 0; i < mLen; i++)
            res[i] = (long) Math.round(rNew[i]);
        return res;
    }

    public static void sort(int[] a, int from, int to) {
        int n = to - from;
        int[] temp = new int[n];
        int[] cnt = new int[1 << 16];
        for (int i = to - 1; i >= from; --i) {
            ++cnt[low(a[i])];
        }
        for (int i = 0; i < cnt.length - 1; ++i) {
            cnt[i + 1] += cnt[i];
        }
        for (int i = to - 1; i >= from; --i) {
            temp[--cnt[low(a[i])]] = a[i];
        }

        Arrays.fill(cnt, 0);
        for (int i = n - 1; i >= 0; --i) {
            ++cnt[high(temp[i])];
        }
        cnt[0] += from;
        for (int i = 0; i < cnt.length - 1; ++i) {
            cnt[i + 1] += cnt[i];
        }
        for (int i = n - 1; i >= 0; --i) {
            a[--cnt[high(temp[i])]] = temp[i];
        }
    }

    private static int high(int a) {
        return (a ^ Integer.MIN_VALUE) >>> 16;
    }

    private static int low(int a) {
        return a & 0xFFFF;
    }

    final static double eps = 1e-9;

    class Point {
        double x, y;

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

        double dist(Point an) {
            double dx = an.x - x;
            double dy = an.y - y;
            return Math.sqrt(dx * dx + dy * dy);
        }
    }

    class Line {
        double A, B, C;
        boolean normed;

        Line(Point p1, Point p2) {
            A = p2.y - p1.y;
            B = p1.x - p2.x;
            C = -A * p1.x - B * p1.y;
        }

        void norm() {
            double z = Math.sqrt(A * A + B * B);
            A /= z;
            B /= z;
            C /= z;
            normed = true;
        }

        double dist(Point p) {
            if (!normed)
                norm();
            return Math.abs(A * p.x + B * p.y + C);
        }

        Point intersec(Line another) {
            double zn = A * another.B - another.A * B;
            if (Math.abs(zn) <= eps)
                return null;
            double x = another.C * B - another.B * C;
            double y = another.A * C - another.C * A;
            return new Point(x / zn, y / zn);
        }
    }

    boolean insideSorted(double x, double xLeft, double xRight) {
        return x >= xLeft - eps && x <= xRight + eps;
    }

    boolean inside(double x, double xLeft, double xRight) {
        return insideSorted(x, Math.min(xLeft, xRight), Math.max(xLeft, xRight));
    }

    class Segment {
        Point p1, p2;
        Line l;

        public Segment(Point p1, Point p2) {
            this.p1 = p1;
            this.p2 = p2;
            l = new Line(p1, p2);
        }

        boolean onSegment(Point p) {
            if (l.dist(p) > eps)
                return false;
            return inside(p.x, p1.x, p2.x) && inside(p.y, p1.y, p2.y);
        }

        boolean isPoint() {
            return p1.dist(p2) <= eps;
        }
    }

    class IntersectionObject {
        boolean isPoint;
        Point point;
        Segment segment;

        IntersectionObject(Point point) {
            isPoint = true;
            this.point = point;
        }

        IntersectionObject(Segment segment) {
            isPoint = false;
            this.segment = segment;
        }
    }

    boolean intersectSorted(double xLeft, double xRight, double yLeft,
            double yRight) {
        return Math.max(xLeft, yLeft) - eps <= Math.min(xRight, yRight);
    }

    boolean intersect(double xLeft, double xRight, double yLeft, double yRight) {
        return intersectSorted(Math.min(xLeft, xRight),
                Math.max(xLeft, xRight), Math.min(yLeft, yRight),
                Math.max(yLeft, yRight));
    }

    IntersectionObject intersect(Segment s1, Segment s2) {
        if (!intersect(s1.p1.x, s1.p2.x, s2.p1.x, s2.p2.x)
                || !intersect(s1.p1.y, s1.p2.y, s2.p1.y, s2.p2.y))
            return null;
        boolean isPoint1 = s1.isPoint();
        boolean isPoint2 = s2.isPoint();
        if (isPoint1 && isPoint2)
            return new IntersectionObject(s1.p1);
        if (isPoint1) {
            if (s2.onSegment(s1.p1))
                return new IntersectionObject(s1.p1);
            return null;
        }
        if (isPoint2) {
            if (s1.onSegment(s2.p1))
                return new IntersectionObject(s2.p1);
            return null;
        }
        Point intersecton = s1.l.intersec(s2.l);
        if (intersecton == null) {
            if (Math.abs(s1.l.dist(s2.p1)) > eps
                    || Math.abs(s2.l.dist(s1.p1)) > eps)
                return null;
            double xLeft1 = Math.min(s1.p1.x, s1.p2.x);
            double xLeft2 = Math.min(s2.p1.x, s2.p2.x);
            double xRight1 = Math.max(s1.p1.x, s1.p2.x);
            double xRight2 = Math.max(s2.p1.x, s2.p2.x);
            double yLeft1 = Math.min(s1.p1.y, s1.p2.y);
            double yLeft2 = Math.min(s2.p1.y, s2.p2.y);
            double yRight1 = Math.max(s1.p1.y, s1.p2.y);
            double yRight2 = Math.max(s2.p1.y, s2.p2.y);
            Point p1 = new Point(Math.max(xLeft1, xLeft2), Math.max(yLeft1,
                    yLeft2));
            Point p2 = new Point(Math.min(xRight1, xRight2), Math.min(yRight1,
                    yRight2));
            if (s1.l.dist(p1) > eps || s1.l.dist(p2) > eps) {
                p1 = new Point(Math.max(xLeft1, xLeft2), Math.min(yRight1,
                        yRight2));
                p2 = new Point(Math.min(xRight1, xRight2), Math.max(yLeft1,
                        yLeft2));
            }
            if (p1.dist(p2) <= eps)
                return new IntersectionObject(p1);
            Segment newSeg = new Segment(p1, p2);
            return new IntersectionObject(newSeg);
        } else {
            if (!s1.onSegment(intersecton) || !s2.onSegment(intersecton))
                return null;
            return new IntersectionObject(intersecton);
        }
    }

    void solve2() {
        Point p1 = new Point(in.nextDouble(), in.nextDouble());
        Point p2 = new Point(in.nextDouble(), in.nextDouble());
        Point p3 = new Point(in.nextDouble(), in.nextDouble());
        Point p4 = new Point(in.nextDouble(), in.nextDouble());
        Segment s1 = new Segment(p1, p2);
        Segment s2 = new Segment(p3, p4);
        IntersectionObject inter = intersect(s1, s2);
        if (inter == null) {
            out.println("Empty");
            return;
        }
        if (inter.isPoint) {
            out.println(inter.point.x + " " + inter.point.y);
            return;
        }
        Point pAns1 = inter.segment.p1;
        Point pAns2 = inter.segment.p2;
        if (pAns2.x < pAns1.x
                || (Math.abs(pAns1.x - pAns2.x) <= eps && pAns2.y < pAns1.y)) {
            Point tmp = pAns1;
            pAns1 = pAns2;
            pAns2 = tmp;
        }
        out.println(pAns1.x + " " + pAns1.y);
        out.println(pAns2.x + " " + pAns2.y);
    }

    void run() {
        try {
            in = new FastScanner(new File("lib.in"));
            out = new PrintWriter(new File("lib.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    public static void main(String[] args) {
        new Lib().runIO();
    }
}