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>
const int MN = 105;
const int MOD = 998244353;
const int MB = 62;
const int M2 = MOD + 1 >> 1;
using ll = long long;
ll F;
bool is_submask(ll x, ll y) { return (x & y) == x; }
struct S {
 public:
  ll l, r;
  void in(void) { scanf("%lld%lld", &l, &r), ++r; }
  bool operator<(const S& o) const { return l < o.l || !(o.l < l) && r > o.r; }
};
struct R {
 public:
  ll v;
  int b;
  bool operator<(R o) const { return v < o.v || !(o.v < v) && b > o.b; }
  bool operator==(R o) const { return v == o.v && b == o.b; }
  bool rem(R o) const {
    if (!~b) return false;
    return is_submask(o.v & ~((1LL << b) - 1), v);
  }
};
void compress(std::vector<S>* a, std::vector<S>* b) {
  std::sort(a->begin(), a->end());
  b->clear();
  S c = a->front();
  for (S x : *a)
    if (c.r < x.l)
      b->push_back(c), c = x;
    else if (x.r > c.r)
      c.r = x.r;
  b->push_back(c);
  a->clear();
}
void transferSR(std::vector<S>* a, std::vector<R>* b, std::vector<ll>* c) {
  ll l0, l, r;
  int i;
  bool r0;
  for (S x : *a) {
    for (i = r0 = 0, l0 = l = x.l, r = x.r; l < r;
         l0 >>= 1, l >>= 1, r >>= 1, ++i) {
      if (l0 < l) c[i].push_back(l0 << i);
      if (r0) c[i].push_back(r << i);
      if (l & 1) c[i].push_back(l << i), b->push_back({l << i, i}), ++l;
      if (r & 1) --r, c[i].push_back(r << i), b->push_back({r << i, i}), r0 = 1;
    }
    for (; i < MB; l0 >>= 1, r >>= 1, ++i) {
      c[i].push_back(l0 << i);
      if (r0 && l0 < r) c[i].push_back(r << i);
    }
  }
  a->clear();
}
int N[2];
std::vector<S> a[2];
std::vector<S> b[2];
std::vector<R> c[2];
std::vector<ll> d[2][MB];
std::vector<R> e;
int main(void) {
  for (int i = 0; i < 2; ++i) {
    a[i].reserve(MN);
    b[i].reserve(MN);
    c[i].reserve(MN * MB * 2);
    for (int j = 0; j < MB; ++j) d[i][j].reserve(MN * 4);
  }
  e.reserve(MN * 4 * MN * MB * 2);
  for (int i : {0, 1}) {
    scanf("%d", N + i);
    a[i].assign(N[i], {-1, -1});
    for (int j = 0; j < N[i]; ++j) a[i][j].in();
    compress(a + i, b + i);
    transferSR(b + i, c + i, d[i]);
    for (int j = 0; j < MB; ++j)
      d[i][j].resize(std::distance(
          d[i][j].begin(), std::unique(d[i][j].begin(), d[i][j].end())));
  }
  for (int i : {0, 1})
    for (R x : c[i])
      for (ll y : d[!i][x.b]) e.push_back({x.v ^ y, x.b});
  std::sort(e.begin(), e.end());
  R t = {-1LL, -1};
  ll q;
  for (R x : e)
    if (!t.rem(x))
      t = x, q = (1LL << x.b) % MOD,
      F = (F + x.v % MOD * q + q * (q - 1) / 2) % MOD;
  printf("%d\n", static_cast<int>(F));
  return 0;
}
