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;
template <typename T>
void maxtt(T& t1, T t2) {
  t1 = max(t1, t2);
}
template <typename T>
void mintt(T& t1, T t2) {
  t1 = min(t1, t2);
}
bool debug = 0;
int n, m, k;
string direc = "URDL";
const long long MOD2 = (long long)998244353 * (long long)998244353;
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int& x, int y, int mod = 998244353) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
  assert(x >= 0 && x < mod);
}
void et(int x = -1) {
  printf("%d\n", x);
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 998244353) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) { return y ? gcd1(y, x % y) : x; }
struct mb {
  vector<long long> vp[61];
  int len[61];
  void add(long long l, long long r, long long L, long long R, long long pre,
           int d, bool fg) {
    if (R <= l || r <= L) return;
    if (L <= l && r <= R) {
      vp[d].push_back(pre << (60 - d));
      return;
    }
    if (fg) vp[d].push_back(pre << (60 - d));
    long long mid = (l + r) >> 1;
    add(l, mid, L, R, pre << 1, d + 1, fg);
    add(mid, r, L, R, pre << 1 | 1, d + 1, fg);
  }
  void init() {
    for (int(j) = 0; (j) < (int)(61); (j)++) {
      sort(vp[j].begin(), vp[j].end());
      len[j] = unique(vp[j].begin(), vp[j].end()) - vp[j].begin();
    }
  }
  void clr() {
    for (int(j) = 0; (j) < (int)(61); (j)++) {
      vp[j].clear();
      len[j] = 0;
    }
  }
} T[2];
pair<long long, long long> q[2][111];
long long ans;
vector<pair<long long, long long> > vp;
void cal() {
  for (int(i) = 0; (i) < (int)(2); (i)++) T[i].clr();
  for (int(i) = 1; (i) <= (int)(n); (i)++)
    T[0].add(0, 1LL << 60, q[0][i].first, q[0][i].second + 1, 0, 0, false);
  for (int(i) = 1; (i) <= (int)(m); (i)++)
    T[1].add(0, 1LL << 60, q[1][i].first, q[1][i].second + 1, 0, 0, true);
  for (int(i) = 0; (i) < (int)(2); (i)++) T[i].init();
  for (int(j) = 0; (j) < (int)(61); (j)++) {
    for (int(x) = 0; (x) < (int)(T[0].len[j]); (x)++) {
      for (int(y) = 0; (y) < (int)(T[1].len[j]); (y)++) {
        long long p = T[0].vp[j][x];
        long long q = T[1].vp[j][y];
        long long z = (p ^ q);
        vp.push_back({z, z + (1LL << (60 - j)) - 1});
      }
    }
  }
}
void ap(pair<long long, long long> pp) {
  long long l = pp.first, r = pp.second;
  ans += ((l + r) % 998244353 * ((r - l + 1) % 998244353)) % 998244353;
  ans %= 998244353;
}
void fmain(int tid) {
  scanf("%d", &n);
  for (int(i) = 1; (i) <= (int)(n); (i)++) {
    scanf("%lld%lld", &q[0][i].first, &q[0][i].second);
  }
  scanf("%d", &m);
  for (int(i) = 1; (i) <= (int)(m); (i)++) {
    scanf("%lld%lld", &q[1][i].first, &q[1][i].second);
  }
  cal();
  swap(n, m);
  swap(q[0], q[1]);
  cal();
  sort(vp.begin(), vp.end());
  vector<pair<long long, long long> > sta;
  for (auto& p : vp) {
    if (sta.empty())
      sta.push_back(p);
    else {
      if (sta.back().second + 1 >= p.first) {
        maxtt(sta[sta.size() - 1].second, p.second);
      } else {
        ap(sta.back());
        sta.pop_back();
        sta.push_back(p);
      }
    }
  }
  ap(sta.back());
  ans = ans * fastPow(2, 998244353 - 2) % 998244353;
  printf("%lld\n", ans);
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
