区间最大子段和

题目描述

Y 同学继续深入研究整数序列的性质。他拥有一个长度为 $N$ 的整数序列 $A = \{a_1, a_2, \ldots, a_N\}$。

这一次，Y 同学遇到的问题更为复杂。他需要处理 $M$ 次查询，每次查询会给出四个整数 $x_1, y_1, x_2, y_2$。他需要在序列 $A$ 中选择一个子段 $[i, j]$（即 $A$ 中下标从 $i$ 到 $j$ 的连续元素），满足以下所有条件：

1. 子段的起始位置 $i$ 必须在区间 $[x_1, y_1]$ 内，即 $x_1 \le i \le y_1$。
2. 子段的结束位置 $j$ 必须在区间 $[x_2, y_2]$ 内，即 $x_2 \le j \le y_2$。
3. 显然，子段的起始位置不能晚于结束位置，即 $i \le j$。

对于每一次查询，Y 同学希望找到一个满足上述条件的子段，使得该子段的元素之和 $\sum_{k=i}^j a_k$ 最大。请你编写程序帮助他计算这个最大值。

输入格式

输入包含多组测试数据。 第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含一个整数 $N$，表示序列的长度。 第二行包含 $N$ 个整数 $a_1, a_2, \ldots, a_N$，表示序列 $A$ 的元素。 第三行包含一个整数 $M$，表示查询的次数。 接下来 $M$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，描述一次查询。保证 $x_1 \le x_2$ 且 $y_1 \le y_2$。

输出格式

对于每组测试数据中的每一次查询，输出一行一个整数，表示满足条件的最大子段和。

样例

样例输入 #1

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

样例输出 #1

2
3
1

数据范围与约定

对于 $100\%$ 的数据，满足：

• $T \le 5$
• $1 \le N \le 10000$
• $1 \le M \le 10000$
• $|a_i| \le 10000$
• $1 \le x_1 \le y_1 \le N$
• $1 \le x_2 \le y_2 \le N$
• $x_1 \le x_2$ 且 $y_1 \le y_2$