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;
const int maxn = 4e6 + 10, mod = 998244353;
const long long inf = 1e18;
const int BITS = 61;
vector<pair<long long, long long> > v;
int nxt[maxn][2], C = 0;
bool is[maxn];
void bfs(long long f1, long long s1, long long f2, long long s2) {
  set<pair<int,
           pair<pair<long long, long long>, pair<long long, long long> > > >
      st1, st2;
  st1.insert({0, {{0, 1ll << BITS}, {0, 1ll << BITS}}});
  while (int((st1).size())) {
    st2.clear();
    for (auto p : st1) {
      auto out = [](long long f, long long s, pair<long long, long long> p) {
        return s <= p.first || p.second <= f;
      };
      auto in = [](long long f, long long s, pair<long long, long long> p) {
        return f <= p.first && p.second <= s;
      };
      auto mid = [](pair<long long, long long> p) {
        return (p.first + p.second) >> 1;
      };
      auto add = [&](pair<int, pair<pair<long long, long long>,
                                    pair<long long, long long> > >
                         pp) {
        if (out(f1, s1, pp.second.first) || out(f2, s2, pp.second.second))
          return 0;
        if (in(f1, s1, pp.second.first) || in(f2, s2, pp.second.second)) {
          is[pp.first] = 1;
          return 1;
        }
        st2.insert(pp);
        return 1;
      };
      long long mid1 = mid(p.second.first), mid2 = mid(p.second.second);
      bool nw = 0;
      if (nxt[p.first][0] == 0) nxt[p.first][0] = ++C, nw = 1;
      assert(C < maxn);
      bool A =
          add({nxt[p.first][0],
               {{p.second.first.first, mid1}, {p.second.second.first, mid2}}});
      bool B = add(
          {nxt[p.first][0],
           {{mid1, p.second.first.second}, {mid2, p.second.second.second}}});
      if (A == 0 && B == 0 && nw) nxt[p.first][0] = 0, --C;
      nw = 0;
      if (nxt[p.first][1] == 0) nxt[p.first][1] = ++C, nw = 1;
      assert(C < maxn);
      A = add({nxt[p.first][1],
               {{p.second.first.first, mid1}, {mid2, p.second.second.second}}});
      B = add({nxt[p.first][1],
               {{mid1, p.second.first.second}, {p.second.second.first, mid2}}});
      if (A == 0 && B == 0 && nw) nxt[p.first][1] = 0, --C;
    }
    st1 = st2;
  }
}
long long ans;
void dfs(int u = 0, long long num = 0, int bt = BITS) {
  if (is[u]) {
    long long x = (1ll << bt) % mod;
    ans = (1ll * ans + (1ll * num * x % mod * x) +
           (1ll * (x - 1) * x % mod * ((mod + 1) / 2))) %
          mod;
    return;
  }
  if (nxt[u][0] != 0) dfs(nxt[u][0], (num << 1) % mod, bt - 1);
  if (nxt[u][1] != 0) dfs(nxt[u][1], (1 | (num << 1)) % mod, bt - 1);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie();
  int N;
  cin >> N;
  for (int i = 0; i < N; i++) {
    long long l, r;
    cin >> l >> r;
    v.push_back({l, ++r});
  }
  cin >> N;
  for (int i = 0; i < N; i++) {
    long long l, r;
    cin >> l >> r;
    ++r;
    for (pair<long long, long long> p : v) {
      bfs(l, r, p.first, p.second);
    }
  }
  dfs();
  return cout << ans << endl, 0;
}
