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;
long long read() {
  long long r = 0, t = 1, c = getchar();
  while (c < '0' || c > '9') {
    t = c == '-' ? -1 : 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    r = r * 10 + c - 48;
    c = getchar();
  }
  return r * t;
}
const int N = 6010, mod = 998244353;
long long n, m, ans, r;
vector<pair<long long, long long> > c, a[N], b[N];
set<pair<long long, long long> > s;
void insert(set<pair<long long, long long> > &s, pair<long long, long long> a) {
  auto it = s.upper_bound(pair<long long, long long>(a.first, (~0ull) >> 1));
  if (it != s.begin()) {
    it--;
    if (it->first <= a.first && it->second >= a.second) return;
  }
  it = s.lower_bound(pair<long long, long long>(a.first, 0));
  while (it != s.end() && a.first <= it->first && a.second >= it->second)
    it = s.erase(it);
  s.insert(a);
  assert(s.size() <= 200000);
}
int main() {
  n = read();
  for (int i = (1), end_i = (n); i <= end_i; i++) {
    long long l = read(), r = read();
    while (r - l >= (l & (-l)) - 1) {
      a[i].push_back(pair<long long, long long>(l, l + (l & (-l)) - 1));
      l += l & (-l);
    }
    for (int j = (60), end_j = (0); j >= end_j; j--)
      if (r - l + 1 >= (1ll << j)) {
        a[i].push_back(pair<long long, long long>(l, l + (1ll << j) - 1));
        l += (1ll << j);
      }
  }
  m = read();
  for (int i = (1), end_i = (m); i <= end_i; i++) {
    long long l = read(), r = read();
    while (l + (l & (-l)) - 1 <= r) {
      b[i].push_back(pair<long long, long long>(l, l + (l & (-l)) - 1));
      l += l & (-l);
    }
    for (int j = (60), end_j = (0); j >= end_j; j--)
      if (r - l + 1 >= (1ll << j)) {
        b[i].push_back(pair<long long, long long>(l, l + (1ll << j) - 1));
        l += (1ll << j);
      }
  }
  for (int i = (1), end_i = (n); i <= end_i; i++)
    for (int j = (1), end_j = (m); j <= end_j; j++) {
      s.clear();
      for (auto A : a[i])
        for (auto B : b[j]) {
          long long w = max(A.second - A.first, B.second - B.first);
          insert(s, pair<long long, long long>((A.first ^ B.first) & (~w),
                                               (A.first ^ B.first) | w));
        }
      for (auto S : s) c.push_back(S);
    }
  sort(c.begin(), c.end(),
       [](pair<long long, long long> a, pair<long long, long long> b) {
         return a.first == b.first ? a.second > b.second : a.first < b.first;
       });
  for (auto C : c)
    if (C.second > r) {
      ans = (ans + ((C.second - C.first + 1) % mod) *
                       ((C.first + C.second) % mod) % mod * ((mod + 1) / 2)) %
            mod;
      r = C.second;
    }
  printf("%d\n", (int)ans);
  return 0;
}
