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>
#pragma GCC optimize("O3,Ofast")
#pragma GCC target( \
    "adx,aes,avx2,avx,bmi2,bmi,clflushopt,cx16,f16c,fma,fsgsbase,hle,lzcnt,movbe,sse4,pclmul,popcnt,prfchw,sahf,sse3,sse4.1,sse4.2,ssse3,xsavec,xsave,xsaveopt,xsaves")
using namespace std;
constexpr int kN = int(1E3 + 10);
constexpr int kMod = 998244353;
constexpr int kThreshold = 1 << 23;
static inline char Get_Raw_Char() {
  static char buf[1 << 16], *p = buf, *end = buf;
  if (p == end) {
    if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0';
    p = buf;
  }
  return *p++;
}
template <typename T>
static inline void Read_P(T &n) {
  static_assert(is_integral<T>::value);
  char c;
  while (!isdigit(c = Get_Raw_Char()))
    ;
  n = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
  return;
}
template <typename T>
static inline void Read(T &n) {
  static_assert(is_integral<T>::value);
  char c;
  bool neg = false;
  while (!isdigit(c = Get_Raw_Char()))
    if (c == '-') neg = true;
  n = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
  if (neg) n = -n;
  return;
}
template <typename T>
static inline void Read_Digit(T &n) {
  static_assert(is_integral<T>::value);
  char c;
  while (!isdigit(c = Get_Raw_Char()))
    ;
  n = int(c - '0');
  return;
}
template <typename T, typename... Targs>
static inline void Read(T &n, Targs &...Fargs) {
  Read(n);
  return Read(Fargs...);
}
template <typename T, typename... Targs>
static inline void Read_Digit(T &n, Targs &...Fargs) {
  Read_Digit(n);
  return Read_Digit(Fargs...);
}
template <typename T, typename... Targs>
static inline void Read_P(T &n, Targs &...Fargs) {
  Read_P(n);
  return Read_P(Fargs...);
}
template <typename T>
static inline void Read_Loop_i(int i, T *a) {
  return Read(a[i]);
}
template <typename T, typename... Targs>
static inline void Read_Loop_i(int i, T *a, Targs *...Fargs) {
  Read(a[i]);
  return Read_Loop_i(i, Fargs...);
}
template <typename... Targs>
static inline void Read_Loop(int n, Targs *...Fargs) {
  for (int i = 1; i <= n; i++) Read_Loop_i(i, Fargs...);
}
template <typename T>
static inline void Read_Loop_Digit_i(int i, T *a) {
  return Read_Digit(a[i]);
}
template <typename T, typename... Targs>
static inline void Read_Loop_Digit_i(int i, T *a, Targs *...Fargs) {
  Read_Digit(a[i]);
  return Read_Loop_Digit_i(i, Fargs...);
}
template <typename... Targs>
static inline void Read_Loop_Digit(int n, Targs *...Fargs) {
  for (int i = 1; i <= n; i++) Read_Loop_Digit_i(i, Fargs...);
}
template <typename T>
static inline void Read_Loop_P_i(int i, T *a) {
  return Read_P(a[i]);
}
template <typename T, typename... Targs>
static inline void Read_Loop_P_i(int i, T *a, Targs *...Fargs) {
  Read_P(a[i]);
  return Read_Loop_P_i(i, Fargs...);
}
template <typename... Targs>
static inline void Read_Loop_P(int n, Targs *...Fargs) {
  for (int i = 1; i <= n; i++) Read_Loop_P_i(i, Fargs...);
}
template <int mul, typename T>
static inline void Read(T &n) {
  char c;
  bool neg = false;
  while (!isdigit(c = Get_Raw_Char()))
    if (c == '-') neg = true;
  n = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
  int cnt = 0;
  if (c == '.') {
    while (isdigit(c = Get_Raw_Char())) {
      n = n * 10 + int(c - '0');
      cnt++;
    }
  }
  while (cnt++ < mul) n = n * 10;
  if (neg) n = -n;
  return;
}
template <int mul, typename T>
static inline void Read_P(T &n) {
  char c;
  while (!isdigit(c = Get_Raw_Char()))
    ;
  n = int(c - '0');
  while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0');
  int cnt = 0;
  if (c == '.') {
    while (isdigit(c = Get_Raw_Char())) {
      n = n * 10 + int(c - '0');
      cnt++;
    }
  }
  while (cnt++ < mul) n = n * 10;
  return;
}
template <int mul, typename T, typename... Targs>
static inline void Read(T &n, Targs &...Fargs) {
  Read<mul>(n);
  return Read<mul>(Fargs...);
}
template <int mul, typename T, typename... Targs>
static inline void Read_P(T &n, Targs &...Fargs) {
  Read_P<mul>(n);
  return Read_P<mul>(Fargs...);
}
inline void IOS() {
  ios::sync_with_stdio(false);
  cin.tie(0);
}
inline void Freopen(const char *in, const char *out) {
  freopen(in, "r", stdin);
  freopen(out, "w", stdout);
}
template <typename T>
void Print(T x) {
  if (x < 0) {
    printf("-");
    x = -x;
  }
  if (x == 0)
    printf("0");
  else {
    static int val[100];
    int idx = -1;
    while (x) {
      val[++idx] = x % 10;
      x /= 10;
    }
    while (idx >= 0) printf("%d", val[idx--]);
  }
}
template <typename T>
inline void sort(vector<T> &v) {
  return sort(v.begin(), v.end());
}
template <typename T>
inline void sort_r(vector<T> &v) {
  return sort(v.begin(), v.end(), greater<T>());
}
template <typename T>
inline void reverse(vector<T> &v) {
  return reverse(v.begin(), v.end());
}
template <typename T>
inline void Merge(vector<T> &a, vector<T> &b, vector<T> &c) {
  if (c.size() < a.size() + b.size()) c.resize(a.size() + b.size());
  merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
  return;
}
template <typename T>
inline void Discrete(vector<T> &v) {
  sort(v);
  v.resize(unique(v.begin(), v.end()) - v.begin());
}
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using PQ_R = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
inline T ABS(T n) {
  return n >= 0 ? n : -n;
}
template <typename T>
inline T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <typename T>
inline T lcm(T a, T b) {
  return a * b / gcd(a, b);
}
template <typename T, typename... Targs>
inline T min(T a, T b, T c, Targs... args) {
  return min(a, min(b, c, args...));
}
template <typename T, typename... Targs>
inline T max(T a, T b, T c, Targs... args) {
  return max(a, max(b, c, args...));
}
template <typename T>
inline void chmin(T &a, T b) {
  a = min(a, b);
  return;
}
template <typename T>
inline void chmax(T &a, T b) {
  a = max(a, b);
  return;
}
template <typename T, typename... Targs>
inline void chmin(T &a, T b, T c, Targs... args) {
  a = min(a, min(b, c, args...));
  return;
}
template <typename T, typename... Targs>
inline void chmax(T &a, T b, T c, Targs... args) {
  a = max(a, max(b, c, args...));
  return;
}
template <typename T>
inline int Digit_Sum(T a) {
  int ans = 0;
  while (a) {
    ans += a % 10;
    a /= 10;
  }
  return ans;
}
template <typename T>
inline int Num_Length(T a) {
  int ans = 1;
  while (a /= 10) ans++;
  return ans;
}
void _print(int x) { printf("%d", x); }
void _print(long long int x) { printf("%lld", x); }
void _print(double x) { printf("%lf", x); }
template <typename T>
void _print(T x) {
  return x.out();
}
template <typename T1, typename T2>
void _print(pair<T1, T2> x) {
  printf("(");
  _print(x.first);
  printf(", ");
  _print(x.second);
  printf(")");
}
template <typename T>
void _Debug(T x) {
  _print(x);
  printf("\n");
}
template <typename T>
void _Debug(vector<T> v) {
  if (v.empty())
    printf(" empty");
  else
    for (T i : v) printf(" "), _print(i);
  printf("\n");
}
template <typename T1, typename T2, typename T3>
void _Debug(priority_queue<T1, T2, T3> pq) {
  if (pq.empty())
    printf(" empty");
  else {
    while (!pq.empty()) {
      printf(" ");
      _print(pq.top());
      pq.pop();
    }
  }
  printf("\n");
}
template <typename T>
void _Debug(queue<T> q) {
  if (q.empty())
    printf(" empty");
  else {
    while (!q.empty()) {
      printf(" ");
      _print(q.front());
      q.pop();
    }
  }
  printf("\n");
}
template <typename T>
void _Debug(stack<T> st) {
  if (st.empty())
    printf(" empty");
  else {
    while (!st.empty()) {
      printf(" ");
      _print(st.top());
      st.pop();
    }
  }
  printf("\n");
}
template <typename T>
void _Debug(deque<T> dq) {
  if (dq.empty())
    printf(" empty");
  else {
    while (!dq.empty()) {
      printf(" ");
      _print(dq.front());
      dq.pop_front();
    }
  }
  printf("\n");
}
template <typename T>
void _Debugln(vector<T> v) {
  if (v.empty())
    printf(" empty\n");
  else {
    for (T i : v) printf("\n"), _print(i);
    printf("\n");
  }
}
template <typename T1, typename T2, typename T3>
void _Debugln(priority_queue<T1, T2, T3> pq) {
  if (pq.empty())
    printf(" empty");
  else {
    while (!pq.empty()) {
      printf("\n");
      _print(pq.top());
      pq.pop();
    }
  }
  printf("\n");
}
template <typename T>
void _Debugln(queue<T> q) {
  if (q.empty())
    printf(" empty");
  else {
    while (!q.empty()) {
      printf("\n");
      _print(q.front());
      q.pop();
    }
  }
  printf("\n");
}
template <typename T>
void _Debugln(stack<T> st) {
  if (st.empty())
    printf(" empty");
  else {
    while (!st.empty()) {
      printf("\n");
      _print(st.top());
      st.pop();
    }
  }
  printf("\n");
}
template <typename T>
void _Debugln(deque<T> dq) {
  if (dq.empty())
    printf(" empty");
  else {
    while (!dq.empty()) {
      printf("\n");
      _print(dq.front());
      dq.pop_front();
    }
  }
  printf("\n");
}
template <typename T>
void _Debug_Array(int n, const T *x) {
  for (int i = 1; i <= n; i++) printf(" "), _print(x[i]);
  printf("\n");
}
template <typename T>
void _Debugln_Array(int n, const T *x) {
  printf("\n");
  for (int i = 1; i <= n; i++) _print(x[i]), printf("\n");
}
template <typename T1, typename T2>
T1 Pow(T1 a, T2 b) {
  T1 ans(1);
  while (b) {
    if (b & 1) ans *= a;
    a *= a;
    b >>= 1;
  }
  return ans;
}
template <int kMod>
struct Mod_Int {
  constexpr static int Mod() { return kMod; }
  int val;
  Mod_Int() { val = 0; }
  template <typename T>
  Mod_Int(const T &x) {
    val = x;
  }
  template <int nMod>
  Mod_Int(const Mod_Int<nMod> &x) {
    val = x.val;
  }
  Mod_Int inv() const { return Pow(*this, kMod - 2); }
  Mod_Int operator+(const Mod_Int &x) const {
    Mod_Int ans(val + x.val);
    if (ans.val >= kMod) ans.val -= kMod;
    return ans;
  }
  Mod_Int operator-(const Mod_Int &x) const {
    Mod_Int ans(val - x.val);
    if (ans.val < 0) ans.val += kMod;
    return ans;
  }
  Mod_Int operator*(const Mod_Int &x) const {
    return Mod_Int(1LL * val * x.val % kMod);
  }
  Mod_Int operator/(const Mod_Int &x) const { return *this * x.inv(); }
  Mod_Int operator^(const Mod_Int &x) const { return Pow(*this, x.val); }
  Mod_Int operator<<(const int &x) const { return ((1LL * val) << x) % kMod; }
  Mod_Int operator+=(const Mod_Int &x) { return *this = *this + x; }
  Mod_Int operator-=(const Mod_Int &x) { return *this = *this - x; }
  Mod_Int operator*=(const Mod_Int &x) { return *this = *this * x; }
  Mod_Int operator/=(const Mod_Int &x) { return *this = *this / x; }
  Mod_Int operator^=(const Mod_Int &x) { return *this = Pow(*this, x.val); }
  Mod_Int operator<<=(const int &x) { return *this = *this << x; }
  Mod_Int operator++(int) {
    val++;
    if (val >= kMod) val -= kMod;
    return *this;
  }
  Mod_Int operator--(int) {
    val--;
    if (val < 0) val += kMod;
    return *this;
  }
  bool operator<(const Mod_Int &x) const { return val < x.val; }
  bool operator>(const Mod_Int &x) const { return val > x.val; }
  bool operator<=(const Mod_Int &x) const { return val <= x.val; }
  bool operator>=(const Mod_Int &x) const { return val >= x.val; }
  bool operator==(const Mod_Int &x) const { return val == x.val; }
  bool operator!=(const Mod_Int &x) const { return val != x.val; }
  void out() const { printf("%d", val); }
};
using Mint = Mod_Int<kMod>;
namespace Factorial {
Mint *f, *inf;
bool preprocessed_factorial;
void Pre_Factorial(const int &sz) {
  if (preprocessed_factorial) return;
  preprocessed_factorial = true;
  f = new Mint[sz + 1];
  inf = new Mint[sz + 1];
  f[0] = f[1] = inf[0] = inf[1] = 1;
  for (int i = 2; i <= sz; i++) f[i] = f[i - 1] * i;
  inf[sz] = f[sz].inv();
  for (int i = sz; i > 2; i--) inf[i - 1] = inf[i] * i;
  return;
}
inline Mint P(const int &n, const int &m) { return f[n] * inf[m]; }
inline Mint C(const int &n, const int &m) { return f[n] * inf[m] * inf[n - m]; }
inline Mint H(const int &n, const int &m) {
  return f[n + m - 1] * inf[m] * inf[n - 1];
}
inline Mint Catalan(const int &n) { return f[n << 1] * inf[n] * inf[n + 1]; }
}  // namespace Factorial
namespace Factorial_No_Inf {
Mint *f;
void Pre_Factorial(const int &sz) {
  f = new Mint[sz + 1];
  f[0] = f[1] = 1;
  for (int i = 2; i <= sz; i++) f[i] = f[i - 1] * i;
  return;
}
inline Mint P(const int &n, const int &m) { return f[n] / f[m]; }
inline Mint C(const int &n, const int &m) { return f[n] / (f[m] * f[n - m]); }
inline Mint H(const int &n, const int &m) {
  return f[n + m - 1] / (f[m] * f[n - 1]);
}
inline Mint Catalan(const int &n) { return f[n << 1] / (f[n] * f[n + 1]); }
}  // namespace Factorial_No_Inf
namespace Inverse {
using namespace Factorial;
Mint *inv;
void Pre_Inverse(const int &sz) {
  inv = new Mint[sz + 1];
  inv[1] = 1;
  Pre_Factorial(sz);
  for (int i = 1; i <= sz; i++) inv[i] = f[i - 1] * inf[i];
  return;
}
};  // namespace Inverse
long long int la[kN], ra[kN], lb[kN], rb[kN];
vector<pair<long long int, long long int>> decomp(long long int l,
                                                  long long int r) {
  vector<pair<long long int, long long int>> ans;
  while (l <= r) {
    long long int mask = l & -l;
    while (l + mask - 1 > r) mask >>= 1;
    ans.push_back(make_pair(l, l + mask - 1));
    l += mask;
  }
  return ans;
}
pair<long long int, long long int> cal(long long int l1, long long int r1,
                                       long long int l2, long long int r2) {
  l2 &= ~(r1 - l1);
  return make_pair(l1 ^ l2, r1 ^ l2);
}
int main() {
  int na;
  Read_P(na);
  Read_Loop_P(na, la, ra);
  int nb;
  Read_P(nb);
  Read_Loop_P(nb, lb, rb);
  vector<pair<long long int, int>> eventa, eventb;
  for (int i = 1; i <= na; i++) {
    eventa.push_back(make_pair(la[i], -1));
    eventa.push_back(make_pair(ra[i] + 1, 1));
  }
  sort(eventa);
  for (int i = 1; i <= nb; i++) {
    eventb.push_back(make_pair(lb[i], -1));
    eventb.push_back(make_pair(rb[i] + 1, 1));
  }
  sort(eventb);
  vector<pair<long long int, long long int>> tva, tvb;
  {
    long long int lst = 0, cur = 0;
    for (pair<long long int, int> i : eventa) {
      if (cur == 0) lst = i.first;
      cur -= i.second;
      if (cur == 0) tva.push_back(make_pair(lst, i.first - 1));
    }
    eventa.clear();
    eventa.shrink_to_fit();
  }
  {
    long long int lst = 0, cur = 0;
    for (pair<long long int, int> i : eventb) {
      if (cur == 0) lst = i.first;
      cur -= i.second;
      if (cur == 0) tvb.push_back(make_pair(lst, i.first - 1));
    }
    eventb.clear();
    eventb.shrink_to_fit();
  }
  vector<pair<long long int, long long int>> va, vb;
  for (pair<long long int, long long int> i : tva)
    for (pair<long long int, long long int> j : decomp(i.first, i.second))
      va.push_back(j);
  for (pair<long long int, long long int> i : tvb)
    for (pair<long long int, long long int> j : decomp(i.first, i.second))
      vb.push_back(j);
  tva.clear();
  tva.shrink_to_fit();
  tvb.clear();
  tvb.shrink_to_fit();
  ;
  ;
  ;
  ;
  vector<long long int> event[60];
  for (int times = 1; times <= 2; times++) {
    sort(va.begin(), va.end(),
         [](pair<long long int, long long int> a,
            pair<long long int, long long int> b) -> bool {
           return a.second - a.first < b.second - b.first;
         });
    sort(vb.begin(), vb.end());
    long long int lst_len = -1;
    vector<long long int> tmp_event;
    for (pair<long long int, long long int> i : va) {
      if (lst_len != i.second - i.first) {
        int id = 0;
        while (lst_len > 0) {
          lst_len >>= 1;
          id++;
        }
        Discrete(tmp_event);
        event[id].reserve(int(event[id].size()) + (int(tmp_event.size()) << 1));
        for (long long int j : tmp_event) event[id].push_back(j);
        tmp_event.clear();
        lst_len = i.second - i.first;
      }
      long long int lst = -1;
      for (pair<long long int, long long int> j : vb)
        if (i.second - i.first >= j.second - j.first) {
          long long int tmp = i.first ^ (j.first & ~(i.second - i.first));
          if (tmp != lst) {
            lst = tmp;
            tmp_event.push_back(tmp);
          }
        }
    }
    int id = 0;
    while (lst_len > 0) {
      lst_len >>= 1;
      id++;
    }
    Discrete(tmp_event);
    event[id].reserve(int(event[id].size()) + (int(tmp_event.size()) << 1));
    for (long long int j : tmp_event) event[id].push_back(j);
    tmp_event.clear();
    swap(va, vb);
  }
  va.clear();
  va.shrink_to_fit();
  vb.clear();
  vb.shrink_to_fit();
  for (int i = 0; i < 60; i++) Discrete(event[i]);
  int idx[60] = {0};
  PQ_R<pair<long long int, int>> pq;
  for (int i = 0; i < 60; i++)
    if (!event[i].empty()) pq.push(make_pair(event[i][0], i));
  Mint ans;
  long long int lst = -2, now = -2;
  while (!pq.empty()) {
    auto [val, id] = pq.top();
    pq.pop();
    if (val > now + 1) {
      if (lst >= 0)
        ans += ((now - lst + 1) % kMod) * ((lst + now) % kMod) % kMod;
      lst = val;
    }
    chmax(now, val + (1LL << id) - 1);
    if (idx[id] + 1 < int(event[id].size()))
      pq.push(make_pair(event[id][++idx[id]], id));
  }
  ans += ((now - lst + 1) % kMod) * ((lst + now) % kMod) % kMod;
  printf("%d\n", ans / 2);
}
