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;
inline long long read() {
  long long data = 0, w = 1;
  char ch = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') w = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();
  return data * w;
}
long long m;
struct ival {
  long long l, r;
} w[5000005];
struct Con {
  long long n;
  ival a[105];
} A, B;
vector<long long> v[65];
const long long M = 60;
void dicon(long long l, long long r, long long ql, long long qr, long long d) {
  v[d].push_back(l);
  if (ql <= l && r <= qr) return;
  long long mid = l + r >> 1;
  if (ql <= mid) dicon(l, mid, ql, qr, d + 1);
  if (mid < qr) dicon(mid + 1, r, ql, qr, d + 1);
}
const long long mod = 998244353;
long long Sum(long long l, long long r) {
  l %= mod;
  r %= mod;
  return (r * (r + 1) - (l - 1) * l) % mod * (mod + 1) / 2 % mod;
}
void Solve(long long l, long long r, long long ql, long long qr, long long d) {
  if (ql <= l && r <= qr) {
    for (auto p : v[d]) w[++m] = (ival){l ^ p, (l ^ p) + (1ll << M - d) - 1};
    return;
  }
  long long mid = l + r >> 1;
  if (ql <= mid) Solve(l, mid, ql, qr, d + 1);
  if (mid < qr) Solve(mid + 1, r, ql, qr, d + 1);
}
void clac() {
  for (long long i = 0; i <= M; i++) v[i].clear();
  for (long long i = 1; i <= B.n; i++)
    dicon(0, (1ll << M) - 1, B.a[i].l, B.a[i].r, 0);
  for (long long i = 1; i <= A.n; i++)
    Solve(0, (1ll << M) - 1, A.a[i].l, A.a[i].r, 0);
}
int main() {
  A.n = read();
  for (long long i = 1; i <= A.n; i++) A.a[i].l = read(), A.a[i].r = read();
  B.n = read();
  for (long long i = 1; i <= B.n; i++) B.a[i].l = read(), B.a[i].r = read();
  clac();
  swap(A, B), clac();
  sort(w + 1, w + m + 1, [](ival A, ival B) { return A.l < B.l; });
  ival now;
  now = w[1];
  long long ans = 0;
  for (long long i = 2; i <= m; i++) {
    if (now.r < w[i].l)
      ans = (ans + Sum(now.l, now.r)) % mod, now = w[i];
    else
      now.r = max(now.r, w[i].r);
  }
  ans = (ans + Sum(now.l, now.r)) % mod;
  cout << (ans % mod + mod) % mod << '\n';
  return 0;
}
