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;
const int N = 30000, mod = 998244353, inv = (mod + 1) / 2;
const long long inf = (1ll << 60) - 1;
int n, num, ans;
struct node {
  long long l, r;
  node(long long x = 0, long long y = 0) : l(x), r(y) {}
  inline bool operator<(const node &x) const {
    if (l != x.l) return l < x.l;
    return r > x.r;
  }
  inline bool operator==(const node &x) const { return l == x.l && r == x.r; }
};
vector<node> seg;
struct segmentTree {
  int root, tot, isEnd[N], ls[N], rs[N];
  void insrt(long long x, long long y) { return insrt(root, x, y, 0, inf); }
  void insrt(int &p, long long x, long long y, long long lt, long long rt) {
    if (!p) p = ++tot;
    if ((lt >= x && rt <= y) || isEnd[p]) {
      isEnd[p] = 1;
      return;
    }
    if (x <= ((lt + rt) >> 1)) insrt(ls[p], x, y, lt, ((lt + rt) >> 1));
    if (y > ((lt + rt) >> 1)) insrt(rs[p], x, y, ((lt + rt) >> 1) + 1, rt);
    return;
  }
  void dfs1(int p, int depA, int depB, long long x, long long lt,
            long long rt) {
    if (!p) return;
    if (depA == depB)
      seg.push_back(
          node(((x ^ lt) | (lt ^ rt)) ^ lt ^ rt, (x ^ lt) | (lt ^ rt)));
    else
      dfs1(ls[p], depA, depB + 1, x, lt, ((lt + rt) >> 1)),
          dfs1(rs[p], depA, depB + 1, x, ((lt + rt) >> 1) + 1, rt);
    return;
  }
  void dfs2(int p, int dep, long long lt, long long rt, segmentTree *tar) {
    if (!p) return;
    if (isEnd[p])
      tar->dfs1(tar->root, dep, 1, lt, 0, inf);
    else
      dfs2(ls[p], dep + 1, lt, ((lt + rt) >> 1), tar),
          dfs2(rs[p], dep + 1, ((lt + rt) >> 1) + 1, rt, tar);
    return;
  }
} segA, segB;
template <class T>
inline void read(T &x) {
  x = 0;
  char ch = getchar(), w = 0;
  while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  x = w ? -x : x;
  return;
}
inline int calc(long long x, long long y) {
  long long a = (y - x + 1) % mod, b = (y + x) % mod;
  return a * b % mod * inv % mod;
}
int main() {
  long long l, r;
  read(n);
  while (n--) read(l), read(r), segA.insrt(l, r);
  read(n);
  while (n--) read(l), read(r), segB.insrt(l, r);
  segA.dfs2(segA.root, 1, 0, inf, &segB);
  segB.dfs2(segB.root, 1, 0, inf, &segA);
  sort(seg.begin(), seg.end());
  seg.resize(unique(seg.begin(), seg.end()) - seg.begin());
  long long lst = 0;
  for (auto &i : seg) {
    if (i.r <= lst) continue;
    ans = (ans + calc(i.l, i.r)) % mod, lst = i.r;
  }
  cout << ans << endl;
  return 0;
}
