\(h_1=w_1=1,h_2=w_2=N\) のケースを考えます。以下の値は全て等しいです。

• \(1 \le i,j \le N\) を満たす整数の組 \(i,j\) すべてに対する \(A_i + B_j\) の最大公約数
• \(1 \le i \le N\) を満たす整数 \(i\) に対する \(A_i + B_1\) と \(2 \le j \le N\) を満たす整数 \(j\) に対する \(B_j-B_{j-1}\) の最大公約数
• \(A_1 + B_1\) と \(2 \le i \le N\) を満たす整数 \(i\) すべてに対する \(A_i - A_{i-1}\) と \(2 \le j \le N\) を満たす整数 \(j\) に対する \(B_j-B_{j-1}\) の最大公約数

よって、一般の場合についても \(C_i = A_i - A_{i-1},D_j = B_j - B_{j-1}\) となる整数列 \(C,D\) を区間 \(\gcd\) の取得できる segtree に乗せることによってこの問題を \(\mathrm{O}(N(\log A+\log B)+Q(\log N+\log A + \log B))\) で解くことができます。