// \sum gcd^2(a[i],b[j])
// l<=i<=r
// L<=j<=R

#include "noya/head.hpp"
using namespace noya;

const int BLOCK = 300;

using u32 = unsigned;

const int V = 1e5 + 1;
const int sqrtV = 200;
u32 point[V], blo[V / sqrtV + 5];
void add(int x, u32 v) {
  int bel = x / sqrtV;
  blo[bel] += v;
  point[x] += v;
}

u32 query(int x) {
  u32 res = 0;
  int bel = x / sqrtV;
  for (int i = 0; i < bel; i++)
    res += blo[i];
  int start = bel * sqrtV;
  int end = x;
  for (int i = start; i < end; i++)
    res += point[i];
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  vector<u32> phi(N + 1);
  for (int i = 1; i <= N; i++) {
    phi[i] = u32(i) * u32(i);
  }

  for (int i = 1; i <= N; i++) {
    for (int j = i * 2; j <= N; j += i) {
      phi[j] -= phi[i];
    }
  }

  vector<int> A(N);
  for (auto &a : A) {
    cin >> a;
  }
  vector<int> B(N);
  for (auto &b : B) {
    cin >> b;
  }
  vector<int> loc_A(N + 1, -1);
  vector<int> loc_B(N + 1, -1);

  for (int i = 0; i < N; i++) {
    loc_A[A[i]] = i;
    loc_B[B[i]] = i;
  }

  int Q;
  cin >> Q;

  vector<array<int, 3>> queries;
  vector<vector<array<int, 2>>> points(N + 1);
  for (int i = 0; i < Q; i++) {
    int l, r, L, R;
    cin >> l >> r >> L >> R;
    --l;
    --L;
    // query(r, R) + query(l, L) - query(r, L) - query(l, R)
    {
      queries.push_back({i, r, R});
      queries.push_back({i, l, L});

      queries.push_back({~i, r, L});
      queries.push_back({~i, l, R});
    }
    {
      points[r].push_back({i, R});
      points[l].push_back({i, L});

      points[r].push_back({~i, L});
      points[l].push_back({~i, R});
    }
  }

  vector<u32> SA(N + 1);
  vector<u32> SB(N + 1);
  vector<u32> ans(Q);

  for (int d = 1; d < min(N + 1, BLOCK); d++) {
    for (int i = 0; i < N; i++) {
      SA[i + 1] = SA[i] + (A[i] % d == 0);
      SB[i + 1] = SB[i] + (B[i] % d == 0);
    }
    for (auto &[i, a, b] : queries) {
      if (i >= 0) {
        ans[i] += SA[a] * SB[b] * phi[d];
      } else {
        ans[~i] -= SA[a] * SB[b] * phi[d];
      }
    }
  }

  vector<vector<int>> divisor(N + 1);
  for (int d = BLOCK; d <= N; d++) {
    for (int i = d; i <= N; i += d) {
      divisor[i].push_back(d);
    }
  }

  for (int p = 0; p < N; p++) {
    int a = A[p];
    for (int d : divisor[a]) {
      for (int b = d; b <= N; b += d) {
        add(loc_B[b], phi[d]);
      }
    }
    for (auto &[i, q] : points[p + 1]) {
      if (i >= 0) {
        ans[i] += query(q);
      } else {
        ans[~i] -= query(q);
      }
    }
  }

  for (int i = 0; i < Q; i++) {
    cout << ans[i] << "\n";
  }
  return 0;
}

answer.code:5:10: fatal error: noya/head.hpp: No such file or directory
    5 | #include "noya/head.hpp"
      |          ^~~~~~~~~~~~~~~
compilation terminated.