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>
const int mod = 998244353, inv2 = (mod + 1) / 2;
using namespace std;
inline void modd(int &x) {
  if (x >= mod) x -= mod;
}
int na, nb;
const int P = 62;
int rt1, rt2, rt3, tot;
int ch[10000050][2], tag[10000050];
long long bin[105];
long long la[105], ra[105], lb[105], rb[105];
inline void addl(int p, int w, long long v) {
  for (int i = w, k; ~i; --i) {
    k = v >> i & 1;
    if (!ch[p][k]) ch[p][k] = ++tot;
    if (!k) ch[p][1] = ++tot, tag[ch[p][1]] = 1;
    p = ch[p][k];
  }
  tag[p] = 1;
}
inline void addr(int p, int w, long long v) {
  for (int i = w, k; ~i; --i) {
    k = v >> i & 1;
    if (!ch[p][k]) ch[p][k] = ++tot;
    if (k) ch[p][0] = ++tot, tag[ch[p][0]] = 1;
    p = ch[p][k];
  }
  tag[p] = 1;
}
inline void add(int rt, long long l, long long r) {
  int p = rt;
  for (int i = P, t1, t2; ~i; --i) {
    if (tag[p]) return;
    t1 = l >> i & 1;
    t2 = r >> i & 1;
    if (t1 == t2) {
      if (!ch[p][t1]) ch[p][t1] = ++tot;
      p = ch[p][t1];
    } else {
      if (!ch[p][t1]) ch[p][t1] = ++tot;
      if (!ch[p][t2]) ch[p][t2] = ++tot;
      addl(ch[p][t1], i - 1, l);
      addr(ch[p][t2], i - 1, r);
      break;
    }
  }
  if (l == r) tag[p] = 1;
}
inline void sear(int x, int y, int &z, int d) {
  if (!x || !y || tag[z]) return;
  if (!z) z = ++tot;
  if (tag[x] || tag[y]) return tag[z] = 1, void();
  sear(ch[x][0], ch[y][0], ch[z][0], d - 1);
  sear(ch[x][1], ch[y][1], ch[z][0], d - 1);
  sear(ch[x][0], ch[y][1], ch[z][1], d - 1);
  sear(ch[x][1], ch[y][0], ch[z][1], d - 1);
}
int dp[10000050], ans;
inline long long getsum(long long x) {
  x %= mod;
  return x * (x + 1) / 2 % mod;
}
inline void bl(int g, int d) {
  if (!g) return;
  if (tag[g]) {
    ++d;
    ans += getsum(bin[d] - 1);
    modd(ans);
    dp[g] = bin[d];
    return;
  }
  bl(ch[g][0], d - 1);
  dp[g] += dp[ch[g][0]], modd(dp[g]);
  bl(ch[g][1], d - 1);
  dp[g] += dp[ch[g][1]], modd(dp[g]);
  ans += bin[d] * dp[ch[g][1]] % mod;
  modd(ans);
}
int main() {
  for (int i = 0; i <= 63; ++i) bin[i] = (1ll << i) % mod;
  scanf("%d", &na);
  for (int i = 1; i <= na; ++i) scanf("%lld%lld", &la[i], &ra[i]);
  scanf("%d", &nb);
  for (int i = 1; i <= nb; ++i) scanf("%lld%lld", &lb[i], &rb[i]);
  rt1 = ++tot;
  rt2 = ++tot;
  for (int i = 1; i <= na; ++i) add(rt1, la[i], ra[i]);
  for (int i = 1; i <= nb; ++i) add(rt2, lb[i], rb[i]);
  sear(rt1, rt2, rt3, P);
  bl(rt3, P);
  cout << ans << endl;
  return 0;
}
