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;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 1e4 + 10;
int n, m;
pair<long long, long long> a[N], b[N];
inline void rd(int &n, pair<long long, long long> *a) {
  int cnt = read();
  vector<pair<long long, long long> > v(cnt);
  for (register int i = (0); i < (cnt); i++)
    v[i].first = read(), v[i].second = read();
  sort((v).begin(), (v).end());
  long long l = v[0].first, r = v[0].second;
  for (register int i = (1); i < (cnt); i++)
    if (v[i].first <= r)
      r = max(r, v[i].second);
    else
      a[++n] = make_pair(l, r), l = v[i].first, r = v[i].second;
  a[++n] = make_pair(l, r);
}
vector<pair<long long, long long> > A, B, C;
inline void Insert(int len, long long l, long long r, long long ql,
                   long long qr) {
  if (l >= ql && r <= qr) return C.push_back(make_pair(len, l)), void(0);
  long long mid = l + r >> 1;
  if (ql <= mid) Insert(len - 1, l, mid, ql, qr);
  if (qr > mid) Insert(len - 1, mid + 1, r, ql, qr);
}
const int maxn = 1e6 + 3;
struct Hash_Table {
  int cnt, now_id, first[maxn], id[maxn], last[maxn];
  long long val1[maxn], val2[maxn];
  inline void init() { cnt = 0, ++now_id; }
  inline void insert(long long s, int v) {
    int S = s % maxn;
    if (id[S] != now_id) id[S] = now_id, first[S] = 0;
    for (int i = first[S]; i; i = last[i])
      if (val1[i] == s) return val2[i] += v, void(0);
    ++cnt, last[cnt] = first[S], first[S] = cnt, val1[cnt] = s, val2[cnt] = v;
  }
} h;
const int mod = 998244353, inv = (mod + 1) >> 1;
inline long long calc(long long l, long long r) {
  return (l + r) % mod * ((r - l + 1) % mod) % mod;
}
int main() {
  rd(n, a), rd(m, b);
  vector<pair<long long, long long> > mg;
  for (register int i = (1); i <= (n); i++)
    for (register int j = (1); j <= (m); j++) {
      C.clear();
      Insert(60, 0, (1ll << 60) - 1, a[i].first, a[i].second);
      A = C;
      C.clear();
      Insert(60, 0, (1ll << 60) - 1, b[j].first, b[j].second);
      B = C;
      h.init();
      for (auto x : A)
        for (auto y : B) {
          int d = max(x.first, y.first);
          long long l = ((x.second ^ y.second) >> d) << d;
          h.insert(l, 1), h.insert(l + (1ll << d), -1);
        }
      for (register int k = (1); k <= (h.cnt); k++)
        mg.push_back(make_pair(h.val1[k], h.val2[k]));
    }
  sort((mg).begin(), (mg).end());
  long long pre = 0, ans = 0, r = 0;
  for (auto i : mg) {
    if (pre > 0) ans = (ans + calc(r, i.first - 1)) % mod;
    pre += i.second, r = i.first;
  }
  printf("%d\n", ans * inv % mod);
}
