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:
/**
 * @author derrick20
 */
import java.io.*;
import java.util.*;

public class ChooseASquare {
    public static void main(String args[]) throws Exception {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        Point[] pts = new Point[N];
        HashMap<Integer, Integer> compress = new HashMap<>();
        TreeSet<Integer> distinct = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            pts[i] = new Point(sc.nextInt(), sc.nextInt(), sc.nextInt());
            distinct.add(pts[i].min);
            distinct.add(pts[i].max);
        }
        lengths = new int[distinct.size()];
        int temp = 0;
        for (int l : distinct) {
            lengths[temp] = l;
            compress.put(l, temp);
            temp++;
        }

        Arrays.sort(pts);
        for (Point p : pts) {
            p.min = compress.get(p.min);
            p.max = compress.get(p.max);
        }

        long best = (long) -9e18;
        long[] ansPair = new long[2];
        // SegmentTree will act on the indices of the point values.
        SegmentTree st = new SegmentTree(new long[distinct.size()]);

        for (int i = 0; i < pts.length; i++) {
            Point p = pts[i];
            st.updateRange(0, p.min, p.v);
            // We must include EVERYTHING with the same max as us, so update all of those...
            while (i + 1 < pts.length && pts[i + 1].max == p.max) {
                i++;
                Point p2 = pts[i];
                st.updateRange(0, p2.min, p2.v);
            }
            // ... THEN, we can check that value!
            long[] pair = st.query(0, p.max);
            long l = lengths[(int) pair[0]];
            int r = lengths[p.max];
            long value = pair[1] - r; // since the segtree stores val + l, we just need to subtract r!
            if (value > best) {
                best = value;
                ansPair[0] = l;
                ansPair[1] = r;
            }
        }
        if (best > 0) {
            out.println(best);
            out.println(ansPair[0] + " " + ansPair[0] + " " + ansPair[1] + " " + ansPair[1]);
        }
        else {
            int l = (int) 2e9;
            out.println(0);
            out.println(l + " " + l + " " + l + " " + l);
        }
        out.close();
    }

    static int[] lengths;

    static class Point implements Comparable<Point> {
        int min, max, v;
        public Point(int x, int y, int val) {
            min = Math.min(x, y);
            max = Math.max(x, y);
            v = val;
        }
        public int compareTo(Point p2) {
            // Sort by maximum value
            return max - p2.max;
        }
        public String toString() {
            return "(" + min + ", " + max + "): " + v;
        }
    }

    static class SegmentTree {
        int[] lo, hi;
        long[] arr;
        long[] tree, delta;
        long[] ansIdx;
        int N;

        // FIX THESE
        long NEUTRAL = (long) -9e18;
        private long eval(int node) {
            return tree[node] + delta[node];
        }
        private long merge(long leftVal, long rightVal) {
            return Math.max(leftVal, rightVal);
        }
        private void pullUp(int node) {
            long leftVal = eval(2 * node);
            long rightVal = eval(2 * node + 1);
            if (leftVal > rightVal) {
                tree[node] = leftVal;
                ansIdx[node] = ansIdx[2 * node];
            }
            else {
                tree[node] = rightVal;
                ansIdx[node] = ansIdx[2 * node + 1];
            }
        }

        public SegmentTree(long[] arr) {
            N = arr.length;
            this.arr = arr;
            lo = new int[4 * N + 1];
            hi = new int[4 * N + 1];
            tree = new long[4 * N + 1];
            delta = new long[4 * N + 1];
            ansIdx = new long[4 * N + 1];

            buildTree(1, 0, N - 1);
        }

        private void buildTree(int node, int l, int r) {
            if (l == r) {
                tree[node] = arr[l] + lengths[l];
                ansIdx[node] = l;

                lo[node] = l;
                hi[node] = r;
            }
            else {
                lo[node] = l;
                hi[node] = r;
                int mid = (l + r) / 2;
                buildTree(2 * node, l, mid);
                buildTree(2 * node + 1, mid + 1, r);
                pullUp(node);
            }
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < N; i++) {
                sb.append(Arrays.toString(query(i, i)) + " ");
            }
            return sb.toString();
        }

        private void pushDown(int node) {
            delta[2 * node] += delta[node];
            delta[2 * node + 1] += delta[node];
            delta[node] = 0;
        }

        public long[] query(int l, int r) {
            return queryHelper(1, l, r);
        }

        private long[] queryHelper(int node, int l, int r) {
            if (r < lo[node] || hi[node] < l) {
                return new long[]{-1, NEUTRAL};
            }
            else if (l <= lo[node] && hi[node] <= r) {
                return new long[]{ansIdx[node], eval(node)};
            }
            else {
                pushDown(node);
                long[] leftResult = queryHelper(2 * node, l, r);
                long[] rightResult = queryHelper(2 * node + 1, l, r);
                pullUp(node);

                if (leftResult[1] > rightResult[1]) {
                    return leftResult;
                }
                else {
                    return rightResult;
                }
            }
        }

        public void updateRange(int l, int r, int val) {
            updateRangeHelper(1, l, r, val);
        }

        private void updateRangeHelper(int node, int l, int r, int val) {
            if (r < lo[node] || hi[node] < l) {
                return;
            }
            else if (l <= lo[node] && hi[node] <= r) {
                delta[node] += val;
            }
            else {
                pushDown(node);
                updateRangeHelper(2 * node, l, r, val);
                updateRangeHelper(2 * node + 1, l, r, val);
                pullUp(node);
            }
        }
    }

    static class FastScanner {
        public int BS = 1<<16;
        public char NC = (char)0;
        byte[] buf = new byte[BS];
        int bId = 0, size = 0;
        char c = NC;
        double cnt = 1;
        BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            }
            catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar(){
            while(bId==size) {
                try {
                    size = in.read(buf);
                }catch(Exception e) {
                    return NC;
                }
                if(size==-1)return NC;
                bId=0;
            }
            return (char)buf[bId++];
        }

        public int nextInt() {
            return (int)nextLong();
        }

        public int[] nextInts(int N, int dx) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong() + dx;
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt=1;
            boolean neg = false;
            if(c==NC)c=getChar();
            for(;(c<'0' || c>'9'); c = getChar()) {
                if(c=='-')neg=true;
            }
            long res = 0;
            for(; c>='0' && c <='9'; c=getChar()) {
                res = (res<<3)+(res<<1)+c-'0';
                cnt*=10;
            }
            return neg?-res:res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c!='.' ? cur:cur+nextLong()/cnt;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c>32) {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while(c<=32)c=getChar();
            while(c!='\n') {
                res.append(c);
                c=getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if(c>32)return true;
            while(true) {
                c=getChar();
                if(c==NC)return false;
                else if(c>32)return true;
            }
        }
    }
}