On donne une séquence $A_1, A_2, \ldots, A_N$ de longueur $N$. Écrire un programme qui exécute la requête suivante :

• x1 y1 x2 y2 : pour tous les $(i, j)$ tels que $x1 \le i \le y1$, $x2 \le j \le y2$, $i \le j$, afficher la valeur maximale de $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$)

Entrée

La première ligne contient un entier $N$ ($1 \le N \le 100{,}000$), la taille de la séquence.

La deuxième ligne contient $A_1, A_2, \ldots, A_N$ ($-100{,}000 \le A_i \le 100{,}000$).

La troisième ligne contient un entier $M$ ($1 \le M \le 100{,}000$), le nombre de requêtes.

Les $M$ lignes suivantes contiennent chacune une requête $x1, y1, x2, y2$.

Sortie

Pour chaque requête, afficher la réponse sur une ligne séparée.

Exemples

Entrée 1

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

Sortie 1

2
3

Entrée 2

1
1
1
1 1 1 1

Sortie 2

1