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;
const long long mod = 998244353;
int n, m;
vector<pair<long long, long long>> segments_on[123][2], decomp_a[123][2];
void dfs_a(int h, long long L, long long R, long long l, long long r, int w) {
  if (L >= l && R <= r) {
    decomp_a[h][w].push_back({L, R});
    return;
  }
  if (l > R || r < L) return;
  long long mid = (L + R) >> 1;
  dfs_a(h - 1, L, mid, l, r, w);
  dfs_a(h - 1, mid + 1, R, l, r, w);
}
void dfs_b(int h, long long L, long long R, long long l, long long r, int w) {
  if (l > R || r < L) return;
  segments_on[h][w].push_back({L, R});
  if (L >= l && R <= r) return;
  long long mid = (L + R) >> 1;
  dfs_b(h - 1, L, mid, l, r, w);
  dfs_b(h - 1, mid + 1, R, l, r, w);
}
long long calc(long long x) {
  x %= mod;
  return (x) * (x + 1) >> 1LL % mod;
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    long long L, R;
    cin >> L >> R;
    dfs_a(60, 0, (1LL << 60) - 1, L, R, 0);
    dfs_b(60, 0, (1LL << 60) - 1, L, R, 1);
  }
  cin >> m;
  for (int i = 1; i <= m; i++) {
    long long L, R;
    cin >> L >> R;
    dfs_a(60, 0, (1LL << 60) - 1, L, R, 1);
    dfs_b(60, 0, (1LL << 60) - 1, L, R, 0);
  }
  vector<pair<long long, long long>> ans;
  for (int i = 0; i <= 60; i++) {
    for (int t = 0; t <= 1; t++) {
      for (auto p : segments_on[i][t]) {
        for (auto q : decomp_a[i][t]) {
          long long pref = (p.first ^ q.first) >> i;
          ans.emplace_back(pref << i, (pref << i) + (1LL << i) - 1);
        }
      }
    }
  }
  sort(ans.begin(), ans.end());
  long long res = 0;
  long long last = -1;
  for (auto p : ans) {
    p.first = max(p.first, last);
    if (p.first > p.second) continue;
    res += calc(p.second) - calc(p.first - 1);
    res += mod;
    last = p.second + 1;
    res %= mod;
  }
  cout << res << endl;
  return 0;
}
