using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("3 5");
WillReturn.Add("3 5 2");
WillReturn.Add("8 1 3");
WillReturn.Add("1 2 2 3");
WillReturn.Add("1 3 1 3");
WillReturn.Add("1 1 1 1");
WillReturn.Add("2 2 2 2");
WillReturn.Add("3 3 1 1");
//2
//1
//11
//6
//10
}
else if (InputPattern == "Input2") {
WillReturn.Add("1 1");
WillReturn.Add("9");
WillReturn.Add("100");
WillReturn.Add("1 1 1 1");
//109
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static void Main()
{
List<string> InputList = GetInputList();
long[] YArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long[] XArr = InputList[2].Split(' ').Select(pX => long.Parse(pX)).ToArray();
long[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();
var DiffYDict = new Dictionary<long, long>();
var DiffXDict = new Dictionary<long, long>();
for (long I = 1; I <= YArr.GetUpperBound(0); I++) {
DiffYDict[I] = Math.Abs(YArr[I] - YArr[I - 1]);
}
for (long I = 1; I <= XArr.GetUpperBound(0); I++) {
DiffXDict[I] = Math.Abs(XArr[I] - XArr[I - 1]);
}
var SegmentTreeYGCD = new SegmentTree(DiffYDict.Count + 1);
var SegmentTreeXGCD = new SegmentTree(DiffXDict.Count + 1);
foreach (var EachPair in DiffYDict.OrderBy(pX => pX.Key)) {
SegmentTreeYGCD.Update(EachPair.Key, EachPair.Value);
}
foreach (var EachPair in DiffXDict.OrderBy(pX => pX.Key)) {
SegmentTreeXGCD.Update(EachPair.Key, EachPair.Value);
}
var sb = new System.Text.StringBuilder();
foreach (string EachStr in InputList.Skip(3)) {
SplitAct(EachStr);
long H1 = wkArr[0] - 1;
long H2 = wkArr[1] - 1;
long W1 = wkArr[2] - 1;
long W2 = wkArr[3] - 1;
long GCD1 = YArr[H1] + XArr[W1];
long GCD2 = 0;
if (H1 + 1 <= H2) {
GCD2 = SegmentTreeYGCD.Query(H1 + 1, H2, 0);
}
long GCD3 = 0;
if (W1 + 1 <= W2) {
GCD3 = SegmentTreeXGCD.Query(W1 + 1, W2, 0);
}
long Answer = GCD1;
Answer = DeriveGCD(Answer, GCD2);
Answer = DeriveGCD(Answer, GCD3);
sb.Append(Answer);
sb.AppendLine();
}
Console.Write(sb.ToString());
}
// ユークリッドの互除法で2数の最大公約数を求める
static long DeriveGCD(long pVal1, long pVal2)
{
if (pVal1 == 0) return pVal2;
if (pVal2 == 0) return pVal1;
long WarareruKazu = pVal2;
long WaruKazu = pVal1;
while (true) {
long Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
}
#region SegmentTree
// SegmentTreeクラス (GCD and 1点更新)
internal class SegmentTree
{
private long[] mTreeNodeArr;
private long UB; // 木のノードの配列のUB
private long mLeafCnt; // 葉ノードの数
// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列
private struct RangeInfoDef
{
internal long StaInd;
internal long EndInd;
}
private RangeInfoDef[] mRangeInfo;
// コンストラクタ
internal SegmentTree(long pLeafCnt)
{
// 簡単のため、葉ノード数を2のべき乗に
long ArrLength = 0;
for (long I = 1; I < long.MaxValue; I *= 2) {
ArrLength += I;
mLeafCnt = I;
if (pLeafCnt < mLeafCnt) break;
}
// すべての値を0に
UB = ArrLength - 1;
mTreeNodeArr = new long[UB + 1];
for (int I = 0; I <= UB; I++) {
mTreeNodeArr[I] = 0;
}
// ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成
mRangeInfo = new RangeInfoDef[UB + 1];
for (long I = 0; I <= UB; I++) {
if (I == 0) {
RangeInfoDef WillSet1;
WillSet1.StaInd = 0;
WillSet1.EndInd = mLeafCnt - 1;
mRangeInfo[I] = WillSet1;
continue;
}
long ParentNode = DeriveParentNode(I);
RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode];
RangeInfoDef WillSet2;
long Mid = (ParentRangeInfo.StaInd + ParentRangeInfo.EndInd) / 2;
if (I % 2 == 1) { // 奇数ノードの場合
WillSet2.StaInd = ParentRangeInfo.StaInd;
WillSet2.EndInd = Mid;
}
else { // 偶数ノードの場合
WillSet2.StaInd = Mid + 1;
WillSet2.EndInd = ParentRangeInfo.EndInd;
}
mRangeInfo[I] = WillSet2;
}
}
// 親ノードの添字を取得
private long DeriveParentNode(long pTarget)
{
return (pTarget - 1) / 2;
}
// 子ノードの添字(小さいほう)を取得
private long DeriveChildNode(long pTarget)
{
return pTarget * 2 + 1;
}
// 葉ノードの配列の添字を木の添字に変換して返す
private long DeriveTreeNode(long pLeafArrInd)
{
long BaseInd = UB - mLeafCnt + 1;
return BaseInd + pLeafArrInd;
}
// 葉ノードの配列のK番目の値をNewValに変更
internal void Update(long pK, long pNewVal)
{
long CurrNode = DeriveTreeNode(pK);
mTreeNodeArr[CurrNode] = pNewVal;
// 登りながら更新
while (CurrNode > 0) {
CurrNode = DeriveParentNode(CurrNode);
long ChildNode1 = DeriveChildNode(CurrNode);
long ChildNode2 = ChildNode1 + 1;
mTreeNodeArr[CurrNode] =
DeriveGCD(mTreeNodeArr[ChildNode1], mTreeNodeArr[ChildNode2]);
}
}
// 開始添字と終了添字とカレントノードを引数として、GCDを返す
internal long Query(long pSearchStaInd, long pSearchEndInd, long pCurrNode)
{
long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;
// OverLapしてなければ、0
if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
return 0;
// 完全に含んでいれば、このノードの値
if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd)
return mTreeNodeArr[pCurrNode];
// そうでなければ、2つの子のGCD
long ChildNode1 = DeriveChildNode(pCurrNode);
long ChildNode2 = ChildNode1 + 1;
long ChildVal1 = Query(pSearchStaInd, pSearchEndInd, ChildNode1);
long ChildVal2 = Query(pSearchStaInd, pSearchEndInd, ChildNode2);
return DeriveGCD(ChildVal1, ChildVal2);
}
internal void DebugPrint()
{
for (int I = 0; I <= UB; I++) {
Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]);
}
}
// ユークリッドの互除法で2数の最大公約数を求める
internal long DeriveGCD(long pVal1, long pVal2)
{
if (pVal1 == 0) return pVal2;
if (pVal2 == 0) return pVal1;
long WarareruKazu = pVal2;
long WaruKazu = pVal1;
while (true) {
long Amari = WarareruKazu % WaruKazu;
if (Amari == 0) return WaruKazu;
WarareruKazu = WaruKazu;
WaruKazu = Amari;
}
}
}
#endregion