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 ll = long long;
using ull = unsigned long long;
ull na, nb, mod = 998244353ull;
pair<ull, ull> sa[110], sb[110];
unordered_set<ull> aux[67];
vector<ull> covered[67];
ull power(ull b, ull e) {
  if (e == 0) return 1;
  ull rec = power(b * b % mod, e / 2);
  return e % 2 ? rec * b % mod : rec;
}
ull inverse(ull n) { return power(n, mod - 2); }
ull trailing_zeros(ull x) {
  ull res = 0ull;
  while (!(x & (1ull << res))) ++res;
  return res;
}
vector<pair<ull, ull>> disjoint_ranges(ull l, ull r) {
  vector<pair<ull, ull>> res;
  while (l <= r) {
    for (ull log = trailing_zeros(l); log != -1ull; --log) {
      ull len = 1ull << log;
      if (l + len - 1 <= r) {
        res.emplace_back(l, log);
        l += len;
        break;
      }
    }
  }
  return res;
}
void combine_with_aux(ull nx, ull ny, pair<ull, ull> sx[],
                      pair<ull, ull> sy[]) {
  for (ll i = (0); i < (nx); ++i) {
    auto dx = disjoint_ranges(sx[i].first, sx[i].second);
    for (ll log = (0); log < (64ull); ++log) aux[log].clear();
    for (auto [p, log] : dx) aux[log].insert(p);
    for (ll log = (0); log < (64ull - 1ull); ++log) {
      for (auto p : aux[log]) {
        aux[log + 1].insert(p & ~(1ull << log));
      }
    }
    for (ll j = (0); j < (ny); ++j) {
      auto dy = disjoint_ranges(sy[j].first, sy[j].second);
      for (auto [py, log] : dy) {
        for (auto px : aux[log]) {
          ull base = (px ^ py) >> log << log;
          covered[log].push_back(base);
        }
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> na;
  for (ll i = (0); i < (na); ++i) cin >> sa[i].first >> sa[i].second;
  cin >> nb;
  for (ll i = (0); i < (nb); ++i) cin >> sb[i].first >> sb[i].second;
  combine_with_aux(na, nb, sa, sb);
  combine_with_aux(nb, na, sb, sa);
  ull res = 0ull;
  ull inv = inverse(2ull);
  for (ll i = (0); i < (64ull); ++i) {
    sort((covered[i]).begin(), (covered[i]).end());
    covered[i].erase(unique((covered[i]).begin(), (covered[i]).end()),
                     covered[i].end());
  }
  for (ll log = (0); log < (64ull); ++log) {
    ull count = power(2ull, log);
    for (ull base : covered[log]) {
      bool ok = true;
      ull pos = base;
      for (ull level = log; level < 64ull; ++level) {
        if (level > log && binary_search((covered[level]).begin(),
                                         (covered[level]).end(), pos)) {
          ok = false;
          break;
        }
        pos &= ~(1ull << level);
      }
      if (ok) {
        ull a = base % mod;
        ull b = (base % mod + count - 1ull + mod) % mod;
        ull sum = (a + b) % mod * (b - a + 1ull + mod) % mod * inv % mod;
        res = (res + sum) % mod;
      }
    }
  }
  cout << res << endl;
  return 0;
}
