A set is initially empty and $n$ points are added to it. Calculate the maximum Manhattan distance of two points after each addition.

The first line has an integer $n$ : the number of points.

The following $n$ lines describe the points. Each line has two integers $x$ and $y$ . You can assume that each point is distinct.

• $1 \le n \le 2 \cdot 10^5$
• $-10^9 \le x, y \le 10^9$

After each addition, print the maximum distance.