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;
bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
  if (a.first != b.first) {
    return a.first < b.first;
  }
  return a.second > b.second;
}
const int maxn = (int)1e7;
struct vt {
  int ed[2];
  bool term;
  vt() {
    ed[0] = ed[1] = -1;
    term = false;
  }
};
vt mas[maxn];
int posit = 0;
int my_new() {
  if (posit == maxn) {
    throw 1;
  }
  return posit++;
}
void add(int t, long long x, int b, int mb) {
  if (b == mb) {
    mas[t].term = true;
    return;
  }
  int c = (x >> b) & 1;
  if (mas[t].ed[c] == -1) {
    mas[t].ed[c] = my_new();
  }
  add(mas[t].ed[c], x, b - 1, mb);
}
void make(vector<pair<long long, long long> > &a) {
  sort(a.begin(), a.end(), cmp);
  long long rm = -1;
  vector<pair<long long, long long> > res;
  for (int i = 0; i < (int)a.size(); i++) {
    if (a[i].second <= rm) {
      continue;
    } else {
      rm = a[i].second;
      res.push_back(a[i]);
    }
  }
  a = res;
}
int t;
void calc(long long la, long long ra, long long lb, long long rb) {
  add(t, la ^ lb, 59, -1);
  add(t, ra ^ rb, 59, -1);
  add(t, la ^ rb, 59, -1);
  add(t, ra ^ lb, 59, -1);
  for (int b = 59; b >= 0; b--) {
    long long lx = (la >> b);
    long long ly = (lb >> b);
    long long rx = (ra >> b);
    long long ry = (rb >> b);
    if (lx != rx && (lx + 1) != rx) {
      if ((lx & 1) == 0) {
        add(t, ((lx + 1) ^ ly) << b, 59, b - 1);
        add(t, ((lx + 1) ^ ry) << b, 59, b - 1);
      }
      if ((rx & 1) == 1) {
        add(t, ((rx - 1) ^ ly) << b, 59, b - 1);
        add(t, ((rx - 1) ^ ry) << b, 59, b - 1);
      }
    }
    if (ly != ry && (ly + 1) != ry) {
      if ((ly & 1) == 0) {
        add(t, (lx ^ (ly + 1)) << b, 59, b - 1);
        add(t, (rx ^ (ly + 1)) << b, 59, b - 1);
      }
      if (ry & 1) {
        add(t, (lx ^ (ry - 1)) << b, 59, b - 1);
        add(t, (rx ^ (ry - 1)) << b, 59, b - 1);
      }
    }
    if (lx != rx && (lx + 1) != rx && ly != ry && (ly + 1) != ry) {
      if ((lx & 1) == 0 && (ly & 1) == 0) {
        add(t, ((lx + 1) ^ (ly + 1)) << b, 59, b - 1);
      }
      if ((lx & 1) == 0 && (ry & 1) == 1) {
        add(t, ((lx + 1) ^ (ry - 1)) << b, 59, b - 1);
      }
      if ((rx & 1) == 1) {
        if ((ly & 1) == 0) {
          add(t, ((rx - 1) ^ (ly + 1)) << b, 59, b - 1);
        }
        if ((ry & 1) == 1) {
          add(t, ((rx - 1) ^ (ry - 1)) << b, 59, b - 1);
        }
      }
    }
  }
}
const int mod = 998244353;
const int maxlog = 135;
int st[maxlog];
int build(int t, int b, long long x) {
  if (mas[t].term) {
    int y = x % mod;
    y = (long long)y * st[b + 1] % mod;
    int ans = (long long)y * st[b + 1] % mod;
    ans += (long long)st[b] * (st[b + 1] - 1) % mod;
    ans %= mod;
    if (ans < 0) {
      ans += mod;
    }
    return ans;
  }
  int ans = 0;
  if (mas[t].ed[0] != -1) {
    ans = build(mas[t].ed[0], b - 1, x << 1);
  }
  if (mas[t].ed[1] != -1) {
    ans += build(mas[t].ed[1], b - 1, (x << 1) + 1);
    if (ans >= mod) {
      ans -= mod;
    }
  }
  return ans;
}
signed main() {
  t = my_new();
  int n;
  cin >> n;
  vector<pair<long long, long long> > a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  int m;
  cin >> m;
  vector<pair<long long, long long> > b(m);
  for (int i = 0; i < m; i++) {
    cin >> b[i].first >> b[i].second;
  }
  make(a);
  make(b);
  n = (int)a.size();
  m = (int)b.size();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      calc(a[i].first, a[i].second, b[j].first, b[j].second);
    }
  }
  st[0] = 1;
  for (int i = 1; i < maxlog; i++) {
    st[i] = st[i - 1] * 2 % mod;
  }
  int ans = build(t, 59, 0);
  cout << ans << endl;
}
