CF1221F.Choose a Square

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.

佩佳最近发现了一个名为“选择正方形”的游戏。在这个游戏中，一个无限大的平面上有 $n$ 个编号为 $1$ 到 $n$ 的点。第 $i$ 个点的坐标为 $(x_i, y_i)$，代价为 $c_i$。

你需要选择一个正方形，满足以下条件：其边与坐标轴平行；其左下角和右上角均位于直线 $y = x$ 上；且所有顶点的坐标均为整数。

你获得的分数等于该正方形所覆盖的所有点的代价之和，减去该正方形边长。注意：边长可以为零。

佩佳请你计算：通过恰好放置一个正方形，所能获得的最大可能分数。

The first line of the input contains one integer $n$ ($1 \le n \le 5 \cdot 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 \le x_i, y_i \le 10^9, -10^6 \le c_i \le 10^6$) — coordinates of the $i$-th point and its cost, respectively.

输入的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）—— 表示场上的点的数量。

接下来的 $n$ 行中，每行包含三个整数 $x_i, y_i, c_i$（$0 \le x_i, y_i \le 10^9$，$-10^6 \le c_i \le 10^6$）—— 分别表示第 $i$ 个点的坐标及其代价。

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 \le x_1, y_1, x_2, y_2 \le 2 \cdot 10^9, x_1 = y_1, x_2 = y_2, x_1 \le 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.

第一行输出佩蒂亚能够获得的最高得分。

第二行输出四个整数 $x_1, y_1, x_2, y_2$（$0 \le x_1, y_1, x_2, y_2 \le 2 \cdot 10^9$，且满足 $x_1 = y_1$，$x_2 = y_2$，$x_1 \le x_2$），以空格分隔——表示佩蒂亚为获得最高得分所需选取的正方形的左下角与右上角坐标。

The field corresponding to the first example:

对应第一个示例的场：