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;
using cat = long long;
int main() {
  cin.sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  int N[2];
  vector<pair<cat, cat> > S[2];
  for (int k = 0; k < 2; k++) {
    cin >> N[k];
    S[k].resize(N[k]);
    for (int i = 0; i < N[k]; i++) cin >> S[k][i].first >> S[k][i].second;
  }
  for (int k = 0; k < 2; k++) {
    sort(begin(S[k]), end(S[k]));
    int cur = 0;
    for (int i = 0; i < (int)S[k].size(); i++) {
      if (cur && S[k][i].first <= S[k][cur - 1].second + 1)
        S[k][cur - 1].second = max(S[k][cur - 1].second, S[k][i].second);
      else
        S[k][cur++] = S[k][i];
    }
    S[k].resize(cur);
  }
  vector<cat> X[2][60], Y[2][60];
  for (int k = 0; k < 2; k++)
    for (int i = 0; i < N[k]; i++) {
      auto [l, r] = S[k][i];
      for (int d = 0; d < 60; d++) {
        if ((l >> d) & 1) {
          X[k][d].push_back(l >> d);
          l += 1LL << d;
        }
        if (l <= r && ((r >> d) & 1) == 0) {
          X[k][d].push_back(r >> d);
          r -= 1LL << d;
        }
        if (l > r) break;
      }
      for (int d = 0; d < 60; d++) {
        Y[k][d].push_back(S[k][i].first >> d);
        Y[k][d].push_back(S[k][i].second >> d);
      }
    }
  for (int k = 0; k < 60; k++) {
    sort(begin(X[0][k]), end(X[0][k]));
    auto it = unique(begin(X[0][k]), end(X[0][k]));
    X[0][k].resize(it - begin(X[0][k]));
    sort(begin(X[1][k]), end(X[1][k]));
    it = unique(begin(X[1][k]), end(X[1][k]));
    X[1][k].resize(it - begin(X[1][k]));
    sort(begin(Y[0][k]), end(Y[0][k]));
    it = unique(begin(Y[0][k]), end(Y[0][k]));
    Y[0][k].resize(it - begin(Y[0][k]));
    sort(begin(Y[1][k]), end(Y[1][k]));
    it = unique(begin(Y[1][k]), end(Y[1][k]));
    Y[1][k].resize(it - begin(Y[1][k]));
  }
  vector<pair<cat, cat> > seg;
  for (int k = 59; k >= 0; k--) {
    static vector<pair<cat, cat> > seg_next;
    seg_next.clear();
    static vector<cat> Z;
    Z.reserve((X[0][k].size() + Y[0][k].size()) *
              (X[1][k].size() * Y[1][k].size()));
    Z.clear();
    for (auto x : X[0][k])
      for (auto y : Y[1][k]) Z.push_back(x ^ y);
    for (auto x : Y[0][k])
      for (auto y : X[1][k]) Z.push_back(x ^ y);
    for (auto x : X[0][k])
      for (auto y : X[1][k]) Z.push_back(x ^ y);
    sort(begin(Z), end(Z));
    int a = 0;
    for (int i = 0; i < (int)Z.size(); i++) {
      if (i && Z[i] == Z[i - 1]) continue;
      cat l = Z[i] << k;
      while (a < (int)seg.size() && seg[a].second <= l) {
        seg_next.push_back(seg[a]);
        a++;
      }
      if (a < (int)seg.size() && seg[a].first <= l) continue;
      seg_next.push_back({l, l + (1LL << k)});
    }
    while (a < (int)seg.size()) {
      seg_next.push_back(seg[a]);
      a++;
    }
    seg.clear();
    for (int i = 0; i < (int)seg_next.size(); i++) {
      if (i && seg.back().second == seg_next[i].first)
        seg.back().second = seg_next[i].second;
      else
        seg.push_back(seg_next[i]);
    }
  }
  cat mod = 998244353, ans = 0;
  for (auto [l, r] : seg) {
    cat f1 = r - l, f2 = r + l - 1;
    if (f1 % 2 == 0)
      f1 /= 2;
    else
      f2 /= 2;
    f1 %= mod, f2 %= mod;
    ans += f1 * f2 % mod;
  }
  ans %= mod;
  cout << ans << "\n";
  return 0;
}
