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;
const ll MOD = 998244353;
const ll TI = 499122177;
int getj(ll a, ll b) {
  int j = 0;
  while (!(a & (1ll << j)) && ((1ll << (j + 1)) <= (b - a + 1))) ++j;
  return j;
}
ll sum(ll a, ll b) {
  if (a > b) return 0;
  ll avg = (a + b) % MOD;
  ll len = (b - a + 1) % MOD;
  return ((avg * len) % MOD) * TI % MOD;
}
vector<pair<ll, ll>> process(const vector<pair<ll, ll>>& segs) {
  vector<pair<ll, ll>> res;
  for (auto pr : segs) {
    ll a = pr.first;
    ll b = pr.second;
    while (a <= b) {
      int j = getj(a, b);
      res.push_back({a, a + (1ll << j) - 1});
      a += (1ll << j);
    }
  }
  sort(res.begin(), res.end());
  vector<pair<ll, ll>> act;
  for (auto pr : res) {
    if (!act.empty() && act.back().first == pr.first) act.pop_back();
    if (act.empty() || act.back().second < pr.second) act.push_back(pr);
  }
  return act;
}
void buildRes(const vector<pair<ll, ll>>& as, const vector<pair<ll, ll>>& bs,
              vector<pair<ll, ll>>& res) {
  auto as_d = process(as);
  for (auto p1 : as_d) {
    ll a1 = p1.first;
    ll b1 = p1.second;
    ll l1 = b1 - a1 + 1;
    ll m = ~(l1 - 1);
    int j = getj(p1.first, p1.second);
    for (auto p2 : bs) {
      ll a2 = p2.first;
      ll b2 = p2.second;
      ll l2 = b2 - a2 + 1;
      ll a = (a1 ^ a2) & m;
      ll b = a + l1 - 1;
      res.push_back({a, b});
      a = (a1 ^ b2) & m;
      b = a + l1 - 1;
      res.push_back({a, b});
      if (l2 > l1) {
        a = (a1 ^ (a2 + l1)) & m;
        b = a + l1 - 1;
        res.push_back({a, b});
        a = (a1 ^ (b2 - l1)) & m;
        b = a + l1 - 1;
        res.push_back({a, b});
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<pair<ll, ll>> as(n);
  for (int i = 0; i < n; ++i) cin >> as[i].first >> as[i].second;
  int m;
  cin >> m;
  vector<pair<ll, ll>> bs(m);
  for (int i = 0; i < m; ++i) cin >> bs[i].first >> bs[i].second;
  vector<pair<ll, ll>> res;
  buildRes(as, bs, res);
  buildRes(bs, as, res);
  sort(res.begin(), res.end());
  ll ans = 0;
  ll lst = -1;
  for (auto pr : res) {
    ans += sum(max(lst + 1, pr.first), pr.second);
    lst = max(lst, pr.second);
  }
  cout << ans % MOD << '\n';
}
