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;
int64_t getLog(int64_t a) {
  int r = 0;
  while (a > 0) {
    a /= 2;
    ++r;
  }
  return r - 1;
}
const int N = 61;
const int64_t mod = 998244353;
int64_t pw(int64_t a, int64_t b) {
  int64_t r = 1;
  while (b > 0) {
    if (b & 1) {
      r = r * a % mod;
    }
    a = a * a % mod;
    b /= 2;
  }
  return r;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  vector<pair<int64_t, int64_t>> a, b;
  int na, nb;
  cin >> na;
  a.resize(na);
  for (int i = 0; i < na; ++i) {
    cin >> a[i].first >> a[i].second;
  }
  cin >> nb;
  b.resize(nb);
  for (int i = 0; i < nb; ++i) {
    cin >> b[i].first >> b[i].second;
  }
  vector<int64_t> ra[N], rb[N];
  for (auto [l, r] : a) {
    while (true) {
      int64_t nr = l | (l - 1);
      if (nr > r) {
        break;
      }
      ra[getLog(nr - l + 1)].push_back(l);
      l = nr + 1;
    }
    while (true) {
      int64_t nl = r & (r + 1);
      if (nl < l) {
        break;
      }
      ra[getLog(r - nl + 1)].push_back(nl);
      r = nl - 1;
    }
    assert(l == r + 1);
  }
  for (auto [l, r] : b) {
    while (true) {
      int64_t nr = l | (l - 1);
      if (nr > r) {
        break;
      }
      rb[getLog(nr - l + 1)].push_back(l);
      l = nr + 1;
    }
    while (true) {
      int64_t nl = r & (r + 1);
      if (nl < l) {
        break;
      }
      rb[getLog(r - nl + 1)].push_back(nl);
      r = nl - 1;
    }
    assert(l == r + 1);
  }
  vector<int64_t> ea, eb;
  vector<pair<int64_t, int64_t>> ans;
  for (int i = 0; i < 60; ++i) {
    for (int64_t j : ra[i]) {
      ea.push_back(j);
    }
    for (int64_t j : rb[i]) {
      eb.push_back(j);
    }
    for (int64_t& j : ea) {
      j = j & ~((1ll << i) - 1);
    }
    for (int64_t& j : eb) {
      j = j & ~((1ll << i) - 1);
    }
    sort(ea.begin(), ea.end());
    sort(eb.begin(), eb.end());
    ea.erase(unique(ea.begin(), ea.end()), ea.end());
    eb.erase(unique(eb.begin(), eb.end()), eb.end());
    for (int64_t j : ra[i]) {
      for (int64_t k : eb) {
        ans.emplace_back(j ^ k, j ^ k + (1ll << i) - 1);
      }
    }
    for (int64_t j : rb[i]) {
      for (int64_t k : ea) {
        ans.emplace_back(j ^ k, j ^ k + (1ll << i) - 1);
      }
    }
  }
  sort(ans.begin(), ans.end());
  int64_t last = 0;
  int64_t mn2 = pw(2, mod - 2);
  int64_t nans = 0;
  for (const auto& [l, r] : ans) {
    if (last >= r) continue;
    last = max(last + 1, l);
    nans =
        (nans + ((r + last) % mod * ((r - last + 1) % mod) % mod) * mn2 % mod) %
        mod;
    last = r;
  }
  cout << nans << endl;
  return 0;
}
