You are given two sets of integers: A and B. You need to output the sum of elements in the set C = \\{x | x = a ⊕ b, a ∈ A, b ∈ B\} modulo 998244353, where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Each number should be counted only once.

For example, if A = \{2, 3\} and B = \{2, 3\} you should count integer 1 only once, despite the fact that you can get it as 3 ⊕ 2 and as 2 ⊕ 3. So the answer for this case is equal to 1 + 0 = 1.

Let's call a segment [l; r] a set of integers \\{l, l+1, ..., r\}.

The set A is given as a union of n_A segments, the set B is given as a union of n_B segments.

Input

The first line contains a single integer n_A (1 ≤ n_A ≤ 100).

The i-th of the next n_A lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 10^{18}), describing a segment of values of set A.

The next line contains a single integer n_B (1 ≤ n_B ≤ 100).

The i-th of the next n_B lines contains two integers l_j and r_j (1 ≤ l_j ≤ r_j ≤ 10^{18}), describing a segment of values of set B.

Note that segments in both sets may intersect.

Output

Print one integer — the sum of all elements in set C = \\{x | x = a ⊕ b, a ∈ A, b ∈ B\} modulo 998244353.

Examples

Input


2
3 5
5 8
3
1 2
1 9
2 9


Output


112


Input


1
1 9
2
2 4
2 10


Output


120

Note

In the second example, we can discover that the set C = \{0,1,...,15\}, which means that all numbers between 0 and 15 can be represented as a ⊕ b.
#include <bits/stdc++.h>
using namespace std;
using vint = vector<long long>;
using pint = pair<long long, long long>;
using vpint = vector<pint>;
template <typename A, typename B>
inline void chmin(A &a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b) {
  if (a < b) a = b;
}
template <class A, class B>
ostream &operator<<(ostream &ost, const pair<A, B> &p) {
  ost << "{" << p.first << "," << p.second << "}";
  return ost;
}
template <class T>
ostream &operator<<(ostream &ost, const vector<T> &v) {
  ost << "{";
  for (long long i = 0; i < v.size(); i++) {
    if (i) ost << ",";
    ost << v[i];
  }
  ost << "}";
  return ost;
}
template <uint32_t mod>
struct ModInt {
  uint32_t a;
  ModInt &s(uint32_t vv) {
    a = vv < mod ? vv : vv - mod;
    return *this;
  }
  ModInt(int64_t x = 0) { s(x % mod + mod); }
  ModInt &operator+=(const ModInt &x) { return s(a + x.a); }
  ModInt &operator-=(const ModInt &x) { return s(a + mod - x.a); }
  ModInt &operator*=(const ModInt &x) {
    a = uint64_t(a) * x.a % mod;
    return *this;
  }
  ModInt &operator/=(const ModInt &x) {
    *this *= x.inv();
    return *this;
  }
  ModInt operator+(const ModInt &x) const { return ModInt(*this) += x; }
  ModInt operator-(const ModInt &x) const { return ModInt(*this) -= x; }
  ModInt operator*(const ModInt &x) const { return ModInt(*this) *= x; }
  ModInt operator/(const ModInt &x) const { return ModInt(*this) /= x; }
  bool operator==(const ModInt &x) const { return a == x.a; }
  bool operator!=(const ModInt &x) const { return a != x.a; }
  bool operator<(const ModInt &x) const { return a < x.a; }
  ModInt operator-() const { return ModInt() - *this; }
  ModInt pow(int64_t n) const {
    ModInt res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  ModInt inv() const { return pow(mod - 2); }
};
template <uint32_t mod>
istream &operator>>(istream &in, const ModInt<mod> &a) {
  return (in >> a.a);
}
template <uint32_t mod>
ostream &operator<<(ostream &out, const ModInt<mod> &a) {
  return (out << a.a);
}
using mint = ModInt<998244353>;
vpint in() {
  long long n;
  scanf("%lld", &n);
  vpint v;
  for (long long i = 0; i < (n); i++) {
    long long l, r;
    scanf("%lld%lld", &l, &r);
    r++;
    v.emplace_back(l, r);
  }
  sort((v).begin(), (v).end());
  vpint vv;
  for (auto &p : v) {
    if (vv.size() == 0 || vv.back().second < p.first) {
      vv.push_back(p);
      continue;
    }
    chmax(vv.back().second, p.second);
  }
  return vv;
}
void dfs(long long l, long long r, long long b, vpint &v, vector<vint> &rX,
         vector<vint> &vX) {
  bool isR = false, isV = false;
  for (auto &p : v) {
    if (r <= p.first || p.second <= l) continue;
    if (p.first <= l && r <= p.second) isR = true;
    isV = true;
  }
  if (isR) {
    rX[b].push_back(l);
  }
  if (isV) {
    vX[b].push_back(l);
  }
  if (isR) return;
  if (!isV) return;
  dfs(l, (l + r) / 2, b - 1, v, rX, vX);
  dfs((l + r) / 2, r, b - 1, v, rX, vX);
}
signed main() {
  vpint A = in();
  vpint B = in();
  vector<vint> rA(61), vA(61);
  vector<vint> rB(61), vB(61);
  dfs(0, 1ll << 60, 60, A, rA, vA);
  dfs(0, 1ll << 60, 60, B, rB, vB);
  vpint lis;
  for (long long i = 0; i < (60 + 1); i++) {
    for (auto a : rA[i])
      for (auto b : vB[i]) lis.emplace_back(a ^ b, (a ^ b) + (1ll << i));
    for (auto a : vA[i])
      for (auto b : rB[i]) lis.emplace_back(a ^ b, (a ^ b) + (1ll << i));
  }
  sort((lis).begin(), (lis).end());
  vpint nex;
  for (auto &p : lis) {
    if (nex.size() == 0 || nex.back().second < p.first) {
      nex.push_back(p);
    } else {
      chmax(nex.back().second, p.second);
    }
  }
  lis = nex;
  mint ans = 0;
  for (auto &p : lis) {
    mint n(p.second - p.first);
    ans += n * p.first * 2;
    ans += n * (n - 1);
  }
  ans /= 2;
  cout << ans << endl;
  return 0;
}
