题目描述

小 \(Z\) 和小 \(X\) 玩一个可爱的游戏，有两个正整数序列 \(A\) 和 \(B\)，每次小 \(Z\) 从 \(A\) 中的一个区间选一个数，小 \(X\) 从 \(B\) 中的一个区间选一个数，把它们相乘。要使这个相乘的结果最大。请你算出每次相乘的结果。

输入格式

第一行两个整数 \(N\) 和 \(M\)，分别是 \(A\) 的长度和 \(B\) 的长度。

接下来一行 \(N\) 个整数，表示 \(A\)。

接下来一行 \(M\) 个整数，表示 \(B\)。

接下来一行一个正整数 \(Q\)。

接下来 \(Q\) 行，每行 \(4\) 个正整数 \(a_l,a_r,b_l,b_r\)。表示小 \(Z\) 能选的区间是 \(a_l \sim a_r\)，小 \(X\) 能选的区间是 \(b_l \sim b_r\)。

输出格式

\(Q\) 行，每行一个整数，表示第 \(Q\) 个询问的结果。

样例 #1

样例输入 #1

4 5
1 9 10 2
5 6 2 4 5
1
1 2 3 4

样例输出 #1

36

提示

\(1 \leq n,m,q \leq 10^5\)

\(1 \leq a_l \leq a_r \leq n\)

\(1 \leq b_l \leq b_r \leq m\)

\(1 \leq a_i,b_i \leq 10^9\)