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 maxN = 100, maxLog = 61;
const int maxNode = maxN * 4 * maxLog * 4,
          maxRange = maxN * 2 * maxN * maxLog * 4;
const unsigned int mod = 998244353, inv2 = 499122177;
struct Range {
  unsigned long long l, r;
  inline friend std::istream &operator>>(std::istream &is, Range &r) {
    is >> r.l >> r.r;
    ++r.r;
    return is;
  }
  inline friend std::ostream &operator<<(std::ostream &os, const Range &r) {
    return os << "[" << r.l << ", " << r.r << ")";
  }
};
template <size_t maxSize>
class Vector {
 public:
  inline const Range *begin() const { return data; }
  inline const Range *end() const { return endPtr; }
  inline void push_back(Range vl) { *(endPtr++) = vl; }
  inline void clear() { endPtr = data; }
  inline friend std::istream &operator>>(std::istream &is, Vector &v) {
    size_t n;
    is >> n;
    v.endPtr = v.data + n;
    std::copy_n(std::istream_iterator<Range>(is), n, v.data);
    return is;
  }
  inline bool empty() const { return endPtr == data; }
  inline friend std::ostream &operator<<(std::ostream &os, const Vector &v) {
    std::copy<const Range *>(v.data, v.endPtr,
                             std::ostream_iterator<Range>(os, " "));
    return os;
  }
  Range data[maxSize], *endPtr;
};
struct Layer {
  Vector<maxN * 4> endpointA, visitB;
  void enumerate(const int dep, Vector<maxRange> &dest) const;
  inline void clear() {
    endpointA.clear();
    visitB.clear();
  }
  inline bool empty() const { return endpointA.empty() && visitB.empty(); }
  inline friend std::ostream &operator<<(std::ostream &os, const Layer &l) {
    return os << "endpointA: " << l.endpointA << "\nvisitB: " << l.visitB;
  }
} ranges[maxLog + 1];
class SegmentTree {
 public:
  void add(const long long l, const long long r);
  void mark(const long long l, const long long r);
  void collect(const int dep = 0) const;
  void init(const long long l, const long long r);
  static SegmentTree nodes[maxNode + 10], *cur;
  static inline SegmentTree *create(const long long l, const long long r);

 private:
  static inline SegmentTree *use(SegmentTree *&ptr, const long long l,
                                 const long long r);
  long long lv, mv, rv;
  SegmentTree *lc, *rc;
  bool visitB, endpointA;
} root;
SegmentTree SegmentTree::nodes[maxNode + 10],
    *SegmentTree::cur = SegmentTree::nodes;
void SegmentTree::add(const long long l, const long long r) {
  endpointA = true;
  if (l == lv && r == rv) {
    return;
  }
  if (r <= mv)
    use(lc, lv, mv)->add(l, r);
  else if (l >= mv)
    use(rc, mv, rv)->add(l, r);
  else {
    use(lc, lv, mv)->add(l, mv);
    use(rc, mv, rv)->add(mv, r);
  }
}
void SegmentTree::mark(const long long l, const long long r) {
  if ((l == lv && r == rv)) {
    visitB = true;
    return;
  }
  if (r <= mv)
    use(lc, lv, mv)->mark(l, r);
  else if (l >= mv)
    use(rc, mv, rv)->mark(l, r);
  else {
    use(lc, lv, mv)->mark(l, mv);
    use(rc, mv, rv)->mark(mv, r);
  }
}
void SegmentTree::collect(const int dep) const {
  const Range cur{static_cast<unsigned long long>(lv),
                  static_cast<unsigned long long>(rv)};
  if (visitB) ranges[dep].visitB.push_back(cur);
  if (endpointA) ranges[dep].endpointA.push_back(cur);
  if (lc) lc->collect(dep + 1);
  if (rc) rc->collect(dep + 1);
}
inline void SegmentTree::init(const long long l, const long long r) {
  lv = l;
  mv = (l + r) >> 1;
  rv = r;
  lc = rc = nullptr;
  visitB = endpointA = false;
}
inline SegmentTree *SegmentTree::use(SegmentTree *&ptr, const long long l,
                                     const long long r) {
  return ptr ? ptr : ptr = create(l, r);
}
inline SegmentTree *SegmentTree::create(const long long l, const long long r) {
  static SegmentTree nodes[maxNode + 10], *cur = nodes;
  cur->init(l, r);
  return cur++;
}
void Layer::enumerate(const int dep, Vector<maxRange> &dest) const {
  const unsigned long long lowMsk = (1ll << (maxLog - dep)) - 1,
                           highMsk = ~lowMsk;
  for (const Range &i : endpointA)
    for (const Range &j : visitB) {
      const unsigned long long prefix = (i.l & highMsk) ^ (j.l & highMsk);
      dest.push_back(Range{prefix, prefix + lowMsk + 1});
    }
}
unsigned int sumRange(Vector<maxRange> &dest) {
  static const auto sumInteger = [](unsigned long long l,
                                    unsigned long long r) -> unsigned int {
    return (((l + r) % mod * ((r - l + 1) % mod)) % mod * inv2) % mod;
  };
  unsigned long long ret = 0;
  std::sort(dest.data, dest.endPtr, [](const Range &l, const Range &r) {
    return l.l != r.l ? l.l < r.l : l.r < r.r;
  });
  unsigned long long mxl = 0;
  for (const Range &i : dest) {
    mxl = std::max(mxl, i.l);
    if (i.r > mxl) {
      ret += sumInteger(mxl, i.r - 1);
      mxl = i.r;
    }
  }
  return ret % mod;
}
void clear() {
  SegmentTree::cur = SegmentTree::nodes;
  for (auto &i : ranges) i.clear();
}
void sumXor(const Vector<maxN> &a, const Vector<maxN> &b,
            Vector<maxRange> &dest) {
  clear();
  root.init(0, 1ll << maxLog);
  std::for_each<const Range *>(a.data, a.endPtr,
                               [](const Range &i) { root.add(i.l, i.r); });
  std::for_each<const Range *>(b.data, b.endPtr,
                               [](const Range &i) { root.mark(i.l, i.r); });
  root.collect();
  for (int i = 0; i <= maxLog; ++i) ranges[i].enumerate(i, dest);
}
int main() {
  std::ios::sync_with_stdio(false);
  static Vector<maxN> a, b;
  std::cin >> a >> b;
  static Vector<maxRange> result;
  result.clear();
  sumXor(a, b, result);
  sumXor(b, a, result);
  std::cout << sumRange(result) << "\n";
  return 0;
}
