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 std::cerr;
using std::endl;
const int N = 2e6, P = 998244353, I2 = (P + 1) / 2;
int na, nb;
struct SegTree {
  static const long long lim = (1ll << 60) - 1;
  int ch[N][2], tot, root;
  bool tag[N];
  void modify(int &p, long long l, long long r, long long L, long long R) {
    if (!p) p = ++tot;
    if (l <= L && r >= R) {
      tag[p] = 1;
      return;
    }
    long long mid = (L + R) >> 1;
    if (l <= mid) modify(ch[p][0], l, r, L, mid);
    if (r > mid) modify(ch[p][1], l, r, mid + 1, R);
  }
  inline void modify(long long l, long long r) { modify(root, l, r, 0, lim); }
} A, B;
std::vector<std::pair<int, int>> vec[233];
long long dfs(int dep, long long val) {
  for (auto p : vec[dep])
    if (A.tag[p.first] || B.tag[p.second])
      return ((1ll << dep) % P * (((1ll << dep) - 1) % P * I2 % P + val % P)) %
             P;
  long long ret = 0;
  for (int i = 0; i < 2; ++i) {
    vec[dep - 1].clear();
    for (auto p : vec[dep])
      for (int j = 0; j < 2; ++j) {
        int x = A.ch[p.first][j], y = B.ch[p.second][j ^ i];
        if (x && y) vec[dep - 1].push_back({x, y});
      }
    if (!vec[dep - 1].empty())
      ret = (ret + dfs(dep - 1, val | ((long long)i << (dep - 1)))) % P;
  }
  return ret;
}
int main() {
  std::cin >> na;
  for (int i = 1; i <= na; ++i) {
    long long l, r;
    std::cin >> l >> r;
    A.modify(l, r);
  }
  std::cin >> nb;
  for (int i = 1; i <= nb; ++i) {
    long long l, r;
    std::cin >> l >> r;
    B.modify(l, r);
  }
  vec[60].push_back({A.root, B.root});
  std::cout << dfs(60, 0) << std::endl;
  return 0;
}
