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;
template <class T>
void splitstr(const string &s, vector<T> &out) {
  istringstream in(s);
  out.clear();
  copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
}
static void redirect(int argc, const char **argv) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (argc > 1) {
    static filebuf f;
    f.open(argv[1], ios::in);
    cin.rdbuf(&f);
    if (!cin) {
      cerr << "Failed to open '" << argv[1] << "'" << endl;
      exit(1);
    }
  }
  if (argc > 2) {
    static filebuf f;
    f.open(argv[2], ios::out | ios::trunc);
    cout.rdbuf(&f);
    if (!cout) {
      cerr << "Failed to open '" << argv[2] << "'" << endl;
    }
  }
  cin.exceptions(ios::failbit);
}
template <typename T>
static constexpr T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
static constexpr T wrap_pos(T a, T m) {
  return a < 0 ? a + m : a;
}
template <typename T>
static constexpr T sqr(T a) {
  return a * a;
}
template <typename T>
static constexpr T mod(T a, T m) {
  return wrap_pos(a % m, m);
}
template <typename T>
static constexpr T inverse2(T a, T m) {
  return a <= 1 ? a : mod((1 - inverse2(m % a, a) * m) / a, m);
}
template <typename T>
static constexpr T inverse(T a, T m) {
  return inverse2(mod(a, m), m);
}
template <typename T, typename P>
static constexpr T power(T a, P b) {
  return b == 0 ? T(1) : (b % 2) ? power(a, b - 1) * a : sqr(power(a, b / 2));
}
template <typename T, typename C, T Modulus>
class MR {
 private:
  struct tag_plus {};
  struct tag_minus {};
  struct tag_good {};
  T value;
  static_assert(std::numeric_limits<C>::max() / Modulus / Modulus > 0,
                "compute type is too small");
  static_assert(Modulus < std::numeric_limits<T>::max() / 2,
                "storage type is too small");
  static constexpr T reduce(T value, tag_plus) {
    return value >= Modulus ? value - Modulus : value;
  }
  static constexpr T reduce(T value, tag_minus) {
    return value < 0 ? value + Modulus : value;
  }
  static constexpr T reduce(T value, tag_good) { return value; }

 public:
  static constexpr T modulus = Modulus;
  constexpr MR() : value(0) {}
  constexpr MR(C value) : value(reduce(value % Modulus, tag_minus())) {}
  template <typename tag_t>
  constexpr MR(T value, tag_t tag) : value(reduce(value, tag)) {}
  MR &operator=(C value) {
    this->value = reduce(value % Modulus, tag_minus());
    return *this;
  }
  constexpr MR operator+(MR b) const { return MR(value + b.value, tag_plus()); }
  constexpr MR operator-(MR b) const {
    return MR(value - b.value, tag_minus());
  }
  constexpr MR operator*(MR b) const {
    return MR(C(value) * C(b.value) % Modulus, tag_good());
  }
  constexpr MR operator-() const { return MR(-value, tag_minus()); }
  MR &operator+=(MR b) {
    value = reduce(value + b.value, tag_plus());
    return *this;
  }
  MR &operator-=(MR b) {
    value = reduce(value - b.value, tag_minus());
    return *this;
  }
  MR &operator*=(MR b) {
    value = C(value) * C(b.value) % Modulus;
    return *this;
  }
  constexpr bool operator==(MR b) const { return value == b.value; }
  constexpr bool operator!=(MR b) const { return value != b.value; }
  constexpr T get() const { return value; }
  constexpr MR inverse() const {
    return MR(::inverse(C(value), C(Modulus)), tag_good());
  }
  constexpr MR operator/(MR b) const { return *this * b.inverse(); }
  MR &operator/=(MR b) { return *this *= b.inverse(); }
};
template <typename T, typename C, T Modulus>
static inline std::ostream &operator<<(std::ostream &o, MR<T, C, Modulus> mr) {
  return o << mr.get();
}
struct chunk {
  long long prefix;
  long long sbits;
  bool operator<(const chunk &other) const {
    return make_pair(prefix, -sbits) < make_pair(other.prefix, -other.sbits);
  }
  bool operator==(const chunk &other) const {
    return prefix == other.prefix && sbits == other.sbits;
  }
  chunk parent() const {
    long long mask = (2LL << sbits) - 1;
    return chunk{prefix & ~mask, sbits + 1};
  }
};
struct chunk_group {
  array<vector<chunk>, 61> real, aux;
};
void add_cg(chunk_group &a, const chunk_group &b) {
  for (int i = 0; i <= 60; i++) {
    a.real[i].insert(a.real[i].end(), begin(b.real[i]), end(b.real[i]));
    a.aux[i].insert(a.aux[i].end(), begin(b.aux[i]), end(b.aux[i]));
  }
}
static chunk operator^(const chunk &a, const chunk &b) {
  chunk out;
  out.sbits = max(a.sbits, b.sbits);
  long long mask = (1LL << out.sbits) - 1;
  out.prefix = (a.prefix ^ b.prefix) & ~mask;
  return out;
}
static chunk_group make_chunks(long long L, long long R) {
  chunk_group out;
  for (long long i = 0; L < R; i++) {
    long long mask = 1LL << i;
    if (L & mask) {
      out.real[i].push_back(chunk{L, i});
      L += mask;
    }
    if (R & mask) {
      R -= mask;
      out.real[i].push_back(chunk{R, i});
    }
  }
  for (int i = 0; i < 60; i++) {
    for (const chunk &c : out.real[i]) {
      chunk p = c.parent();
      if (!count(begin(out.aux[i + 1]), end(out.aux[i + 1]), p))
        out.aux[i + 1].push_back(p);
    }
    for (const chunk &c : out.aux[i]) {
      chunk p = c.parent();
      if (!count(begin(out.aux[i + 1]), end(out.aux[i + 1]), p))
        out.aux[i + 1].push_back(p);
    }
  }
  return out;
}
static chunk_group load_cg() {
  int N;
  cin >> N;
  chunk_group out;
  for (int i = 0; i < N; i++) {
    long long L, R;
    cin >> L >> R;
    auto cg = make_chunks(L, R + 1);
    add_cg(out, cg);
  }
  return out;
}
int main(int argc, const char **argv) {
  redirect(argc, argv);
  chunk_group ag = load_cg();
  chunk_group bg = load_cg();
  vector<chunk> cs;
  for (int i = 0; i < 60; i++) {
    for (const chunk &a : ag.real[i])
      for (const chunk &b : bg.aux[i]) cs.push_back(a ^ b);
    for (const chunk &a : ag.aux[i])
      for (const chunk &b : bg.real[i]) cs.push_back(a ^ b);
    for (const chunk &a : ag.real[i])
      for (const chunk &b : bg.real[i]) cs.push_back(a ^ b);
  }
  sort(begin(cs), end(cs));
  chunk last{LLONG_MAX, 0};
  MR<int, long long, 998244353> ans = 0;
  constexpr MR<int, long long, 998244353> half =
      MR<int, long long, 998244353>(1) / MR<int, long long, 998244353>(2);
  for (const chunk &c : cs) {
    long long lmask = (1LL << last.sbits) - 1;
    if (c.sbits <= last.sbits && (c.prefix & ~lmask) == last.prefix) continue;
    long long p = c.prefix;
    long long q = c.prefix + (1LL << c.sbits) - 1;
    ans += MR<int, long long, 998244353>(p + q) *
           MR<int, long long, 998244353>(q - p + 1) * half;
    last = c;
  }
  cout << ans << '\n';
  return 0;
}
