Dany jest ciąg (A_1, A_2, \ldots, A_N) długości (N). Napisz program wykonujący następujące zapytania:

• x1 y1 x2 y2: dla wszystkich par ((i, j)) takich, że (x1 \le i \le y1), (x2 \le j \le y2) oraz (i \le j), wypisz maksymalną wartość sumy (A_i + \ldots + A_j). ((1 \le x1 \le x2 \le N), (1 \le y1 \le y2 \le N), (x1 \le y1), (x2 \le y2))

Wejście

Pierwszy wiersz zawiera liczbę całkowitą (N) ((1 \le N \le 100\,000)), długość ciągu.

Drugi wiersz zawiera (A_1, A_2, \ldots, A_N) ((-100\,000 \le A_i \le 100\,000)).

Trzeci wiersz zawiera liczbę całkowitą (M) ((1 \le M \le 100\,000)), liczbę zapytań.

Kolejne (M) wierszy zawiera po jednym zapytaniu: (x1, y1, x2, y2).

Wyjście

Dla każdego zapytania wypisz odpowiedź w osobnym wierszu.

Przykład

Wejście 1

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

Wyjście 1

2
3

Wejście 2

1
1
1
1 1 1 1

Wyjście 2

1