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;
namespace mine {
long long qread() {
  long long ans = 0, f = 1;
  char c = getchar();
  while (c < '0' or c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while ('0' <= c and c <= '9') ans = ans * 10 + c - '0', c = getchar();
  return ans * f;
}
void write(long long num) {
  if (num < 0) putchar('-'), num = -num;
  if (num >= 10) write(num / 10);
  putchar('0' + num % 10);
}
void write1(long long num) {
  write(num);
  putchar(' ');
}
void write2(long long num) {
  write(num);
  putchar('\n');
}
template <typename T>
void chmax(T &x, const T y) {
  x = (x > y ? x : y);
}
template <typename T>
void chmin(T &x, const T y) {
  x = (x < y ? x : y);
}
long long gcd(long long x, long long y) { return y ? gcd(y, x % y) : x; }
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
int mm(const int x) { return x >= MOD ? x - MOD : x; }
template <typename T>
void add(T &x, const int &y) {
  x = (x + y >= MOD ? x + y - MOD : x + y);
}
long long qpower(long long x, long long e, int mod = MOD) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % mod;
    x = x * x % mod;
    e >>= 1;
  }
  return ans;
}
long long invm(long long x) { return qpower(x, MOD - 2); }
const int N = 2e5 + 10;
vector<pair<long long, long long> > split(long long l, long long r) {
  if (l == r) return {{l, 0}};
  int t = 60;
  while (((l ^ r) >> t) == 0) t--;
  long long m = (1ll << (t)) - 1;
  return {{l ^ (l & m) ^ m, (l & m) ^ m}, {r ^ (r & m), r & m}};
}
long long join(long long x, long long y) {
  return x | y | ((1ll << ((int)log2(x & y))) - 1);
}
vector<pair<long long, long long> > all;
void solve(long long al, long long ar, long long bl, long long br) {
  for (auto x : split(al, ar))
    for (auto y : split(bl, br)) {
      long long f = x.first ^ y.first, g = join(x.second, y.second) + 1;
      for (int i = (0), I = (60); i <= I; i++)
        if (g & (1ll << (i))) {
          long long L = (g >> (i + 1) << (i + 1)) ^ (f >> i << i);
          all.push_back({L, L + (1ll << (i)) - 1});
        }
    }
}
void main() {
  int n = qread();
  vector<pair<long long, long long> > A(n);
  for (int i = (0), I = (n - 1); i <= I; i++)
    A[i].first = qread(), A[i].second = qread();
  n = qread();
  vector<pair<long long, long long> > B(n);
  for (int i = (0), I = (n - 1); i <= I; i++)
    B[i].first = qread(), B[i].second = qread();
  for (auto a : A)
    for (auto b : B) solve(a.first, a.second, b.first, b.second);
  sort((all).begin(), (all).end());
  long long R = -1, ans = 0;
  for (auto t : all)
    if (R < t.second) {
      long long l = max(R + 1, t.first) % MOD, r = t.second % MOD;
      (ans += (r + 1) * r - l * (l - 1)) %= MOD;
      R = t.second;
    }
  write((ans * invm(2) % MOD + MOD) % MOD);
}
};  // namespace mine
signed main() {
  srand(time(0));
  mine::main();
}
