Ban đầu có một tập rỗng và \(n\) điểm được thêm vào tập đó. Hãy tính khoảng cách Manhattan lớn nhất giữa hai điểm sau mỗi lần thêm.

Input

Dòng đầu tiên chứa một số nguyên \(n\): số lượng điểm.

\(n\) dòng tiếp theo mô tả các điểm. Mỗi dòng chứa hai số nguyên \(x\) và \(y\). Bạn có thể giả sử rằng mỗi điểm là phân biệt.

Output

Sau mỗi lần thêm, in ra khoảng cách lớn nhất.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

• \(-10^9 \le x, y \le 10^9\)

Example

5
1 1
3 2
2 4
2 1
4 5

0
3
4
4
7