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;
int const N = 60, md = 998244353;
vector<long long> v[2][N + 1], u[2][N + 1], fn[N + 1];
int add(int x, int y) { return (x += y) >= md ? x - md : x; }
void ad(vector<long long> v[], long long x, long long y, long long l = 0,
        long long r = (1ll << 60) - 1, int ln = 0) {
  if (l > y || r < x) return;
  if (l >= x && r <= y) {
    v[ln].push_back(l & r);
    return;
  }
  long long m = l + r >> 1;
  ad(v, x, y, l, m, ln + 1);
  ad(v, x, y, m + 1, r, ln + 1);
}
void sru(vector<long long> &v) {
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
}
int sm(long long n) { return n % md * ((n + 1) % md) % md * 499122177 % md; }
int sm(long long l, long long r) { return add(sm(r) - sm(l - 1), md); }
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); ++i) {
    long long l, r;
    scanf("%lld %lld", &l, &r);
    ad(v[0], l, r);
  }
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); ++i) {
    long long l, r;
    scanf("%lld %lld", &l, &r);
    ad(v[1], l, r);
  }
  for (int t = 0; t < (int)(2); ++t)
    for (int i = 0; i < (int)(N + 1); ++i)
      for (long long z : v[t][i])
        for (int j = 0; j < (int)(i + 1); ++j)
          u[t][j].push_back(z & (1ll << j) - 1 << N - j);
  for (int t = 0; t < (int)(2); ++t)
    for (int i = 0; i < (int)(N + 1); ++i) sru(u[t][i]);
  for (int t = 0; t < (int)(2); ++t)
    for (int i = 0; i < (int)(N + 1); ++i)
      for (long long z : v[t][i])
        for (long long y : u[t ^ 1][i]) fn[i].push_back(z ^ y);
  for (int i = 0; i < (int)(N + 1); ++i) sru(fn[i]);
  for (int i = N; i > 0; --i)
    for (int j = 0; j < (int)(fn[i].size()); ++j)
      for (int k = 0; k < (int)(i); ++k)
        if (binary_search(fn[k].begin(), fn[k].end(),
                          fn[i][j] & (1ll << k) - 1 << N - k)) {
          swap(fn[i][j], fn[i].back());
          fn[i].pop_back();
          --j;
          break;
        }
  int an = 0;
  for (int i = 0; i < (int)(N + 1); ++i)
    for (long long u : fn[i]) an = add(an, sm(u, u | (1ll << N - i) - 1));
  printf("%d\n", an);
}
