Background

Solution write-up: https://blog.csdn.net/kkkksc03/article/details/84928342.

Xiaoben knows that Minecraft coordinates have three parameters: $X$, $Y$, and $Z$. But in Xiaoben’s eyes, there is a fourth parameter $Q$, which represents how much he likes this location. For example, some places are Xiaoben’s home, so $Q$ will be large; some places are dangerous mines, so $Q$ will be small.

Problem Description

There are $N$ coordinates. For the $i$-th coordinate with parameters $\{X _ i, Y _ i, Z _ i, Q _ i\}$ and the $j$-th coordinate with parameters $\{X _ j, Y _ j, Z _ j, Q _ j\}$, if $X _ i - X _ j = Y _ i - Y _ j = Z _ i - Z _ j = Q _ i - Q _ j$, then these coordinates are called beautiful coordinates.

Given $N$ coordinates, Xiaoben wants to know the minimum value of $j - i$ and the maximum value of $i + j$ among all beautiful coordinate pairs. Can you help him?

Input Format

The input has $n + 1$ lines. The first line contains an integer $n$. Then follow $n$ lines, each containing four integers $X$, $Y$, $Z$, and $Q$.

Output Format

Output one line containing the minimum value of $j - i$ and the maximum value of $i + j$, separated by a space. The testdata guarantees that a solution exists.

7
1 2 3 4
2 3 4 5
1 4 3 3
5 2 3 5
2 4 5 6
1 4 3 3
2 5 4 4

1 13

10
1 4 3 2
4 4 4 4
2 3 4 5
1 1 1 1
1 2 3 1
3 4 2 1
2 4 5 2
8 9 7 6
0 0 0 0
1 2 3 4

2 14

Hint

Explanation for Sample 1

$(1, 2, 3, 4)$ and $(2, 3, 4, 5)$, or $(1, 4, 3, 3)$ and $(2, 5, 4, 4)$, achieve the minimum value.

For $(1, 4, 3, 3)$ and $(2, 5, 4, 4)$, $6 + 7 = 13$ is the maximum value.

Constraints

For $30\%$ of the data, $n \le 10 ^ 3$.

For $100\%$ of the data, $1 \le n \le 5 \times 10 ^ 5$, and $X$, $Y$, $Z$, $Q$ are all within the int range.

Translated by ChatGPT 5