#line 1 "library/my_template.hpp"
#if defined(LOCAL)
#include <my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pi = pair<ll, ll>;
using vi = vector<ll>;
using u32 = unsigned int;
using u64 = unsigned long long;
using i128 = __int128;

template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define vv(type, name, h, ...) \
  vector<vector<type>> name(h, vector<type>(__VA_ARGS__))
#define vvv(type, name, h, w, ...)   \
  vector<vector<vector<type>>> name( \
      h, vector<vector<type>>(w, vector<type>(__VA_ARGS__)))
#define vvvv(type, name, a, b, c, ...)       \
  vector<vector<vector<vector<type>>>> name( \
      a, vector<vector<vector<type>>>(       \
             b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))

// https://trap.jp/post/1224/
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define FOR1_R(a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR2_R(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define FOR3_R(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload4(a, b, c, d, e, ...) e
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload3(__VA_ARGS__, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)

#define FOR_subset(t, s) \
  for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define elif else if

#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second

#define stoi stoll

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T, typename U>
T ceil(T x, U y) {
  return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
  return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T, typename U>
pair<T, T> divmod(T x, U y) {
  T q = floor(x, y);
  return {q, x - q * y};
}

template <typename T, typename U>
T SUM(const vector<U> &A) {
  T sum = 0;
  for (auto &&a: A) sum += a;
  return sum;
}

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))
#define UNIQUE(x) \
  sort(all(x)), x.erase(unique(all(x)), x.end()), x.shrink_to_fit()

template <typename T>
T POP(deque<T> &que) {
  T a = que.front();
  que.pop_front();
  return a;
}
template <typename T>
T POP(pq<T> &que) {
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(pqg<T> &que) {
  assert(!que.empty());
  T a = que.top();
  que.pop();
  return a;
}
template <typename T>
T POP(vc<T> &que) {
  assert(!que.empty());
  T a = que.back();
  que.pop_back();
  return a;
}

template <typename F>
ll binary_search(F check, ll ok, ll ng) {
  assert(check(ok));
  while (abs(ok - ng) > 1) {
    auto x = (ng + ok) / 2;
    tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
  }
  return ok;
}
template <typename F>
double binary_search_real(F check, double ok, double ng, int iter = 100) {
  FOR(iter) {
    double x = (ok + ng) / 2;
    tie(ok, ng) = (check(x) ? mp(x, ng) : mp(ok, x));
  }
  return (ok + ng) / 2;
}

template <class T, class S>
inline bool chmax(T &a, const S &b) {
  return (a < b ? a = b, 1 : 0);
}
template <class T, class S>
inline bool chmin(T &a, const S &b) {
  return (a > b ? a = b, 1 : 0);
}

// ? は -1
vc<int> s_to_vi(const string &S, char first_char) {
  vc<int> A(S.size());
  FOR(i, S.size()) { A[i] = (S[i] != '?' ? S[i] - first_char : -1); }
  return A;
}

template <typename T, typename U>
vector<T> cumsum(vector<U> &A, int off = 1) {
  int N = A.size();
  vector<T> B(N + 1);
  FOR(i, N) { B[i + 1] = B[i] + A[i]; }
  if (off == 0) B.erase(B.begin());
  return B;
}

// stable sort
template <typename T>
vector<int> argsort(const vector<T> &A) {
  vector<int> ids(len(A));
  iota(all(ids), 0);
  sort(all(ids),
       [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); });
  return ids;
}

// A[I[0]], A[I[1]], ...
template <typename T>
vc<T> rearrange(const vc<T> &A, const vc<int> &I) {
  vc<T> B(len(I));
  FOR(i, len(I)) B[i] = A[I[i]];
  return B;
}
#endif
#line 1 "library/other/io.hpp"
// based on yosupo's fastio
#include <unistd.h>

namespace fastio {
#define FASTIO
// クラスが read(), print() を持っているかを判定するメタ関数
struct has_write_impl {
  template <class T>
  static auto check(T &&x) -> decltype(x.write(), std::true_type{});

  template <class T>
  static auto check(...) -> std::false_type;
};

template <class T>
class has_write : public decltype(has_write_impl::check<T>(std::declval<T>())) {
};

struct has_read_impl {
  template <class T>
  static auto check(T &&x) -> decltype(x.read(), std::true_type{});

  template <class T>
  static auto check(...) -> std::false_type;
};

template <class T>
class has_read : public decltype(has_read_impl::check<T>(std::declval<T>())) {};

struct Scanner {
  FILE *fp;
  char line[(1 << 15) + 1];
  size_t st = 0, ed = 0;
  void reread() {
    memmove(line, line + st, ed - st);
    ed -= st;
    st = 0;
    ed += fread(line + ed, 1, (1 << 15) - ed, fp);
    line[ed] = '\0';
  }
  bool succ() {
    while (true) {
      if (st == ed) {
        reread();
        if (st == ed) return false;
      }
      while (st != ed && isspace(line[st])) st++;
      if (st != ed) break;
    }
    if (ed - st <= 50) {
      bool sep = false;
      for (size_t i = st; i < ed; i++) {
        if (isspace(line[i])) {
          sep = true;
          break;
        }
      }
      if (!sep) reread();
    }
    return true;
  }
  template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
  bool read_single(T &ref) {
    if (!succ()) return false;
    while (true) {
      size_t sz = 0;
      while (st + sz < ed && !isspace(line[st + sz])) sz++;
      ref.append(line + st, sz);
      st += sz;
      if (!sz || st != ed) break;
      reread();
    }
    return true;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  bool read_single(T &ref) {
    if (!succ()) return false;
    bool neg = false;
    if (line[st] == '-') {
      neg = true;
      st++;
    }
    ref = T(0);
    while (isdigit(line[st])) { ref = 10 * ref + (line[st++] & 0xf); }
    if (neg) ref = -ref;
    return true;
  }
  template <typename T,
            typename enable_if<has_read<T>::value>::type * = nullptr>
  inline bool read_single(T &x) {
    x.read();
    return true;
  }
  bool read_single(double &ref) {
    string s;
    if (!read_single(s)) return false;
    ref = std::stod(s);
    return true;
  }
  bool read_single(char &ref) {
    string s;
    if (!read_single(s) || s.size() != 1) return false;
    ref = s[0];
    return true;
  }
  template <class T>
  bool read_single(vector<T> &ref) {
    for (auto &d: ref) {
      if (!read_single(d)) return false;
    }
    return true;
  }
  template <class T, class U>
  bool read_single(pair<T, U> &p) {
    return (read_single(p.first) && read_single(p.second));
  }
  template <size_t N = 0, typename T>
  void read_single_tuple(T &t) {
    if constexpr (N < std::tuple_size<T>::value) {
      auto &x = std::get<N>(t);
      read_single(x);
      read_single_tuple<N + 1>(t);
    }
  }
  template <class... T>
  bool read_single(tuple<T...> &tpl) {
    read_single_tuple(tpl);
    return true;
  }
  void read() {}
  template <class H, class... T>
  void read(H &h, T &... t) {
    bool f = read_single(h);
    assert(f);
    read(t...);
  }
  Scanner(FILE *fp) : fp(fp) {}
};

struct Printer {
  Printer(FILE *_fp) : fp(_fp) {}
  ~Printer() { flush(); }

  static constexpr size_t SIZE = 1 << 15;
  FILE *fp;
  char line[SIZE], small[50];
  size_t pos = 0;
  void flush() {
    fwrite(line, 1, pos, fp);
    pos = 0;
  }
  void write(const char val) {
    if (pos == SIZE) flush();
    line[pos++] = val;
  }
  template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  void write(T val) {
    if (pos > (1 << 15) - 50) flush();
    if (val == 0) {
      write('0');
      return;
    }
    if (val < 0) {
      write('-');
      val = -val; // todo min
    }
    size_t len = 0;
    while (val) {
      small[len++] = char(0x30 | (val % 10));
      val /= 10;
    }
    for (size_t i = 0; i < len; i++) { line[pos + i] = small[len - 1 - i]; }
    pos += len;
  }
  void write(const string s) {
    for (char c: s) write(c);
  }
  void write(const char *s) {
    size_t len = strlen(s);
    for (size_t i = 0; i < len; i++) write(s[i]);
  }
  void write(const double x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << x;
    string s = oss.str();
    write(s);
  }
  void write(const long double x) {
    ostringstream oss;
    oss << fixed << setprecision(15) << x;
    string s = oss.str();
    write(s);
  }
  template <typename T,
            typename enable_if<has_write<T>::value>::type * = nullptr>
  inline void write(T x) {
    x.write();
  }
  template <class T>
  void write(const vector<T> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
      if (i) write(' ');
      write(val[i]);
    }
  }
  template <class T, class U>
  void write(const pair<T, U> val) {
    write(val.first);
    write(' ');
    write(val.second);
  }
  template <size_t N = 0, typename T>
  void write_tuple(const T t) {
    if constexpr (N < std::tuple_size<T>::value) {
      if constexpr (N > 0) { write(' '); }
      const auto x = std::get<N>(t);
      write(x);
      write_tuple<N + 1>(t);
    }
  }
  template <class... T>
  bool write(tuple<T...> tpl) {
    write_tuple(tpl);
    return true;
  }
  template <class T, size_t S>
  void write(const array<T, S> val) {
    auto n = val.size();
    for (size_t i = 0; i < n; i++) {
      if (i) write(' ');
      write(val[i]);
    }
  }
  void write(i128 val) {
    string s;
    bool negative = 0;
    if (val < 0) {
      negative = 1;
      val = -val;
    }
    while (val) {
      s += '0' + int(val % 10);
      val /= 10;
    }
    if (negative) s += "-";
    reverse(all(s));
    if (len(s) == 0) s = "0";
    write(s);
  }
};
Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);
void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  printer.write(head);
  if (sizeof...(Tail)) printer.write(' ');
  print(forward<Tail>(tail)...);
}

void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &... tail) {
  scanner.read(head);
  read(tail...);
}
} // namespace fastio
using fastio::print;
using fastio::flush;
using fastio::read;

#define INT(...)   \
  int __VA_ARGS__; \
  read(__VA_ARGS__)
#define LL(...)   \
  ll __VA_ARGS__; \
  read(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  read(__VA_ARGS__)
#define CHAR(...)   \
  char __VA_ARGS__; \
  read(__VA_ARGS__)
#define DBL(...)      \
  double __VA_ARGS__; \
  read(__VA_ARGS__)

#define VEC(type, name, size) \
  vector<type> name(size);    \
  read(name)
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  read(name)

void YES(bool t = 1) { print(t ? "YES" : "NO"); }
void NO(bool t = 1) { YES(!t); }
void Yes(bool t = 1) { print(t ? "Yes" : "No"); }
void No(bool t = 1) { Yes(!t); }
void yes(bool t = 1) { print(t ? "yes" : "no"); }
void no(bool t = 1) { yes(!t); }
#line 1 "library/ds/intervals.hpp"
// https://codeforces.com/contest/1638/problem/E
// https://codeforces.com/contest/897/problem/E
// 持つ値のタイプ T、座標タイプ X
// コンストラクタでは T none_val を指定する
template <typename T = ll, typename X = ll>
struct Intervals {
  static constexpr X LLIM = numeric_limits<X>::lowest();
  static constexpr X RLIM = numeric_limits<X>::max();
  const T none_val;
  // none_val でない区間の個数と長さ合計
  int total_num;
  X total_len;
  map<X, T> dat;

  Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) {
    dat[LLIM] = none_val;
    dat[RLIM] = none_val;
  }

  tuple<X, X, T> get(X x) {
    auto it = dat.upper_bound(x);
    X r = (*it).fi;
    auto [l, t] = *prev(it);
    return {l, r, t};
  }

  template <typename ADD, typename RM>
  void set(X L, X R, T t, ADD& add_f, RM& rm_f) {
    if (L == R) return;
    assert(L < R);
    // 区間 [l, r) を t に変更する
    // まずは、重なるか隣り合う区間を全列挙
    vc<tuple<X, X, T>> tmp;
    auto it = prev(dat.lower_bound(L));
    while (1) {
      auto [l, t] = *it;
      if (R < l) break;
      it = next(it);
      X r = (*it).fi;
      tmp.eb(l, r, t);
    }
    auto [lx, _, lt] = tmp[0];
    auto [__, rx, rt] = tmp.back();
    // とりあえず全部削除
    for (auto&& [l, r, t]: tmp) {
      dat.erase(l);
      if (t == none_val) continue;
      total_num--;
      total_len -= r - l;
      rm_f(l, r, t);
    }
    if (lt == t) chmin(L, lx);
    if (rt == t) chmax(R, rx);
    if (lx < L) {
      // [lx, L)
      dat[lx] = lt;
      if (lt != none_val) {
        total_num++;
        total_len += L - lx;
        add_f(lx, L, lt);
      }
    }
    if (R < rx) {
      // [R, rx)
      dat[R] = rt;
      if (rt != none_val) {
        total_num++;
        total_len += rx - R;
        add_f(R, rx, rt);
      }
    }
    // [L, R)
    dat[L] = t;
    if (t != none_val) {
      total_num++;
      total_len += R - L;
      add_f(L, R, t);
    }
  }

  void set(X L, X R, T t = 1) {
    auto f = [&](X L, X R, T t) -> void {};
    set(L, R, t, f, f);
  }

  void erase(X L, X R) {
    auto f = [&](X L, X R, T t) -> void {};
    set(L, R, none_val, f, f);
  }

  // L, R 内のデータ (l, r, t) を全部取得する
  vc<tuple<X, X, T>> get(X L, X R) {
    vc<tuple<X, X, T>> res;
    auto it = dat.lower_bound(L);
    if(it != dat.begin()) it = prev(it);
    while (1) {
      auto [l, t] = *it;
      if (R <= l) break;
      it = next(it);
      X r = (*it).fi;
      X l0 = max(l, L);
      X r0 = min(r, R);
      if (l0 < r0) res.eb(l0, r0, t);
    }
    return res;
  }

  vc<tuple<X, X, T>> get_all() {
    return get(LLIM, RLIM);
  }

  void debug() {
    auto it = dat.begin();
    print("Intervals");
    print("total_num", total_num);
    print("total_len", total_len);
    while (1) {
      auto [l, t] = *it;
      ++it;
      if (it == dat.end()) break;
      X r = (*it).fi;
      print("l, r, t", l, r, t);
    }
  }
};


#line 1 "library/ds/fastset.hpp"
/* 64分木。
insert, erase
[]での存在判定
next, prev
*/
struct FastSet {
  using uint = unsigned;
  using ull = unsigned long long;

  int bsr(ull x) { return 63 - __builtin_clzll(x); }
  int bsf(ull x) { return __builtin_ctzll(x); }

  static constexpr uint B = 64;
  int n, lg;
  vector<vector<ull>> seg;
  FastSet(int _n) : n(_n) {
    do {
      seg.push_back(vector<ull>((_n + B - 1) / B));
      _n = (_n + B - 1) / B;
    } while (_n > 1);
    lg = int(seg.size());
  }
  bool operator[](int i) const { return (seg[0][i / B] >> (i % B) & 1) != 0; }
  void insert(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] |= 1ULL << (i % B);
      i /= B;
    }
  }
  void erase(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] &= ~(1ULL << (i % B));
      if (seg[h][i / B]) break;
      i /= B;
    }
  }

  // x以上最小の要素を返す。存在しなければ n。
  int next(int i) {
    chmax(i, 0);
    if (i >= n) return n;
    for (int h = 0; h < lg; h++) {
      if (i / B == seg[h].size()) break;
      ull d = seg[h][i / B] >> (i % B);
      if (!d) {
        i = i / B + 1;
        continue;
      }
      // find
      i += bsf(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsf(seg[g][i / B]);
      }
      return i;
    }
    return n;
  }

  // x以下最大の要素を返す。存在しなければ -1。
  int prev(int i) {
    if (i < 0) return -1;
    if (i >= n) i = n - 1;
    for (int h = 0; h < lg; h++) {
      if (i == -1) break;
      ull d = seg[h][i / B] << (63 - i % 64);
      if (!d) {
        i = i / B - 1;
        continue;
      }
      // find
      i += bsr(d) - (B - 1);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsr(seg[g][i / B]);
      }
      return i;
    }
    return -1;
  }

  // [l, r) 内の要素を全部集める
  vector<int> collect(int l, int r) {
    vector<int> res;
    int x = l - 1;
    while (1) {
      x = next(x + 1);
      if (x >= r) break;
      res.emplace_back(x);
    }
    return res;
  }

  void debug() {
    string s;
    for (int i = 0; i < n; ++i) s += ((*this)[i] ? '1' : '0');
    print(s);
  }
};
#line 129 "library/ds/intervals.hpp"

// FastSet で高速化したもの
template <typename T>
struct Intervals_Fast {
  const int LLIM, RLIM;
  const T none_val;
  // none_val でない区間の個数と長さ合計
  int total_num;
  int total_len;
  vc<T> dat;
  FastSet ss;

  Intervals_Fast(int N, T none_val)
      : LLIM(0),
        RLIM(N),
        none_val(none_val),
        total_num(0),
        total_len(0),
        dat(N, none_val),
        ss(N + 1) {
    ss.insert(0);
    ss.insert(N);
  }

  tuple<int, int, T> get(int x) {
    auto l = ss.prev(x);
    auto r = ss.next(x + 1);
    return {l, r, dat[l]};
  }

  template <typename ADD, typename RM>
  void set(int L, int R, T t, ADD& add_f, RM& rm_f) {
    assert(LLIM <= L && L <= R && R <= RLIM);
    if (L == R) return;
    assert(L < R);
    // 区間 [l, r) を t に変更する
    // まずは、重なるか隣り合う区間を全列挙
    vc<tuple<int, int, T>> tmp;
    auto l = ss.prev(L);
    while (l < R) {
      auto r = ss.next(l + 1);
      auto t = dat[l];
      tmp.eb(l, r, t);
      l = r;
    }
    auto [lx, _, lt] = tmp[0];
    auto [__, rx, rt] = tmp.back();
    // とりあえず全部削除
    for (auto&& [l, r, t]: tmp) {
      ss.erase(l);
      if (t == none_val) continue;
      total_num--;
      total_len -= r - l;
      rm_f(l, r, t);
    }
    if (lt == t) chmin(L, lx);
    if (rt == t) chmax(R, rx);
    if (lx < L) {
      // [lx, L)
      ss.insert(lx);
      dat[lx] = lt;
      if (lt != none_val) {
        total_num++;
        total_len += L - lx;
        add_f(lx, L, lt);
      }
    }
    if (R < rx) {
      // [R, rx)
      ss.insert(R);
      dat[R] = rt;
      if (rt != none_val) {
        total_num++;
        total_len += rx - R;
        add_f(R, rx, rt);
      }
    }
    // [L, R)
    ss.insert(L);
    dat[L] = t;
    if (t != none_val) {
      total_num++;
      total_len += R - L;
      add_f(L, R, t);
    }
  }

  void set(int L, int R, T t) {
    auto f = [&](int L, int R, T t) -> void {};
    set(L, R, t, f, f);
  }

  void erase(int L, int R) {
    auto f = [&](int L, int R, T t) -> void {};
    set(L, R, none_val, f, f);
  }

  // L, R 内のデータ (l, r, t) を全部取得する
  vc<tuple<int, int, T>> get(int L, int R) {
    assert(LLIM <= L && L <= R && R <= RLIM);
    vc<tuple<int, int, T>> res;
    auto l = ss.prev(L);
    while (l < R) {
      auto t = dat[l];
      auto r = ss.next(l + 1);
      int l0 = max(l, L);
      int r0 = min(r, R);
      if (l0 < r0) res.eb(l0, r0, t);
      l = r;
    }
    return res;
  }

  vc<tuple<int, int, T>> get_all() { return get(LLIM, RLIM); }

  void debug() {
    print("Intervals");
    print("total_num", total_num);
    print("total_len", total_len);
    int l = 0;
    while (l < RLIM) {
      auto t = dat[l];
      auto r = ss.next(l + 1);
      print("l, r, t", l, r, t);
      l = r;
    }
  }
};
#line 4 "main.cpp"

using Re = long double;

vc<pi> shrink(vc<pi> LR) {
  Intervals<int, int> I(-1);
  for (auto&& [a, b]: LR) { I.set(a, b, 1); }
  vc<pi> res;
  for (auto&& [a, b, t]: I.get_all()) {
    if (t != -1) res.eb(a, b);
  }
  return res;
}

void solve_dd(vi X, vi Y) {
  // 離散・離散
  UNIQUE(X);
  UNIQUE(Y);
  ll sm = 0;
  ll cnt = 0;
  Re ANS = 0;
  FOR(2) {
    swap(X, Y);
    int p = 0;
    for (auto&& y: Y) {
      while (p < len(X) && X[p] < y) {
        sm += X[p++];
        ++cnt;
      }
      ANS += cnt * y - sm;
    }
  }
  print(ANS / (len(X) * len(Y)));
};

void solve_cd(vc<pi> AB, vi C) {
  AB = shrink(AB);
  UNIQUE(C);

  // 連続・離散
  Re ANS = 0;

  FOR(2) {
    // 区間の方が右側
    for (auto&& [a, b]: AB) tie(a, b) = mp(-b, -a);
    for (auto&& x: C) x = -x;
    sort(all(C));
    vi X;
    for (auto&& [a, b]: AB) X.eb(a), X.eb(b);
    for (auto&& x: C) X.eb(x);
    UNIQUE(X);
    vi dp(len(X));
    for (auto&& [a, b]: AB) {
      dp[LB(X, a)]++;
      dp[LB(X, b)]--;
    }
    dp = cumsum<ll>(dp, 0);
    ll cnt = 0, sm = 0;
    int p = 0;
    FOR(i, len(X) - 1) {
      while (p < len(C) && C[p] <= X[i]) {
        ++cnt;
        sm += C[p++];
      }
      Re lx = X[i], rx = X[i + 1];
      Re mx = (lx + rx) / 2;
      if (dp[i]) ANS += (mx * cnt - sm) * (rx - lx);
    }
  }
  ll w = 0;
  for (auto&& [a, b]: AB) w += b - a;
  ANS /= w * len(C);
  print(ANS);
}

void solve_cc(vc<pi> AB, vc<pi> CD) {
  // 連続・連続
  AB = shrink(AB);
  CD = shrink(CD);
  ll LEN1 = 0, LEN2 = 0;
  for (auto&& [x, y]: AB) LEN1 += y - x;
  for (auto&& [x, y]: CD) LEN2 += y - x;
  vi X;
  for (auto&& [a, b]: AB) { X.eb(a), X.eb(b); }
  for (auto&& [a, b]: CD) { X.eb(a), X.eb(b); }
  UNIQUE(X);
  for (auto&& [a, b]: AB) { a = LB(X, a), b = LB(X, b); }
  for (auto&& [a, b]: CD) { a = LB(X, a), b = LB(X, b); }
  ll N = len(X);
  vi A(N), B(N);
  for (auto&& [a, b]: AB) { FOR(i, a, b) A[i]++; }
  for (auto&& [a, b]: CD) { FOR(i, a, b) B[i]++; }
  vc<Re> dpc1(N), dps1(N), dpc2(N), dps2(N);
  FOR(i, N - 1) {
    Re a = X[i], b = X[i + 1];
    if (A[i]) {
      dpc1[i] += b - a;
      dps1[i] += (a + b) * 0.5 * (b - a);
    }
    if (B[i]) {
      dpc2[i] += b - a;
      dps2[i] += (a + b) * 0.5 * (b - a);
    }
  }

  Re ANS = 0;

  FOR(i, N - 1) {
    Re a = X[i], b = X[i + 1];
    if (A[i] && B[i]) ANS += (b - a) * (b - a) * (b - a) / 3;
  }

  {
    /*
    FOR(i, N - 1) FOR(j, i) {
      Re a = X[i], b = X[i + 1];
      if (A[i]) ANS += (b - a) * (dpc2[j] * (a + b) / 2 - dps2[j]);
    }
    */
    dpc2 = cumsum<Re>(dpc2);
    dps2 = cumsum<Re>(dps2);
    FOR(i, N - 1) if (A[i]) {
      Re a = X[i], b = X[i + 1];
      ANS += (b - a) * (dpc2[i] * (a + b) / 2 - dps2[i]);
    }
  }
  {
    dpc1 = cumsum<Re>(dpc1);
    dps1 = cumsum<Re>(dps1);
    FOR(i, N - 1) if (B[i]) {
      Re a = X[i], b = X[i + 1];
      ANS += (b - a) * (dpc1[i] * (a + b) / 2 - dps1[i]);
    }
  }

  print(ANS / LEN1 / LEN2);
};

void solve() {
  LL(N, M);
  VEC(pi, AB, N);
  VEC(pi, CD, M);
  ll X = 0, Y = 0;
  for (auto&& [a, b]: AB) X += b - a;
  for (auto&& [c, d]: CD) Y += d - c;
  if (X == 0) {
    swap(X, Y);
    swap(AB, CD);
  }
  if (X == 0) {
    assert(Y == 0);
    vi A, B;
    for (auto&& [a, b]: AB) A.eb(a);
    for (auto&& [a, b]: CD) B.eb(a);
    return solve_dd(A, B);
  }
  if (Y == 0) {
    vi A;
    for (auto&& [a, b]: CD) A.eb(a);
    return solve_cd(AB, A);
  }
  solve_cc(AB, CD);
}

signed main() {
  solve();
  return 0;
}