小红的数组

题目分析

题目要求对平面上的$n$个点，对于每个点，计算出与它曼哈顿距离最远的点的距离。
曼哈顿距离定义为：
$dist(a_i, a_j) = |x_i - x_j|$$+ |y_i - y_j|$

当数据量较大$(n≤2\times10^5)$时，直接暴力$O(n^2)$显然会超时，因此需要优化。

题目内容

小红拿到一个长度为$n$的数组$a$

第$i$个元素为$(x_i,y_i)$，编号为$i$。

定义两个点的距离为

$dist(a_i,a_j)=|x_i-y_i|+|y_i-y_j|$

现在请你对于任意的$i(1≤i≤n)$，输出距离其最大的点的距离。

输入描述

第一行一个整数$n(2≤n≤2×10^5)$ 表示字数和单行限制总数。

接下来$n$行，每行两个整数

$x_i,y_i(-10^9≤x_i,y_i≤10^9)$,表示第$i$个元素的坐标

输出描述

一个长度为$n$的数组，表示每个点距离其最大的点的距离，每个数之间用空格隔开。

样例1

输入

3
1 2
4 5
2 1

输出

6 6 6