Cho một dãy số nguyên \(A\) gồm \(N\) phần tử. Hãy tìm ba đoạn con liên tiếp (có ít nhất một phần tử) không giao nhau của dãy số sao cho tổng các phần tử của ba đoạn con này là lớn nhất.

Dữ liệu vào từ thiết bị vào chuẩn:

• Dòng đầu tiên gồm một số nguyên dương \(N\) (\(3 \le N \le 10^5\)) mô tả số phần tử của dãy số;
• Dòng thứ hai gồm \(N\) số nguyên \(A_i\) (\(1 \le i \le N\); \(|A_i| \le 10^9\)) mô tả các phần tử của dãy số.

Kết quả ghi ra thiết bị ra chuẩn:

• Gồm một số nguyên là kết quả của bài toán.

Ví dụ:

Ràng buộc:

• Có 40% số test ứng với 40% số điểm có: \(N \le 10^2\);
• 30% số test khác ứng với 30% số điểm có: \(N \le 10^3\);
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

Example

Sample input 1

07/07/0777

Sample output 1

05/07/0777
11/07/0777

Sample input 2

03/13/1234

Sample output 2

02/13/1234
05/13/1234

Example

Sample input

6
3 2 6
LLR
2 -1 8
RL
4 -2 5
LRRR
5 3 7
LRRLL
1 1 1
L
3 -1 4846549234412827
RLR

Sample output

1 -2
4 1
1 -1
0 2
1 0
2423274617206414 0

Example

Sample input 1

3 3
001

Sample output 1

101

Sample input 2

6 3
101100

Sample output 2

101100

.