长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$ 给定。请编写一个程序执行以下查询：

• x1 y1 x2 y2：对于所有满足 $x1 \le i \le y1$, $x2 \le j \le y2$, $i \le j$ 的 $(i, j)$，输出 $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$）

输入格式

第一行包含一个整数 $N$，表示序列的长度（$1 \le N \le 100{,}000$）。

第二行包含 $A_1, A_2, \ldots, A_N$（$-100{,}000 \le A_i \le 100{,}000$）。

第三行包含一个整数 $M$，表示查询的个数（$1 \le M \le 100{,}000$）。

接下来 $M$ 行，每行包含一个查询 $x1, y1, x2, y2$。

输出格式

对于每个查询，输出一行答案。

样例

样例输入 1

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

样例输出 1

2
3

样例输入 2

1
1
1
1 1 1 1

样例输出 2

1