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;
vector<pair<long long int, long long int> > A, B, ans;
vector<pair<long long int, int> > a, b;
vector<pair<long long int, long long int> > com(
    vector<pair<long long int, long long int> > v) {
  int i;
  vector<pair<long long int, long long int> > vv;
  sort(v.begin(), v.end());
  long long int p = v[0].first, q = v[0].second;
  for (i = 1; i < v.size(); i++) {
    if (v[i].first > q + 1)
      vv.push_back(make_pair(p, q)), p = v[i].first, q = v[i].second;
    else
      q = max(q, v[i].second);
  }
  vv.push_back(make_pair(p, q));
  return vv;
}
bool comp(pair<long long int, int> a, pair<long long int, int> b) {
  return a.second > b.second;
}
set<pair<long long int, long long int> > S;
int insert(long long int x, long long int y) {
  auto it = S.upper_bound(make_pair(x, 2e18));
  if (it != S.begin()) {
    it--;
    if (it->second >= y) return 0;
    if ((it->second >= x) && (it->first < x)) {
      pair<long long int, long long int> p = *it;
      S.erase(it);
      if (x - 1 >= p.first) S.insert(make_pair(p.first, x - 1));
    }
  }
  it = S.upper_bound(make_pair(y, 2e18));
  if (it != S.begin()) {
    it--;
    if ((it->second > y) && (it->first <= x)) {
      pair<long long int, long long int> p = *it;
      S.erase(it), S.insert(make_pair(y + 1, p.second));
    }
  }
  it = S.lower_bound(make_pair(x, 0));
  while ((it != S.end()) && (it->second <= y)) it = S.erase(it);
  S.insert(make_pair(x, y));
  return 0;
}
int main() {
  int i;
  int n;
  long long int l, r;
  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%I64d %I64d", &l, &r), A.push_back(make_pair(l, r));
  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%I64d %I64d", &l, &r), B.push_back(make_pair(l, r));
  A = com(A), B = com(B);
  int j;
  for (i = 0; i < A.size(); i++) {
    for (j = 60; j >= 0; j--) {
      if ((A[i].first ^ A[i].second) & (1LL << j)) break;
    }
    int p = j;
    for (j = p - 1; j >= 0; j--) {
      if (A[i].second & (1LL << j))
        a.push_back(make_pair(A[i].second & (~((1LL << (j + 1)) - 1)), j));
    }
    a.push_back(make_pair(A[i].second, 0));
    for (j = p - 1; j >= 0; j--) {
      if (!(A[i].first & (1LL << j)))
        a.push_back(
            make_pair((A[i].first ^ (1LL << j)) & (~((1LL << j) - 1)), j));
    }
    a.push_back(make_pair(A[i].first, 0));
  }
  swap(a, b), swap(A, B);
  for (i = 0; i < A.size(); i++) {
    for (j = 60; j >= 0; j--) {
      if ((A[i].first ^ A[i].second) & (1LL << j)) break;
    }
    int p = j;
    for (j = p - 1; j >= 0; j--) {
      if (A[i].second & (1LL << j))
        a.push_back(make_pair(A[i].second & (~((1LL << (j + 1)) - 1)), j));
    }
    a.push_back(make_pair(A[i].second, 0));
    for (j = p - 1; j >= 0; j--) {
      if (!(A[i].first & (1LL << j)))
        a.push_back(
            make_pair((A[i].first ^ (1LL << j)) & (~((1LL << j) - 1)), j));
    }
    a.push_back(make_pair(A[i].first, 0));
  }
  sort(a.begin(), a.end(), comp);
  sort(b.begin(), b.end(), comp);
  for (i = 0; i < a.size(); i++) {
    for (j = 0; j < B.size(); j++) {
      int m = a[i].second;
      long long int x = (a[i].first ^ B[j].first) & (~((1LL << m) - 1));
      long long int y = x + (1LL << m) - 1;
      insert(x, y);
      x = (a[i].first ^ B[j].second) & (~((1LL << m) - 1));
      y = x + (1LL << m) - 1;
      insert(x, y);
      if ((B[j].first >> m) != (B[j].second >> m)) {
        if (!(B[j].first & (1LL << m))) {
          x = (a[i].first ^ B[j].first ^ (1LL << m)) & (~((1LL << m) - 1));
          y = x + (1LL << m) - 1;
          insert(x, y);
        }
        if (B[j].second & (1LL << m)) {
          x = (a[i].first ^ B[j].second ^ (1LL << m)) & (~((1LL << m) - 1));
          y = x + (1LL << m) - 1;
          insert(x, y);
        }
      }
    }
  }
  for (i = 0; i < A.size(); i++) {
    for (j = 0; j < b.size(); j++) {
      int m = b[j].second;
      long long int x = (A[i].first ^ b[j].first) & (~((1LL << m) - 1));
      long long int y = x + (1LL << m) - 1;
      insert(x, y);
      x = (A[i].second ^ b[j].first) & (~((1LL << m) - 1));
      y = x + (1LL << m) - 1;
      insert(x, y);
      if ((A[i].first >> m) != (A[i].second >> m)) {
        if (!(A[i].first & (1LL << m))) {
          x = (A[i].first ^ b[j].first ^ (1LL << m)) & (~((1LL << m) - 1));
          y = x + (1LL << m) - 1;
          insert(x, y);
        }
        if (A[i].second & (1LL << m)) {
          x = (A[i].second ^ b[j].first ^ (1LL << m)) & (~((1LL << m) - 1));
          y = x + (1LL << m) - 1;
          insert(x, y);
        }
      }
    }
  }
  for (auto it = S.begin(); it != S.end(); it++) ans.push_back(*it);
  long long int sum = 0;
  for (i = 0; i < ans.size(); i++) {
    if ((ans[i].second - ans[i].first + 1) & 1) {
      long long int m = (ans[i].second + ans[i].first) / 2;
      sum += (m % 998244353) * ((ans[i].second - ans[i].first + 1) % 998244353),
          sum %= 998244353;
    } else {
      long long int m = (ans[i].second - ans[i].first + 1) / 2;
      sum += (m % 998244353) * ((ans[i].second + ans[i].first) % 998244353),
          sum %= 998244353;
    }
  }
  printf("%I64d\n", sum);
  return 0;
}
