Năm hết Tết đến người người nhà nhà ăn chơi, về quê, đi kiếm gấu nên mình không làm khó các bạn nữa. Bài tập cho các bạn như sau:

Cho một dãy số, tìm:

• Dãy con khác rỗng có tổng lớn nhất
• Đoạn con khác rỗng có tổng lớn nhất

Gồm nhiều test, dòng đầu tiên là số lượng test T (1 \leq T \leq 10)

Mỗi bộ test gồm hai dòng:

• Dòng đầu gồm số lượng phần tử của dãy N (1 \leq N \leq 100000)
• Dòng tiếp theo gồm N số nguyên trong khoảng [−10^4, 10^4].

Với mỗi bộ test in ra trên một dòng hai số là hai tổng lớn nhất theo thứ tự yêu cầu.

• Subtask 1 (50% số điểm): N \leq 20
• Subtask 2 (50% số điểm): Không có ràng buộc gì thêm