Chia kho báu

Trong buổi lễ mừng chiến thắng tại học viện Chiến lược và Sáng tạo, các thí sinh được tham gia vào một trò chơi mang tên chia kho báu. Có \(N\) kho báu được đặt rải rác trên mặt phẳng tọa độ. Kho báu thứ \(i\) nằm tại ô có tọa độ \((x_i, y_i)\) và có giá trị \(w_i\).

BTC cho phép 4 người chơi chia kho báu theo cách đặc biệt: họ được chọn một cặp số \((X, Y)\) với \(1 \le i < N\). Sau đó, mỗi người sẽ nhận các kho báu nằm trong vùng tương ứng:

• Người thứ nhất nhận các kho báu tại ô có \(x_i < X\) và \(y_i < Y\)
• Người thứ hai nhận các kho báu tại ô có \(x_i < X\) và \(y_i > Y\)
• Người thứ ba nhận các kho báu tại ô có \(x_i > X\) và \(y_i < Y\)
• Người thứ tư nhận các kho báu tại ô có \(x_i > X\) và \(y_i > Y\)

Giá trị của mỗi người là tổng các \(w_i\) của những kho báu họ nhận được. Với mỗi cặp \((X, Y)\), họ sẽ tính chênh lệch lớn nhất giữa hai người bất kỳ. Trong trường hợp lý tưởng là họ nhận được cùng một giá trị thưởng, nhưng thực tế luôn phũ phàng và nếu đã không thể đồng đều, thì 4 người trên muốn chọn (X,Y) sao cho chênh lệch lớn nhất là nhỏ nhất có thể.

Yêu cầu: Với mỗi \(X = i + 0.5\) \((1 \le i < N)\), hãy tìm giá trị chênh lệch nhỏ nhất có thể giữa người nhận được nhiều kho báu nhất và người nhận được ít nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\) --- số kho báu \((1 \le N \le 2 \cdot 10^5)\).
• \(N\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x_i\), \(y_i\), \(w_i\) --- tọa độ và giá trị của kho báu thứ \(i\) \((1 \le x_i, y_i \le n, 1 \le w_i \le 10^9)\).

Output

• In ra \(N - 1\) dòng, dòng thứ \(i\) chứa số nguyên duy nhất là chênh lệch nhỏ nhất có thể giữa hai người, khi \(X = i + 0.5\).

Example

5
1 1 2
2 2 1
3 4 5
4 3 3
5 5 4

9
8
2
6

Scoring

• Subtask 1 (11 điểm): \(1 \le N \le 200\)
• Subtask 2 (14 điểm): \(1 \le N \le 5000\)
• Subtask 3 (48 điểm): \(1 \le N \le 10^5\)
• Subtask 4 (27 điểm): Không có ràng buộc bổ sung