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

Input

• Gồm nhiều test, dòng đầu tiên là số lượng test ~T~ ~(1 ≤ T ≤ 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 ≤ N ≤ 100000)~;
  • Dòng tiếp theo gồm ~N~ số nguyên trong khoảng ~[-10^4, 10^4]~

Giới hạn:

• Subtask #1: ~N ≤ 20~;
• Subtask #2: Không có ràng buộc gì thêm.

Output

• 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.

Sample

Input #1

2
4
1 2 3 4
6
2 -1 2 3 4 -5

Output #1

10 10
11 10

Problem source: Kc97ble - Free Contest