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>
template <class T>
class _Fenwick {
 private:
  std::vector<T> sum;
  int _size;

 public:
  _Fenwick() { _size = 0; }
  void reset(int n) {
    _size = n;
    sum.clear();
    sum.resize(n + 1);
  }
  void add(int x, T y) {
    while (x <= _size) {
      sum[x] += y;
      x += x & -x;
    }
  }
  T query(int x, T y) {
    T ans = y;
    while (x) {
      ans += sum[x];
      x -= x & -x;
    };
    return ans;
  }
  void build(T *a, int n) {
    reset(n);
    for (int i = 1; i <= n; ++i) add(i, a[i]);
  }
};
template <typename T>
void read(T &x);
template <typename T>
void read(T &x, T &y);
template <typename T>
void read(T &x, T &y, T &z);
template <typename T>
void write(T x);
template <typename T>
void writeC(T x);
template <typename T>
void writeN(T x);
template <typename T>
void _binary(T x, int len);
void init_factorial(int *fac, int *ifac, int n, int mod);
long long _qpow(long long a, long long b, long long M);
long long _inv(long long x, long long M);
const long long lim = (1ll << 60);
const long long mod = 998244353;
const long long inv2 = (mod + 1) / 2;
long long l, r, ans, tl;
int n, m;
std::vector<std::pair<long long, long long> > A, B, Avrt, Bvrt;
std::pair<long long, long long> C[8000005];
long long cal(long long x) {
  x %= mod;
  return x % mod * (x + 1) % mod * inv2 % mod;
}
long long calc(long long l, long long r) {
  if (l > r) return 0;
  return (cal(r) - cal(l - 1) + mod) % mod;
}
void split(long long l, long long r, long long L, long long R,
           std::vector<std::pair<long long, long long> > &A,
           std::vector<std::pair<long long, long long> > &V,
           long long pre = 0) {
  if (l > R || r < L) return;
  V.push_back(std::make_pair(R - L + 1, pre));
  if (l <= L && R <= r) {
    A.push_back(std::make_pair(R - L + 1, pre));
    return;
  }
  split(l, r, L, (L + R) >> 1, A, V, pre << 1);
  split(l, r, ((L + R) >> 1) + 1, R, A, V, pre << 1 | 1);
}
void work(std::vector<std::pair<long long, long long> > &A,
          std::vector<std::pair<long long, long long> > &B) {
  for (std::pair<long long, long long> x : A)
    for (std::pair<long long, long long> y : B) {
      if (x.first != y.first) continue;
      long long len = x.first;
      long long A1 = x.second, B1 = y.second;
      C[++tl] = std::make_pair((A1 ^ B1) * len, (A1 ^ B1) * len + len - 1);
    }
}
signed main() {
  read(n);
  for (int i = (1); i <= (n); ++i) {
    read(l, r);
    split(l, r, 0, lim - 1, A, Avrt);
  }
  read(m);
  for (int i = (1); i <= (m); ++i) {
    read(l, r);
    split(l, r, 0, lim - 1, B, Bvrt);
  }
  work(A, Bvrt);
  work(B, Avrt);
  std::sort(C + 1, C + tl + 1);
  long long rpre = -1;
  for (int i = 1; i <= tl; ++i) {
    l = C[i].first, r = C[i].second;
    ans = (ans + calc(std::max(l, rpre + 1), r)) % mod;
    rpre = std::max(rpre, r);
  }
  printf("%lld", ans);
  return 0;
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T flag = 1;
  while (c < '0' || c > '9') {
    if (c == '-') flag = -flag;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= flag;
}
template <typename T>
void read(T &x, T &y) {
  read(x);
  read(y);
}
template <typename T>
void read(T &x, T &y, T &z) {
  read(x);
  read(y);
  read(z);
}
template <typename T>
void writeC(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) writeC(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void write(T x) {
  writeC(x);
  putchar(' ');
}
template <typename T>
void writeN(T x) {
  writeC(x);
  puts("");
}
template <typename T>
void _binary(T x, int len) {
  for (int i = len - 1; i >= 0; --i) writeC((x >> i) & 1);
}
long long _inv(long long x, long long M) {
  assert(x != 0);
  return x == 1 ? 1 : (M - M / x) * _inv(M % x, M) % M;
}
long long _qpow(long long a, long long b, long long M) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % M;
    a = a * a % M;
    b >>= 1;
  }
  return res;
}
void init_factorial(int *fac, int *ifac, int n, int mod) {
  fac[0] = ifac[0] = ifac[1] = 1;
  for (int i = 1; i <= n; ++i) fac[i] = (long long)fac[i - 1] * i % mod;
  for (int i = 2; i <= n; ++i)
    ifac[i] = (long long)(mod - mod / i) * ifac[mod % i] % mod;
  for (int i = 2; i <= n; ++i) ifac[i] = (long long)ifac[i - 1] * ifac[i] % mod;
}
