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;
using ll = long long;
template <class t, class u>
void chmax(t& first, u second) {
  if (first < second) first = second;
}
template <class t, class u>
void chmin(t& first, u second) {
  if (second < first) first = second;
}
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
using pi = pair<ll, ll>;
using vi = vc<ll>;
template <class t, class u>
ostream& operator<<(ostream& os, const pair<t, u>& p) {
  return os << "{" << p.first << "," << p.second << "}";
}
template <class t>
ostream& operator<<(ostream& os, const vc<t>& v) {
  os << "{";
  for (auto e : v) os << e << ",";
  return os << "}";
}
using uint = unsigned;
using ull = unsigned long long;
template <ll i, class T>
void print_tuple(ostream&, const T&) {}
template <ll i, class T, class H, class... Args>
void print_tuple(ostream& os, const T& t) {
  if (i) os << ",";
  os << get<i>(t);
  print_tuple<i + 1, T, Args...>(os, t);
}
template <class... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
  os << "{";
  print_tuple<0, tuple<Args...>, Args...>(os, t);
  return os << "}";
}
void print(ll x, ll suc = 1) {
  cout << x;
  if (suc == 1) cout << "\n";
  if (suc == 2) cout << " ";
}
ll read() {
  ll i;
  cin >> i;
  return i;
}
vi readvi(ll n, ll off = 0) {
  vi v(n);
  for (ll i = ll(0); i < ll(n); i++) v[i] = read() + off;
  return v;
}
template <class T>
void print(const vector<T>& v, ll suc = 1) {
  for (ll i = ll(0); i < ll(v.size()); i++)
    print(v[i], i == ll(v.size()) - 1 ? suc : 2);
}
string readString() {
  string s;
  cin >> s;
  return s;
}
template <class T>
T sq(const T& t) {
  return t * t;
}
void yes(bool ex = true) {
  cout << "Yes" << endl;
  if (ex) exit(0);
}
void no(bool ex = true) {
  cout << "No" << endl;
  if (ex) exit(0);
}
constexpr ll ten(ll n) { return n == 0 ? 1 : ten(n - 1) * 10; }
const ll infLL = LLONG_MAX / 3;
const ll inf = infLL;
ll topbit(signed t) { return t == 0 ? -1 : 31 - __builtin_clz(t); }
ll topbit(ll t) { return t == 0 ? -1 : 63 - __builtin_clzll(t); }
ll botbit(signed first) { return first == 0 ? 32 : __builtin_ctz(first); }
ll botbit(ll first) { return first == 0 ? 64 : __builtin_ctzll(first); }
ll popcount(signed t) { return __builtin_popcount(t); }
ll popcount(ll t) { return __builtin_popcountll(t); }
bool ispow2(ll i) { return i && (i & -i) == i; }
ll mask(ll i) { return (ll(1) << i) - 1; }
bool inc(ll first, ll second, ll c) { return first <= second && second <= c; }
template <class t>
void mkuni(vc<t>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
ll rand_int(ll l, ll r) {
  static random_device rd;
  static mt19937_64 gen(rd());
  return uniform_int_distribution<ll>(l, r)(gen);
}
template <class t>
ll lwb(const vc<t>& v, const t& first) {
  return lower_bound(v.begin(), v.end(), first) - v.begin();
}
using uint = unsigned;
using ull = unsigned long long;
const uint mod = 998244353;
struct mint {
  uint v;
  mint(ll vv = 0) { s(vv % mod + mod); }
  mint& s(uint vv) {
    v = vv < mod ? vv : vv - mod;
    return *this;
  }
  mint operator-() const { return mint() - *this; }
  mint& operator+=(const mint& rhs) { return s(v + rhs.v); }
  mint& operator-=(const mint& rhs) { return s(v + mod - rhs.v); }
  mint& operator*=(const mint& rhs) {
    v = ull(v) * rhs.v % mod;
    return *this;
  }
  mint& operator/=(const mint& rhs) { return *this *= rhs.inv(); }
  mint operator+(const mint& rhs) const { return mint(*this) += rhs; }
  mint operator-(const mint& rhs) const { return mint(*this) -= rhs; }
  mint operator*(const mint& rhs) const { return mint(*this) *= rhs; }
  mint operator/(const mint& rhs) const { return mint(*this) /= rhs; }
  mint pow(ll n) const {
    mint res(1), x(*this);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
  mint inv() const { return pow(mod - 2); }
  friend ostream& operator<<(ostream& os, const mint& m) { return os << m.v; }
  bool operator<(const mint& r) const { return v < r.v; }
  bool operator==(const mint& r) const { return v == r.v; }
};
const ll vmax = 10;
mint fact[vmax], finv[vmax], invs[vmax];
void initfact() {
  fact[0] = 1;
  for (ll i = ll(1); i < ll(vmax); i++) {
    fact[i] = fact[i - 1] * i;
  }
  finv[vmax - 1] = fact[vmax - 1].inv();
  for (ll i = vmax - 2; i >= 0; i--) {
    finv[i] = finv[i + 1] * (i + 1);
  }
  for (ll i = vmax - 1; i >= 1; i--) {
    invs[i] = finv[i] * fact[i - 1];
  }
}
mint choose(ll n, ll k) { return fact[n] * finv[n - k] * finv[k]; }
mint binom(ll first, ll second) {
  return fact[first + second] * finv[first] * finv[second];
}
mint catalan(ll n) {
  return binom(n, n) - (n - 1 >= 0 ? binom(n - 1, n + 1) : 0);
}
mint sum(ll l, ll r) {
  mint res = mint(r) * (r - 1) * invs[2] - mint(l) * (l - 1) * invs[2];
  return res;
}
const ll L = 60;
void rec(ll second, ll e, ll l, ll r, ll d, vc<pi>& dst) {
  if (second <= l && r <= e) {
    dst.emplace_back(l, d);
    return;
  }
  if (e <= l || r <= second) {
    return;
  }
  const ll m = (l + r) / 2;
  rec(second, e, l, m, d - 1, dst);
  rec(second, e, m, r, d - 1, dst);
}
vc<pi> waf() {
  ll n;
  cin >> n;
  vc<pi> res;
  vc<pi> z;
  for (ll _ = ll(0); _ < ll(n); _++) {
    ll l, r;
    cin >> l >> r;
    r++;
    z.emplace_back(l, r);
  }
  sort(z.begin(), z.end());
  ll mx = -1;
  vc<pi> w;
  for (auto tmp : z) {
    ll l, r;
    tie(l, r) = tmp;
    if (mx < l) {
      w.emplace_back(l, r);
    } else {
      chmax(w.back().second, r);
    }
    chmax(mx, r);
  }
  for (auto tmp : w) {
    rec(tmp.first, tmp.second, 0, 1LL << L, L, res);
  }
  return res;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
  initfact();
  mint ans;
  {
    auto first = waf();
    void(0);
    auto second = waf();
    void(0);
    set<pi> rs;
    for (auto c : first)
      for (auto d : second) {
        ll p, q, r, s;
        tie(p, q) = c;
        tie(r, s) = d;
        ll u = max(q, s);
        ll left = (p ^ r) & ~mask(u);
        ll right = left + (1LL << u);
        auto itr = rs.lower_bound(pi(left, -1));
        if (itr != rs.begin()) {
          auto jtr = prev(itr);
          if (left <= jtr->second) {
            if (right <= jtr->second) continue;
            left = jtr->first;
            rs.erase(jtr);
          }
        }
        while (itr != rs.end() && itr->first <= right) {
          chmax(right, itr->second);
          itr = rs.erase(itr);
        }
        while (1) {
          if (itr == rs.begin()) break;
          itr--;
          if (itr->second < left) break;
          chmin(left, itr->first);
        }
        rs.emplace(left, right);
      }
    for (auto w : rs) {
      void(0);
      ans += sum(w.first, w.second);
    }
  }
  cout << ans << endl;
}
