SP2916 GSS5 - Can you answer these queries V

给定序列 $a_1,a_2,\cdots,a_n$ 和 $m$ 次询问。 每次询问给定 $x_1,y_1,x_2,y_2$，求左端点在 $[x_1,y_1]$ 内，右端点在 $[x_2,y_2]$ 内的所有子段和的最大值。

第一行一个整数 $T$，表示测试数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行包含 $n+1$ 个整数，其中第一个整数表示 $n$，其余表示 $a_1,a_2,\cdots,a_n$。 第二行包含一个整数 $m$，表示询问个数。 接下来 $m$ 行，每行四个整数 $x_1,y_1,x_2,y_2$。

对于每次询问，输出一行一个整数表示答案。

数据保证 $1\leq T\leq 5$，$1\leq n,m\leq10000$。对于 $1\leq i\leq n$，$\vert a_i\vert\leq10000$。