Cho dãy số nguyên gồm \(N\) phần tử. Tìm:

• Dãy con khác rỗng có tổng các phần tử là lớn nhất. (Các phần tử có thể không liên tiếp)
• Dãy con gồm các phần tử liên tiếp 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 là số nguyên dương \(N\) là số lượng phần tử của dãy \((1≤N≤10^5)\)
  • Dòng tiếp theo gồm \(N\) số nguyên trong khoảng \([−10^4,10^4]\)

Output

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

Example

2
3
4 4 2
5
3 3 -2 3 -4 

10 10
9 7