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;
bool home = 1;
signed realMain();
signed main() {
  home = 0;
  if (home) {
    freopen("input", "r", stdin);
  } else {
    ios::sync_with_stdio(0);
    cin.tie(0);
  }
  realMain();
}
const int M = 998244353;
int add(int a, int b) {
  a += b;
  if (a >= M) return a - M;
  if (a < 0) return a + M;
  return a;
}
int mul(int a, int b) { return a * (long long)b % M; }
int pw(int a, int b) {
  int r = 1;
  while (b) {
    if (b & 1) {
      r = mul(r, a);
    }
    a = mul(a, a);
    b /= 2;
  }
  return r;
}
int dv(int a, int b) { return mul(a, pw(b, M - 2)); }
struct seg {
  long long l;
  int free;
};
vector<seg> ret_split;
void rec(long long tl, long long tr, long long l, long long r, int cfree = 60) {
  if (tr < l || r < tl) {
    return;
  }
  if (l <= tl && tr <= r) {
    ret_split.push_back({tl, cfree});
    return;
  }
  long long tm = (tl + tr) / 2;
  rec(tl, tm, l, r, cfree - 1);
  rec(tm + 1, tr, l, r, cfree - 1);
}
vector<seg> split(long long l, long long r) {
  ret_split.clear();
  rec(0, (1LL << 60) - 1, l, r);
  return ret_split;
}
seg operator+(seg a, seg b) {
  long long pre1 = a.l, pre2 = b.l;
  int len = max(a.free, b.free);
  long long pre = (pre1 ^ pre2) / (1LL << len) * (1LL << len);
  return {pre, len};
}
const int N = 100 + 7;
const int i2 = dv(1, 2);
int n, m;
long long l1[N], r1[N], l2[N], r2[N];
vector<seg> unu[65], doi[65];
struct node {
  node* l;
  node* r;
  bool tot;
  node() {
    tot = 0;
    l = r = 0;
  }
};
node* root = new node;
int type;
vector<long long> la[3][100];
void baga2(node* now, long long tl, long long tr, long long l, long long r,
           int kek = 60) {
  if (now->tot) {
    return;
  }
  if (l <= tl && tr <= r) {
    now->tot = 1;
    return;
  }
  long long tm = (tl + tr) / 2;
  if (l <= tm) {
    if (!now->l) {
      now->l = new node;
      la[type][kek - 1].push_back(tl);
    }
    baga2(now->l, tl, tm, l, r, kek - 1);
  }
  if (tm + 1 <= r) {
    if (!now->r) {
      now->r = new node;
      la[type][kek - 1].push_back(tm + 1);
    }
    baga2(now->r, tm + 1, tr, l, r, kek - 1);
  }
}
void baga(node* now, long long tl, long long tr, long long l, long long r) {
  if (now->tot) {
    return;
  }
  if (l <= tl && tr <= r) {
    now->tot = 1;
    return;
  }
  long long tm = (tl + tr) / 2;
  if (l <= tm) {
    if (!now->l) now->l = new node;
    baga(now->l, tl, tm, l, r);
  }
  if (tm + 1 <= r) {
    if (!now->r) now->r = new node;
    baga(now->r, tm + 1, tr, l, r);
  }
}
int gauss(long long x) {
  x %= M;
  return mul(i2, mul(x, x + 1));
}
long long gauss(long long x, long long y) {
  return add(gauss(y), -gauss(x - 1));
}
int scoate(node* now, long long tl, long long tr) {
  if (now->tot) {
    return gauss(tl, tr);
  }
  long long tm = (tl + tr) / 2;
  int ret = 0;
  if (now->l) ret = add(ret, scoate(now->l, tl, tm));
  if (now->r) ret = add(ret, scoate(now->r, tm + 1, tr));
  return ret;
}
signed realMain() {
  cin >> n;
  vector<seg> segs1, segs2;
  for (int i = 1; i <= n; i++) {
    cin >> l1[i] >> r1[i];
    auto vec = split(l1[i], r1[i]);
    for (auto& s : vec) {
      segs1.push_back(s);
    }
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    cin >> l2[i] >> r2[i];
    auto vec = split(l2[i], r2[i]);
    for (auto& s : vec) {
      segs2.push_back(s);
    }
  }
  node* root1 = new node;
  node* root2 = new node;
  type = 1;
  la[type][60].push_back(0);
  for (auto& x : segs1) {
    baga2(root1, 0, (1LL << 60) - 1, x.l, x.l + (1LL << x.free) - 1);
  }
  type = 2;
  la[type][60].push_back(0);
  for (auto& y : segs2) {
    baga2(root2, 0, (1LL << 60) - 1, y.l, y.l + (1LL << y.free) - 1);
  }
  for (auto& x : segs1) {
    for (auto& val : la[2][x.free]) {
      seg y = {val, x.free};
      auto z = x + y;
      baga(root, 0, (1LL << 60) - 1, z.l, z.l + (1LL << z.free) - 1);
    }
  }
  for (auto& x : segs2) {
    for (auto& val : la[1][x.free]) {
      seg y = {val, x.free};
      auto z = x + y;
      baga(root, 0, (1LL << 60) - 1, z.l, z.l + (1LL << z.free) - 1);
    }
  }
  cout << scoate(root, 0, (1LL << 60) - 1) << "\n";
  return 0;
}
