Problem: Petya recently found a game "Choose a Square". In this game, there are n points numbered from 1 to n on an infinite field. The i-th point has coordinates (x_i, y_i) and cost c_i.

You have to choose a square such that its sides are parallel to coordinate axes, the lower left and upper right corners belong to the line y = x, and all corners have integer coordinates.

The score you get is the sum of costs of the points covered by the selected square minus the length of the side of the square. Note that the length of the side can be zero.

Petya asks you to calculate the maximum possible score in the game that can be achieved by placing exactly one square.

Input

The first line of the input contains one integer n (1 ≤ n ≤ 5 ⋅ 10^5) — the number of points on the field.

Each of the following n lines contains three integers x_i, y_i, c_i (0 ≤ x_i, y_i ≤ 10^9, -10^6 ≤ c_i ≤ 10^6) — coordinates of the i-th point and its cost, respectively.

Output

In the first line print the maximum score Petya can achieve.

In the second line print four integers x_1, y_1, x_2, y_2 (0 ≤ x_1, y_1, x_2, y_2 ≤ 2 ⋅ 10^9, x_1 = y_1, x_2 = y_2, x_1 ≤ x_2) separated by spaces — the coordinates of the lower left and upper right corners of the square which Petya has to select in order to achieve the maximum score.

Examples

Input


6
0 0 2
1 0 -5
1 1 3
2 3 4
1 4 -4
3 1 -1


Output


4
1 1 3 3


Input


5
3 3 0
3 3 -3
0 2 -1
3 1 3
0 0 -2


Output


0
1 1 1 1

Note

The field corresponding to the first example: <image>

Solution (in JAVA):

Solution:

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.nio.charset.Charset;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Random;

public class CF1221F {
    public static void main(String[] args) throws Exception {
        boolean local = System.getSecurityManager() == null;
        boolean async = false;

        Charset charset = Charset.forName("ascii");

        FastIO io = local ? new FastIO(new FileInputStream("D:\\DATABASE\\TESTCASE\\Code.in"), System.out, charset) : new FastIO(System.in, System.out, charset);
        Task task = new Task(io, new Debug(local));

        if (async) {
            Thread t = new Thread(null, task, "skypool", 1 << 27);
            t.setPriority(Thread.MAX_PRIORITY);
            t.start();
            t.join();
        } else {
            task.run();
        }

        if (local) {
            io.cache.append("\n\n--memory -- \n" + ((Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20) + "M");
        }

        io.flush();
    }

    public static class Task implements Runnable {
        final FastIO io;
        final Debug debug;
        int inf = (int) 1e8;
        long lInf = (long) 1e18;

        public Task(FastIO io, Debug debug) {
            this.io = io;
            this.debug = debug;
        }

        @Override
        public void run() {
            solve();
        }

        public void solve() {
            int n = io.readInt();
            Point[] pts = new Point[n];

            int[] seq = new int[n + n];
            int seqTail = 0;
            for (int i = 0; i < n; i++) {
                pts[i] = new Point();
                pts[i].x = io.readInt();
                pts[i].y = io.readInt();
                if (pts[i].x > pts[i].y) {
                    int tmp = pts[i].x;
                    pts[i].x = pts[i].y;
                    pts[i].y = tmp;
                }
                pts[i].c = io.readInt();
                seq[seqTail++] = pts[i].x;
                seq[seqTail++] = pts[i].y;
            }

            DiscreteMap dm = new DiscreteMap(seq, 0, seqTail);
            Segment seg = new Segment(dm.minRank(), dm.maxRank());
            for (int i = dm.minRank(); i <= dm.maxRank(); i++) {
                seg.update(i, i, dm.minRank(), dm.maxRank(), 0, dm.iThElement(i));
            }
            Arrays.sort(pts, (a, b) -> a.x - b.x);
            for (Point pt : pts) {
                int h = dm.rankOf(pt.y);
                seg.update(h, h, dm.minRank(), dm.maxRank(), pt.c, 0);
            }


            long ans = 0;
            long actualCost = 2 * (int)1e9;
            long x = 2 * (int)1e9;
            Deque<Point> ptDeque = new ArrayDeque<>(Arrays.asList(pts));
            for (int i = dm.minRank(); i <= dm.maxRank(); i++) {
                int tran = dm.iThElement(i);
                long maxProfit = seg.optimal + tran;
                if (ans < maxProfit) {
                    ans = maxProfit;
                    x = tran;
                    actualCost = seg.actualCost;
                }
                seg.update(i, i, dm.minRank(), dm.maxRank(), 0, lInf);
                while (!ptDeque.isEmpty() && ptDeque.peekFirst().x == tran) {
                    Point head = ptDeque.removeFirst();
                    int h = dm.rankOf(head.y);
                    seg.update(h, h, dm.minRank(), dm.maxRank(), -head.c, 0);
                }
            }

            io.cache.append(ans).append('\n')
                    .append(String.format("%d %d %d %d", x, x
                            , actualCost, actualCost));
        }
    }

    public static class Point {
        int x;
        int y;
        int c;

        @Override
        public String toString() {
            return String.format("%d %d %d", x, y, c);
        }
    }


    public static class DiscreteMap {
        int[] val;
        int f;
        int t;

        public DiscreteMap(int[] val, int f, int t) {
            Randomized.randomizedArray(val, f, t);
            Arrays.sort(val, f, t);
            int wpos = f + 1;
            for (int i = f + 1; i < t; i++) {
                if (val[i] == val[i - 1]) {
                    continue;
                }
                val[wpos++] = val[i];
            }
            this.val = val;
            this.f = f;
            this.t = wpos;
        }

        /**
         * Return 0, 1, so on
         */
        public int rankOf(int x) {
            return Arrays.binarySearch(val, f, t, x) - f;
        }

        public int floorRankOf(int x) {
            int index = Arrays.binarySearch(val, f, t, x);
            if (index >= 0) {
                return index - f;
            }
            index = -(index + 1);
            return index - 1 - f;
        }

        public int ceilRankOf(int x) {
            int index = Arrays.binarySearch(val, f, t, x);
            if (index >= 0) {
                return index - f;
            }
            index = -(index + 1);
            return index - f;
        }

        /**
         * Get the i-th smallest element
         */
        public int iThElement(int i) {
            return val[f + i];
        }

        public int minRank() {
            return 0;
        }

        public int maxRank() {
            return t - f - 1;
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(val, f, t));
        }
    }

    /**
     * Created by dalt on 2018/6/1.
     */
    public static class Randomized {
        static Random random = new Random();

        public static double nextDouble(double min, double max) {
            return random.nextDouble() * (max - min) + min;
        }

        public static void randomizedArray(int[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                int tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static void randomizedArray(long[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                long tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static void randomizedArray(double[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                double tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static void randomizedArray(float[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                float tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static <T> void randomizedArray(T[] data, int from, int to) {
            to--;
            for (int i = from; i <= to; i++) {
                int s = nextInt(i, to);
                T tmp = data[i];
                data[i] = data[s];
                data[s] = tmp;
            }
        }

        public static int nextInt(int l, int r) {
            return random.nextInt(r - l + 1) + l;
        }
    }


    public static class Segment implements Cloneable {
        private Segment left;
        private Segment right;
        long profit;
        long cost;
        long optimal;
        long actualCost;

        public void pushUp() {
            profit = left.profit + right.profit;
            cost = right.cost;
            optimal = Math.max(left.optimal,
                    right.optimal + left.profit);
            if (optimal == left.optimal) {
                actualCost = left.actualCost;
            } else {
                actualCost = right.actualCost;
            }
        }

        public void pushDown() {
        }

        public Segment(int l, int r) {
            if (l < r) {
                int m = (l + r) >> 1;
                left = new Segment(l, m);
                right = new Segment(m + 1, r);
                pushUp();
            } else {
            }
        }

        private boolean covered(int ll, int rr, int l, int r) {
            return ll <= l && rr >= r;
        }

        private boolean noIntersection(int ll, int rr, int l, int r) {
            return ll > r || rr < l;
        }

        public void update(int ll, int rr, int l, int r, long p, long c) {
            if (noIntersection(ll, rr, l, r)) {
                return;
            }
            if (covered(ll, rr, l, r)) {
                profit += p;
                cost += c;
                optimal = profit - cost;
                actualCost = cost;
                return;
            }
            pushDown();
            int m = (l + r) >> 1;
            left.update(ll, rr, l, m, p, c);
            right.update(ll, rr, m + 1, r, p, c);
            pushUp();
        }

        public void query(int ll, int rr, int l, int r) {
            if (noIntersection(ll, rr, l, r)) {
                return;
            }
            if (covered(ll, rr, l, r)) {
                return;
            }
            pushDown();
            int m = (l + r) >> 1;
            left.query(ll, rr, l, m);
            right.query(ll, rr, m + 1, r);
        }
    }


    public static class FastIO {
        public final StringBuilder cache = new StringBuilder(1 << 13);
        private final InputStream is;
        private final OutputStream os;
        private final Charset charset;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastIO(InputStream is, OutputStream os, Charset charset) {
            this.is = is;
            this.os = os;
            this.charset = charset;
        }

        public FastIO(InputStream is, OutputStream os) {
            this(is, os, Charset.forName("ascii"));
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                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;
        }

        public long readLong() {
            int sign = 1;

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

            long 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;
        }

        public double readDouble() {
            boolean sign = true;
            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+';
                next = read();
            }

            long val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                next = read();
            }
            if (next != '.') {
                return sign ? val : -val;
            }
            next = read();
            long radix = 1;
            long point = 0;
            while (next >= '0' && next <= '9') {
                point = point * 10 + next - '0';
                radix = radix * 10;
                next = read();
            }
            double result = val + (double) point / radix;
            return sign ? result : -result;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

        public int readLine(char[] data, int offset) {
            int originalOffset = offset;
            while (next != -1 && next != '\n') {
                data[offset++] = (char) next;
                next = read();
            }
            return offset - originalOffset;
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public int readString(byte[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (byte) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public char readChar() {
            skipBlank();
            char c = (char) next;
            next = read();
            return c;
        }

        public void flush() throws IOException {
            os.write(cache.toString().getBytes(charset));
            os.flush();
            cache.setLength(0);
        }

        public boolean hasMore() {
            skipBlank();
            return next != -1;
        }
    }

    public static class Debug {
        private boolean allowDebug;

        public Debug(boolean allowDebug) {
            this.allowDebug = allowDebug;
        }

        public void assertTrue(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (!flag) {
                fail();
            }
        }

        public void fail() {
            throw new RuntimeException();
        }

        public void assertFalse(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (flag) {
                fail();
            }
        }

        private void outputName(String name) {
            System.out.print(name + " = ");
        }

        public void debug(String name, int x) {
            if (!allowDebug) {
                return;
            }

            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, long x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, double x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, int[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, long[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, double[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, Object x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, Object... x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.deepToString(x));
        }
    }
}