問題文
长度 W 序列 a_1, a_2, ..., a_W 和长度 H 序列 b_1, b_2, ..., b_H 。
从左起 从上往下数 i 在第 j 个方格中, a_i + b_j 被写入, 考虑正方形W \times H 。 您将收到如下所示的
Q 查询,因此请处理它们。 给出了
- A, B ,所以从左边开始 从上往下第 A 内 当从 B 方格中选择多个方格以使所选部分成为矩形时,输出所选方格值之和的最大值。
请注意网格 1 不选择是不可能的。
制約
- 1 ≦ W, H ≦ 2000
- 1 ≦ Q ≦ 2000
- 1 ≦ A ≦ W
- 1 ≦ B ≦ H
- -100,000 ≦ a_i, b_i ≦ 100,000
入力
输入是按以下格式从标准输入给出的。
W H a_1 a_2 ... a_W b_1 b_2 ... b_H Q A_1 B_1 A_2 B_2 : A_Q B_Q
但是,A_i, B_i 分别是 i 的查询 代表 A, B 。 输出
出力
Q 行。 输出第
i 行中,i 个查询的结果。
入力例1
2 2 0 10 0 -1 4 1 1 1 2 2 1 2 2
出力例1
0 0 10 19
入力例2
3 3 1 10 100 1000 10000 100000 9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
出力例2
1001 11002 111003 2011 22022 222033 3111 33222 333333
入力例3
10 8 2 -4 0 0 -1 4 5 0 -3 0 2 0 0 -3 -5 -5 -4 -4 10 2 6 1 4 1 2 5 7 1 5 7 6 7 4 1 5 3 5 10 7
出力例3
8 8 6 8 8 34 34 8 8 36