#include <bits/stdc++.h>
#include <cmath>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <iostream>
#include <stdexcept>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

// lib/quo.hpp
#ifndef QUO_H
#define QUO_H

/*
a == tools:quo(a, b) * b + tools::mod(a, b)
0 <= tools::mod(a, b) < std::abs(b)
*/

namespace tools {
  template <typename T>
  constexpr T quo(const T lhs, const T rhs) {
    return lhs > 0 ? lhs / rhs : rhs > 0 ? -((-lhs - 1 + rhs) / rhs) : (-lhs - 1 + -rhs) / -rhs;
  }
}

#endif

// lib/optional.hpp
#ifndef OPTIONAL_HPP
#define OPTIONAL_HPP


namespace tools {
  template <typename T>
  class optional {
  private:
    bool m_has_value;
    T m_value;

  public:
    optional() :
      m_has_value(false),
      m_value() {
    }

    optional(const T& other) :
      m_has_value(true),
      m_value(other) {
    }

    optional<T>& operator=(const T& other) {
      this->m_has_value = true;
      this->m_value = other;
    }

    ~optional() {
      this->m_value.~T();
    }

    T& operator*() {
      return this->value();
    }
    const T& operator*() const {
      return this->value();
    }

    explicit operator bool() const {
      return this->has_value();
    }

    void reset() {
      this->m_has_value = false;
    }

    bool has_value() const {
      return this->m_has_value;
    }

    T& value() {
      if (!this->m_has_value) throw std::range_error("Optional has no valid value.");
      return this->m_value;
    }
    const T& value() const {
      if (!this->m_has_value) throw std::range_error("Optional has no valid value.");
      return this->m_value;
    }

    T value_or(const T& default_value) const {
      return this->m_has_value ? this->m_value : default_value;
    }
  };
}

#endif

// lib/to_signed.hpp
#ifndef TO_SIGNED_HPP
#define TO_SIGNED_HPP


/*
usage:

std::uint_fast64_t i;
decltype(tools::to_signed(i)) // => std::int_fast64_t
*/

namespace tools {
  template <typename T>
  constexpr typename std::make_signed<T>::type to_signed(const T x) noexcept {
    return x;
  }
}

#endif

// lib/signum.hpp
#ifndef SIGNUM_HPP
#define SIGNUM_HPP


/*
usage:

tools::signum(-5) // => -1
*/

namespace tools {
  template <typename T>
  constexpr int signum(const T x, const std::false_type) noexcept {
    return T(0) < x;
  }

  template <typename T>
  constexpr int signum(const T x, const std::true_type) noexcept {
    return (T(0) < x) - (x < T(0));
  }

  template <typename T>
  constexpr int signum(const T x) noexcept {
    return signum(x, std::is_signed<T>());
  }
}

#endif

// lib/variant.hpp
#ifndef VARIANT_HPP
#define VARIANT_HPP


// Source: https://qiita.com/ktokhrtk/items/9774208863f249007462
// Author: ktokhrtk ( https://qiita.com/ktokhrtk )
namespace tools {
  namespace detail {
    namespace variant {
      template <class...>
      struct variant_storage;

      template <class A, class... B>
      struct variant_storage<A, B...> : variant_storage<B...> {
        using base_t = variant_storage<B...>;
        static constexpr std::size_t size = sizeof(A) > base_t::size ? sizeof(A) : base_t::size;
        static constexpr std::size_t align = alignof(A) > base_t::align ? alignof(A) : base_t::align;
      };

      template <class Z>
      struct variant_storage<Z> {
        static constexpr std::size_t size = sizeof(Z);
        static constexpr std::size_t align = alignof(Z);
      };

      template <class... Types>
      using storage_t = typename std::aligned_storage<variant_storage<Types...>::size, variant_storage<Types...>::align>::type;

      template <class...>
      struct variant_typeid;

      template <class A, class... B>
      struct variant_typeid<A, B...> : variant_typeid<B...> {
        using base_t = variant_typeid<B...>;
        static constexpr std::size_t id = base_t::id + 1;

        template <class T, typename std::enable_if<std::is_same<A, typename std::decay<T>::type>::value, std::nullptr_t>::type = nullptr>
        static std::size_t assign(void* p, T&& t) {
          ::new(p) A(std::forward<T>(t));
          return id;
        }

        using base_t::assign;
      };

      template <class Z>
      struct variant_typeid<Z> {
        static constexpr std::size_t id = 1;

        template <class T, typename std::enable_if<std::is_same<Z, typename std::decay<T>::type>::value, std::nullptr_t>::type = nullptr>
        static std::size_t assign(void* p, T&& t) {
          ::new(p) Z(std::forward<T>(t));
          return id;
        }
      };

      template <class F, class T, class R>
      auto declfunc() -> R (*)(void*, F&&) {
        return [](void* p, F&& f) {
          return std::forward<F>(f)(*static_cast<T*>(p));
        };
      }

      template <class F, class T, class R>
      auto const_declfunc() -> R (*)(const void*, F&&) {
        return [](const void* p, F&& f) {
          return std::forward<F>(f)(*static_cast<const T*>(p));
        };
      }

      template <class...>
      struct contains;

      template <class T, class FirstType, class... Types>
      struct contains<T, FirstType, Types...> {
        static constexpr bool value = std::is_same<typename std::decay<T>::type, FirstType>::value || contains<T, Types...>::value;
      };

      template <class T>
      struct contains<T> {
        static constexpr bool value = false;
      };

      template <class FirstType, class... Types>
      struct first {
        using type = FirstType;
      };
    }
  }

  template <class... Types>
  struct variant {
  private:
    detail::variant::storage_t<Types...> m_storage;
    std::size_t m_id;

    struct deleter {
      template <class T>
      void operator()(T& p) {
        p.~T();
      }
    };

  public:
    ~variant() {
      this->visit<void>(deleter());
    }

    variant()
      : variant(detail::variant::first<Types...>::type()) {
    }

    template <
      class T,
      typename std::enable_if<detail::variant::contains<T, Types...>::value, std::nullptr_t>::type = nullptr
    >
    variant(T&& t)
      : m_id(detail::variant::variant_typeid<Types...>::assign(&this->m_storage, std::forward<T>(t))) {
    }

    template <class R, class F>
    R visit(F&& f) {
      static R (*ftbl[])(void*, F&&) = { detail::variant::declfunc<F, Types, R>()... };
      return ftbl[sizeof...(Types) - this->m_id](&this->m_storage, std::forward<F>(f));
    }

    template <class R, class F>
    R visit(F&& f) const {
      static R (*ftbl[])(const void*, F&&) = { detail::variant::const_declfunc<F, Types, R>()... };
      return ftbl[sizeof...(Types) - this->m_id](&this->m_storage, std::forward<F>(f));
    }
  };
}

#endif

// lib/extgcd.hpp
#ifndef EXTGCD_HPP
#define EXTGCD_HPP


/*
usage:

std::tuple<int, int, int> result = tools:extgcd(4, 5);
int gcd = std::get<0>(result);
int x0 = std::get<1>(result);
int y0 = std::get<2>(result);
*/

namespace tools {
  template <typename T>
  std::tuple<T, T, T> extgcd(T prev_r, T r) {
    T prev_s = 1;
    T prev_t = 0;
    T s = 0;
    T t = 1;
    while (r != 0) {
      const T q = quo(prev_r, r);
      const T next_r = prev_r - q * r;
      prev_r = r;
      r = next_r;
      const T next_s = prev_s - q * s;
      prev_s = s;
      s = next_s;
      const T next_t = prev_t - q * t;
      prev_t = t;
      t = next_t;
    }
    return std::make_tuple(prev_r, prev_s, prev_t);
  }
}

#endif

// lib/fraction.hpp
#ifndef FRACTION_HPP
#define FRACTION_HPP


/*
usage:

tools::fraction(5, 2) // => (5/2)
*/

namespace tools {
  class fraction {
  private:
    std::intmax_t m_numerator;
    std::intmax_t m_denominator;

    void reduct() noexcept {
      if (this->m_denominator < 0) {
        this->m_numerator *= -1;
        this->m_denominator *= -1;
      }
      if (this->m_numerator != 0) {
        const std::intmax_t gcd = std::get<0>(tools::extgcd(this->m_numerator, this->m_denominator));
        this->m_numerator /= gcd;
        this->m_denominator /= gcd;
      }
    }

    fraction(const std::intmax_t numerator, const std::intmax_t denominator, bool) noexcept :
      m_numerator(numerator),
      m_denominator(denominator) {
      this->reduct();
    }

  public:
    fraction() noexcept :
      fraction(0, 1, true) {
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    fraction(const T n) noexcept :
      fraction(n, 1, true) {
    }
    template <typename T1, typename T2, typename std::enable_if<std::is_integral<T1>::value && std::is_integral<T2>::value, std::nullptr_t>::type = nullptr>
    fraction(const T1 numerator, const T2 denominator) :
      m_numerator(numerator),
      m_denominator(denominator) {
      if (this->m_denominator == 0) throw std::domain_error("Denominator cannot be zero.");
      this->reduct();
    }

    std::intmax_t numerator() const noexcept {
      return this->m_numerator;
    }

    std::intmax_t denominator() const noexcept {
      return this->m_denominator;
    }

    explicit operator double() const noexcept {
      return static_cast<double>(this->m_numerator) / this->m_denominator;
    }

    fraction operator+() const noexcept {
      return *this;
    }

    fraction operator-() const noexcept {
      return fraction(-this->m_numerator, this->m_denominator, true);
    }

    friend fraction operator+(const fraction& lhs, const fraction& rhs) noexcept {
      return fraction(lhs.m_numerator * rhs.m_denominator + rhs.m_numerator * lhs.m_denominator, lhs.m_denominator * rhs.m_denominator, true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator+(const fraction& lhs, const T rhs) noexcept {
      return fraction(lhs.m_numerator + static_cast<std::intmax_t>(rhs) * lhs.m_denominator, lhs.m_denominator, true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator+(const T lhs, const fraction& rhs) noexcept {
      return fraction(static_cast<std::intmax_t>(lhs) * rhs.m_denominator + rhs.m_numerator, rhs.m_denominator, true);
    }

    friend fraction operator-(const fraction& lhs, const fraction& rhs) noexcept {
      return fraction(lhs.m_numerator * rhs.m_denominator - rhs.m_numerator * lhs.m_denominator, lhs.m_denominator * rhs.m_denominator, true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator-(const fraction& lhs, const T rhs) noexcept {
      return fraction(lhs.m_numerator - static_cast<std::intmax_t>(rhs) * lhs.m_denominator, lhs.m_denominator, true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator-(const T lhs, const fraction& rhs) noexcept {
      return fraction(static_cast<std::intmax_t>(lhs) * rhs.m_denominator - rhs.m_numerator, rhs.m_denominator, true);
    }

    friend fraction operator*(const fraction& lhs, const fraction& rhs) noexcept {
      return fraction(lhs.m_numerator * rhs.m_numerator, lhs.m_denominator * rhs.m_denominator, true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator*(const fraction& lhs, const T rhs) noexcept {
      return fraction(lhs.m_numerator * static_cast<std::intmax_t>(rhs), lhs.m_denominator, true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator*(const T lhs, const fraction& rhs) noexcept {
      return fraction(static_cast<std::intmax_t>(lhs) * rhs.m_numerator, rhs.m_denominator, true);
    }

    friend fraction operator/(const fraction& lhs, const fraction& rhs) {
      if (rhs == 0) throw std::domain_error("Cannot divide by zero.");
      return fraction(lhs.m_numerator * rhs.m_denominator, lhs.m_denominator * rhs.m_numerator, true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator/(const fraction& lhs, const T rhs) {
      if (rhs == 0) throw std::domain_error("Cannot divide by zero.");
      return fraction(lhs.m_numerator, lhs.m_denominator * static_cast<std::intmax_t>(rhs), true);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend fraction operator/(const T lhs, const fraction& rhs) {
      if (rhs == 0) throw std::domain_error("Cannot divide by zero.");
      return fraction(static_cast<std::intmax_t>(lhs) * rhs.m_denominator, rhs.m_numerator, true);
    }

    fraction& operator++() noexcept {
      return *this = *this + 1;
    }
    fraction operator++(int) noexcept {
      const fraction prev = *this;
      ++*this;
      return prev;
    }

    fraction& operator--() noexcept {
      return *this = *this - 1;
    }
    fraction operator--(int) noexcept {
      const fraction prev = *this;
      --*this;
      return prev;
    }

    fraction& operator+=(const fraction& other) noexcept {
      return *this = *this + other;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    fraction& operator+=(const T other) noexcept {
      return *this = *this + other;
    }

    fraction& operator-=(const fraction& other) noexcept {
      return *this = *this - other;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    fraction& operator-=(const T other) noexcept {
      return *this = *this - other;
    }

    fraction& operator*=(const fraction& other) noexcept {
      return *this = *this * other;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    fraction& operator*=(const T other) noexcept {
      return *this = *this * other;
    }

    fraction& operator/=(const fraction& other) {
      return *this = *this / other;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    fraction& operator/=(const T other) {
      return *this = *this / other;
    }

    friend bool operator==(const fraction& lhs, const fraction& rhs) noexcept {
      return lhs.m_numerator == rhs.m_numerator && lhs.m_denominator == rhs.m_denominator;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator==(const fraction& lhs, const T rhs) noexcept {
      return lhs.m_numerator == static_cast<std::intmax_t>(rhs) && lhs.m_denominator == 1;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator==(const T lhs, const fraction& rhs) noexcept {
      return static_cast<std::intmax_t>(lhs) == rhs.m_numerator && 1 == rhs.m_denominator;
    }

    friend bool operator!=(const fraction& lhs, const fraction& rhs) noexcept {
      return !(lhs == rhs);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator!=(const fraction& lhs, const T rhs) noexcept {
      return !(lhs == rhs);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator!=(const T lhs, const fraction& rhs) noexcept {
      return !(lhs == rhs);
    }

    friend bool operator<(const fraction& lhs, const fraction& rhs) noexcept {
      return lhs.m_numerator * rhs.m_denominator < rhs.m_numerator * lhs.m_denominator;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator<(const fraction& lhs, const T rhs) noexcept {
      return lhs.m_numerator < static_cast<std::intmax_t>(rhs) * lhs.m_denominator;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator<(const T lhs, const fraction& rhs) noexcept {
      return static_cast<std::intmax_t>(lhs) * rhs.m_denominator < rhs.m_numerator;
    }

    friend bool operator>(const fraction& lhs, const fraction& rhs) noexcept {
      return rhs < lhs;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator>(const fraction& lhs, const T rhs) noexcept {
      return rhs < lhs;
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator>(const T lhs, const fraction& rhs) noexcept {
      return rhs < lhs;
    }

    friend bool operator<=(const fraction& lhs, const fraction& rhs) noexcept {
      return !(rhs < lhs);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator<=(const fraction& lhs, const T rhs) noexcept {
      return !(rhs < lhs);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator<=(const T lhs, const fraction& rhs) noexcept {
      return !(rhs < lhs);
    }

    friend bool operator>=(const fraction& lhs, const fraction& rhs) noexcept {
      return !(lhs < rhs);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator>=(const fraction& lhs, const T rhs) noexcept {
      return !(lhs < rhs);
    }
    template <typename T, typename std::enable_if<std::is_integral<T>::value, std::nullptr_t>::type = nullptr>
    friend bool operator>=(const T lhs, const fraction& rhs) noexcept {
      return !(lhs < rhs);
    }
  };
}

namespace std {
  string to_string(const tools::fraction& f);
  double sqrt(const tools::fraction& f);
  ostream& operator<<(ostream& os, const tools::fraction& self);

  template <>
  struct hash<tools::fraction> {
    typedef std::size_t result_type;
    typedef tools::fraction argument_type;
    std::size_t operator()(const tools::fraction& key) const {
      static const std::hash<std::intmax_t> hash = std::hash<std::intmax_t>();
      std::size_t result = 17;
      result = 31 * result + hash(key.numerator());
      result = 31 * result + hash(key.denominator());
      return result;
    }
  };
}

#endif

// lib/vector2.hpp
#ifndef VECTOR2_HPP
#define VECTOR2_HPP


/*
usage:

tools::vector2<int>(6, 5) // => (6, 5)
*/

namespace tools {
  template <typename T>
  class vector2 {
  public:
    T x;
    T y;

    vector2() :
      vector2(T(), T()) {
    }

    vector2(const T& x, const T& y) :
      x(x),
      y(y) {
    }

    double norm() const {
      return std::sqrt(this->squaredNorm());
    }

    T squaredNorm() const {
      return this->inner_product(*this);
    }

    template <typename CHECK = T, typename std::enable_if<std::is_same<CHECK, double>::value, std::nullptr_t>::type = nullptr>
    double normalize() const {
      return *this / this->norm();
    }

    vector2<T> operator+() const {
      return *this;
    }

    vector2<T> operator-() const {
      return vector2<T>(-this->x, -this->y);
    }

    friend vector2<T> operator+(const vector2<T>& lhs, const vector2<T>& rhs) {
      return vector2<T>(lhs.x + rhs.x, lhs.y + rhs.y);
    }

    friend vector2<T> operator-(const vector2<T>& lhs, const vector2<T>& rhs) {
      return vector2<T>(lhs.x - rhs.x, lhs.y - rhs.y);
    }

    template <typename T2, typename std::enable_if<!std::is_same<T2, vector2<T>>::value, std::nullptr_t>::type = nullptr>
    friend vector2<T> operator*(const vector2<T>& lhs, const T2& rhs) {
      return vector2<T>(lhs.x * rhs, lhs.y * rhs);
    }
    template <typename T2, typename std::enable_if<!std::is_same<T2, vector2<T>>::value, std::nullptr_t>::type = nullptr>
    friend vector2<T> operator*(const T2& lhs, const vector2<T>& rhs) {
      return vector2<T>(lhs * rhs.x, lhs * rhs.y);
    }

    template <typename T2, typename std::enable_if<!std::is_same<T2, vector2<T>>::value, std::nullptr_t>::type = nullptr>
    friend vector2<T> operator/(const vector2<T>& lhs, const T2& rhs) {
      return vector2<T>(lhs.x / rhs, lhs.y / rhs);
    }

    T inner_product(const vector2<T>& other) const {
      return this->x * other.x + this->y * other.y;
    }

    vector2<T>& operator+=(const vector2<T>& other) {
      return *this = *this + other;
    }

    vector2<T>& operator-=(const vector2<T>& other) {
      return *this = *this - other;
    }

    friend bool operator==(const vector2<T>& lhs, const vector2<T>& rhs) {
      return lhs.x == rhs.x && lhs.y == rhs.y;
    }

    friend bool operator!=(const vector2<T>& lhs, const vector2<T>& rhs) {
      return lhs.x != rhs.x || lhs.y != rhs.y;
    }
  };
}

namespace std {
  template <typename T>
  string to_string(const tools::vector2<T>& f) {
    return '(' + to_string(f.x) + ", " + to_string(f.y) + ')';
  }

  template <typename T>
  struct hash<tools::vector2<T>> {
    typedef std::size_t result_type;
    typedef tools::vector2<T> argument_type;
    std::size_t operator()(const tools::vector2<T>& key) const {
      static const std::hash<T> hash = std::hash<T>();
      std::size_t result = 17;
      result = 31 * result + hash(key.x);
      result = 31 * result + hash(key.y);
      return result;
    }
  };
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const tools::vector2<T>& self) {
  return os << std::to_string(self);
}

#endif

// lib/fraction.cpp

namespace std {
  string to_string(const tools::fraction& f) {
    return '(' + to_string(f.numerator()) + '/' + to_string(f.denominator()) + ')';
  }

  double sqrt(const tools::fraction& f) {
    return sqrt(static_cast<double>(f));
  }

  ostream& operator<<(ostream& os, const tools::fraction& self) {
    return os << to_string(self);
  }
}

// lib/detail/element_2d.hpp
#ifndef DETAIL_ELEMENT_2D_HPP
#define DETAIL_ELEMENT_2D_HPP


namespace tools {
  template <typename T>
  class directed_line_segment_2d;

  template <typename T>
  class half_line_2d;

  template <typename T>
  class line_2d;

  template <typename T>
  class directed_line_segment_2d {
  private:
    vector2<T> m_p1;
    vector2<T> m_p2;

  public:
    directed_line_segment_2d();
    directed_line_segment_2d(const vector2<T>& p1, const vector2<T>& p2);

    const vector2<T>& p1() const;
    const vector2<T>& p2() const;

    vector2<T> to_vector() const;
    half_line_2d<T> to_half_line() const;
    line_2d<T> to_line() const;
    double length() const;
    T squared_length() const;
    vector2<T> midpoint() const;
    bool contains(const vector2<T>& p) const;

    optional<vector2<T>> cross_point(const directed_line_segment_2d<T>& other) const;
    optional<vector2<T>> cross_point(const half_line_2d<T>& other) const;
    optional<vector2<T>> cross_point(const line_2d<T>& other) const;
    std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersection(const directed_line_segment_2d<T>& other) const;
    std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersection(const half_line_2d<T>& other) const;
    std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersection(const line_2d<T>& other) const;

    directed_line_segment_2d<T> operator+() const;
    directed_line_segment_2d<T> operator-() const;
    bool operator==(const directed_line_segment_2d<T>& other) const;
  };
}

namespace tools {
  template <typename T>
  class half_line_2d {
  private:
    vector2<T> m_a;
    vector2<T> m_d;

  public:
    half_line_2d();
    half_line_2d(const vector2<T>& a, const vector2<T>& d);

    const vector2<T>& a() const;
    const vector2<T>& d() const;

    line_2d<T> to_line() const;
    bool contains(const vector2<T>& p) const;

    optional<vector2<T>> cross_point(const directed_line_segment_2d<T>& other) const;
    optional<vector2<T>> cross_point(const half_line_2d<T>& other) const;
    std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersection(const directed_line_segment_2d<T>& other) const;
    std::vector<variant<vector2<T>, directed_line_segment_2d<T>, half_line_2d<T>>> intersection(const half_line_2d<T>& other) const;

    bool operator==(const half_line_2d<T>& other) const;
  };
}

namespace tools {
  template <typename T>
  class line_2d {
  private:
    T m_a;
    T m_b;
    T m_c;

  public:
    line_2d();
    line_2d(const T& a, const T& b, const T& c);

    const T& a() const;
    const T& b() const;
    const T& c() const;

    bool contains(const vector2<T>& p) const;
    bool is_parallel_to(const line_2d<T>& other) const;

    bool crosses(const line_2d<T>& other) const;
    optional<vector2<T>> cross_point(const line_2d<T>& other) const;
    vector2<T> unsafe_cross_point(const line_2d<T>& other) const;
    bool intersects(const line_2d<T>& other) const;
    std::vector<variant<vector2<T>, line_2d<T>>> intersection(const line_2d<T>& other) const;
    std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersection(const directed_line_segment_2d<T>& other) const;

    bool operator==(const line_2d<T>& other) const;

    static line_2d<T> through(const vector2<T>& p1, const vector2<T>& p2);
  };
}

namespace tools {
  template <typename T>
  directed_line_segment_2d<T>::directed_line_segment_2d() :
    directed_line_segment_2d(vector2<T>(), vector2<T>()) {
  }

  template <typename T>
  directed_line_segment_2d<T>::directed_line_segment_2d(const vector2<T>& p1, const vector2<T>& p2) :
    m_p1(p1),
    m_p2(p2) {
    if (p1 == p2) throw std::domain_error("Two ends must differ.");
  }

  template <typename T>
  const vector2<T>& directed_line_segment_2d<T>::p1() const {
    return this->m_p1;
  }

  template <typename T>
  const vector2<T>& directed_line_segment_2d<T>::p2() const {
    return this->m_p2;
  }

  template <typename T>
  vector2<T> directed_line_segment_2d<T>::to_vector() const {
    return this->m_p2 - this->m_p1;
  }

  template <typename T>
  half_line_2d<T> directed_line_segment_2d<T>::to_half_line() const {
    return half_line_2d<T>(this->m_p1, this->m_p2 - this->m_p1);
  }

  template <typename T>
  line_2d<T> directed_line_segment_2d<T>::to_line() const {
    return line_2d<T>::through(this->m_p1, this->m_p2);
  }

  template <typename T>
  double directed_line_segment_2d<T>::length() const {
    return this->to_vector().norm();
  }

  template <typename T>
  T directed_line_segment_2d<T>::squared_length() const {
    return this->to_vector().squared_norm();
  }

  template <typename T>
  vector2<T> directed_line_segment_2d<T>::midpoint() const {
    return (this->m_p1 + this->m_p2) / 2;
  }

  template <typename T>
  bool directed_line_segment_2d<T>::contains(const vector2<T>& p) const {
    if (p == this->m_p1 || p == this->m_p2) return true;
    const line_2d<T> l = this->to_line();
    if (!l.contains(p)) return false;
    const T d = (p - this->m_p1).inner_product(this->to_vector());
    return 0 <= d && d <= this->squared_length();
  }

  template <typename T>
  optional<vector2<T>> directed_line_segment_2d<T>::cross_point(const directed_line_segment_2d<T>& other) const {
    const std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersections = this->intersection(other);
    struct {
      optional<vector2<T>> operator()(const vector2<T>& v) {
        return optional<vector2<T>>(v);
      }
      optional<vector2<T>> operator()(const directed_line_segment_2d<T>&) {
        return optional<vector2<T>>();
      }
    } visitor;
    return intersections.size() == 1 ? intersections.front().template visit<optional<vector2<T>>>(visitor) : optional<vector2<T>>();
  }

  template <typename T>
  optional<vector2<T>> directed_line_segment_2d<T>::cross_point(const half_line_2d<T>& other) const {
    const std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersections = this->intersection(other);
    struct {
      optional<vector2<T>> operator()(const vector2<T>& v) {
        return optional<vector2<T>>(v);
      }
      optional<vector2<T>> operator()(const directed_line_segment_2d<T>&) {
        return optional<vector2<T>>();
      }
    } visitor;
    return intersections.size() == 1 ? intersections.front().template visit<optional<vector2<T>>>(visitor) : optional<vector2<T>>();
  }

  template <typename T>
  optional<vector2<T>> directed_line_segment_2d<T>::cross_point(const line_2d<T>& other) const {
    const std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> intersections = this->intersection(other);
    struct {
      optional<vector2<T>> operator()(const vector2<T>& v) {
        return optional<vector2<T>>(v);
      }
      optional<vector2<T>> operator()(const directed_line_segment_2d<T>&) {
        return optional<vector2<T>>();
      }
    } visitor;
    return intersections.size() == 1 ? intersections.front().template visit<optional<vector2<T>>>(visitor) : optional<vector2<T>>();
  }

  template <typename T>
  std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> directed_line_segment_2d<T>::intersection(const directed_line_segment_2d<T>& other) const {
    typedef std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> result_t;
    const line_2d<T> l1 = this->to_line();
    const line_2d<T> l2 = other.to_line();
    if (l1 == l2) {
      const vector2<T> base = this->to_vector();
      const directed_line_segment_2d<T> fixed_other = base.inner_product(other.to_vector()) > 0 ? other : -other;
      const T d1 = 0;
      const T d2 = base.inner_product(base);
      const T d3 = base.inner_product(fixed_other.m_p1 - this->m_p1);
      const T d4 = base.inner_product(fixed_other.m_p2 - this->m_p2);
      if (d1 == d4) return result_t({this->m_p1});
      if (d2 == d3) return result_t({this->m_p2});
      if (d3 <= d1 && d2 <= d4) return result_t({*this});
      if (d1 <= d3 && d4 <= d2) return result_t({fixed_other});
      if (d3 <= d1 && d1 <= d4 && d4 <= d2) return result_t({directed_line_segment_2d<T>(this->m_p1, fixed_other.m_p2)});
      if (d1 <= d3 && d3 <= d2 && d2 <= d4) return result_t({directed_line_segment_2d<T>(fixed_other.m_p1, this->m_p2)});
      return result_t();
    }
    if (l1.is_parallel_to(l2)) return result_t();
    if (this->m_p1 == other.m_p1 || this->m_p1 == other.m_p2) return result_t({this->m_p1});
    if (this->m_p2 == other.m_p1 || this->m_p2 == other.m_p2) return result_t({this->m_p2});
    if (((other.m_p1.y - this->m_p1.y) * (this->m_p2.x - this->m_p1.x) - (this->m_p2.y - this->m_p1.y) * (other.m_p1.x - this->m_p1.x)) *
        ((other.m_p2.y - this->m_p1.y) * (this->m_p2.x - this->m_p1.x) - (this->m_p2.y - this->m_p1.y) * (other.m_p2.x - this->m_p1.x)) > 0 ||
        ((this->m_p1.y - other.m_p1.y) * (other.m_p2.x - other.m_p1.x) - (other.m_p2.y - other.m_p1.y) * (this->m_p1.x - other.m_p1.x)) *
        ((this->m_p2.y - other.m_p1.y) * (other.m_p2.x - other.m_p1.x) - (other.m_p2.y - other.m_p1.y) * (this->m_p2.x - other.m_p1.x)) > 0) return result_t();
    return result_t(l1.unsafe_cross_point(l2));
  }

  template <typename T>
  std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> directed_line_segment_2d<T>::intersection(const half_line_2d<T>& other) const {
    typedef std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> result_t;
    const line_2d<T> l1 = this->to_line();
    const line_2d<T> l2 = other.to_line();
    if (l1 == l2) {
      const bool has_same_direction = other.d().inner_product(this->to_vector()) > 0;
      const T d1 = other.d().inner_product(this->m_p1 - other.a());
      const T d2 = other.d().inner_product(this->m_p2 - other.a());
      if (has_same_direction) {
        if (d2 < 0) return result_t();
        if (d2 == 0) return result_t({other.a()});
        if (d1 < 0) return result_t({directed_line_segment_2d<T>(other.a(), this->m_p2)});
        return result_t({*this});
      } else {
        if (d1 > 0) return result_t();
        if (d1 == 0) return result_t({other.a()});
        if (d2 > 0) return result_t({directed_line_segment_2d<T>(this->m_p1, other.a())});
        return result_t({*this});
      }
    }
    if (other.contains(this->m_p1)) return result_t({this->m_p1});
    if (other.contains(this->m_p2)) return result_t({this->m_p2});
    if ((l2.a() * this->m_p1.x + l2.b() * this->m_p1.y + l2.c()) * (l2.a() * this->m_p2.x + l2.b() * this->m_p2.y + l2.c()) > 0) return result_t();
    const vector2<T> possible_cross_point = l1.unsafe_cross_point(l2);
    if (other.d().inner_product(possible_cross_point - other.a()) < 0) return result_t();
    return result_t({possible_cross_point});
  }

  template <typename T>
  std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> directed_line_segment_2d<T>::intersection(const line_2d<T>& other) const {
    typedef std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> result_t;
    const line_2d<T> this_line = this->to_line();
    if (this_line == other) return result_t({*this});
    if (other.contains(this->m_p1)) return result_t({this->m_p1});
    if (other.contains(this->m_p2)) return result_t({this->m_p2});
    if ((other.a() * this->m_p1.x + other.b() * this->m_p1.y + other.c()) * (other.a() * this->m_p2.x + other.b() * this->m_p2.y + other.c()) > 0) return result_t();
    return result_t(this_line.unsafe_cross_point(other));
  }

  template <typename T>
  directed_line_segment_2d<T> directed_line_segment_2d<T>::operator+() const {
    return *this;
  }

  template <typename T>
  directed_line_segment_2d<T> directed_line_segment_2d<T>::operator-() const {
    return directed_line_segment_2d(this->m_p2, this->m_p1);
  }

  template <typename T>
  bool directed_line_segment_2d<T>::operator==(const tools::directed_line_segment_2d<T>& other) const {
    return this->p1() == other.p1() && this->p2() == other.p2();
  }
}

namespace tools {
  template <typename T>
  half_line_2d<T>::half_line_2d() :
    half_line_2d(vector2<T>(0, 0), vector2<T>(1, 0)) {
  }

  template <typename T>
  half_line_2d<T>::half_line_2d(const vector2<T>& a, const vector2<T>& d) :
    m_a(a),
    m_d(d) {
    if (d == vector2<T>(0, 0)) throw std::domain_error("d cannot be zero vector.");
  }

  template <typename T>
  const vector2<T>& half_line_2d<T>::a() const {
    return this->m_a;
  }

  template <typename T>
  const vector2<T>& half_line_2d<T>::d() const {
    return this->m_d;
  }

  template <typename T>
  line_2d<T> half_line_2d<T>::to_line() const {
    return line_2d<T>::through(this->m_a, this->m_a + this->m_d);
  }

  template <typename T>
  bool half_line_2d<T>::contains(const vector2<T>& p) const {
    const line_2d<T> l = this->to_line();
    return l.a() * p.x + l.b() * p.y + l.c() == 0 && this->m_d.inner_product(p - this->m_a) >= 0;
  }

  template <typename T>
  optional<vector2<T>> half_line_2d<T>::cross_point(const directed_line_segment_2d<T>& other) const {
    return other.cross_point(*this);
  }

  template <typename T>
  optional<vector2<T>> half_line_2d<T>::cross_point(const half_line_2d<T>& other) const {
    const std::vector<variant<vector2<T>, directed_line_segment_2d<T>, half_line_2d<T>>> intersections = this->intersection(other);
    struct {
      optional<vector2<T>> operator()(const vector2<T>& v) {
        return optional<vector2<T>>(v);
      }
      optional<vector2<T>> operator()(const directed_line_segment_2d<T>&) {
        return optional<vector2<T>>();
      }
      optional<vector2<T>> operator()(const half_line_2d<T>&) {
        return optional<vector2<T>>();
      }
    } visitor;
    return intersections.size() == 1 ? intersections.front().template visit<optional<vector2<T>>>(visitor) : optional<vector2<T>>();
  }

  template <typename T>
  std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> half_line_2d<T>::intersection(const directed_line_segment_2d<T>& other) const {
    return other.intersection(*this);
  }

  template <typename T>
  std::vector<variant<vector2<T>, directed_line_segment_2d<T>, half_line_2d<T>>> half_line_2d<T>::intersection(const half_line_2d<T>& other) const {
    typedef std::vector<variant<vector2<T>, directed_line_segment_2d<T>, half_line_2d<T>>> result_t;
    const line_2d<T> l1 = this->to_line();
    const line_2d<T> l2 = other.to_line();
    if (l1 == l2) {
      if (this->d().inner_product(other.d()) > 0) {
        switch (tools::signum(this->d().inner_product(other.a() - this->a()))) {
        case 1:
        case 0:
          return result_t({other});
        case -1:
          return result_t({*this});
        default:
          throw std::runtime_error("Cannot happen.");
        }
      } else {
        switch (tools::signum(this->d().inner_product(other.a() - this->a()))) {
        case 1:
          return result_t({directed_line_segment_2d<T>(this->a(), other.a())});
        case 0:
          return result_t({this->a()});
        case -1:
          return result_t();
        default:
          throw std::runtime_error("Cannot happen.");
        }
      }
    } else if (l1.is_parallel_to(l2)) {
      return result_t();
    } else {
      const vector2<T> possible_cross_point = l1.unsafe_cross_point(l2);
      if (this->d().inner_product(possible_cross_point - this->a()) < 0 || other.d().inner_product(possible_cross_point - other.a()) < 0) {
        return result_t();
      }
      return result_t({possible_cross_point});
    }
  }

  template <typename T>
  bool half_line_2d<T>::operator==(const tools::half_line_2d<T>& other) const {
    return this->a() == other.a() && this->d().x * other.d().y == other.d().x * this->d().y;
  }
}

namespace tools {
  template <typename T>
  line_2d<T>::line_2d() :
    line_2d(T(0), T(1), T(0)) {
  }

  template <typename T>
  line_2d<T>::line_2d(const T& a, const T& b, const T& c) :
    m_a(a),
    m_b(b),
    m_c(c) {
  }

  template <typename T>
  const T& line_2d<T>::a() const {
    return this->m_a;
  }

  template <typename T>
  const T& line_2d<T>::b() const {
    return this->m_b;
  }

  template <typename T>
  const T& line_2d<T>::c() const {
    return this->m_c;
  }

  template <typename T>
  bool line_2d<T>::contains(const vector2<T>& p) const {
    return this->m_a * p.x + this->m_b * p.y + this->m_c == 0;
  }

  template <typename T>
  bool line_2d<T>::is_parallel_to(const line_2d<T>& other) const {
    return this->a() * other.b() == this->b() * other.a() && (this->b() * other.c() != this->c() * other.b() || this->c() * other.a() != this->a() * other.c());
  }

  template <typename T>
  bool line_2d<T>::crosses(const line_2d<T>& other) const {
    return this->a() * other.b() - other.a() * this->b() != 0;
  }

  template <typename T>
  optional<vector2<T>> line_2d<T>::cross_point(const line_2d<T>& other) const {
    if (!this->crosses(other)) return optional<vector2<T>>();
    return optional<vector2<T>>(this->unsafe_cross_point(other));
  }

  template <typename T>
  vector2<T> line_2d<T>::unsafe_cross_point(const line_2d<T>& other) const {
    return vector2<T>(
      (this->b() * other.c() - other.b() * this->c()) / (this->a() * other.b() - other.a() * this->b()),
      (other.a() * this->c() - this->a() * other.c()) / (this->a() * other.b() - other.a() * this->b())
    );
  }

  template <typename T>
  bool line_2d<T>::intersects(const line_2d<T>& other) const {
    return this == other || this->crosses(other);
  }

  template <typename T>
  std::vector<variant<vector2<T>, line_2d<T>>> line_2d<T>::intersection(const line_2d<T>& other) const {
    typedef std::vector<variant<vector2<T>, line_2d<T>>> result_t;
    if (this == other) return result_t({*this});
    if (this->crosses(other)) return result_t({this->unsafe_cross_point(other)});
    return result_t();
  }

  template <typename T>
  std::vector<variant<vector2<T>, directed_line_segment_2d<T>>> line_2d<T>::intersection(const directed_line_segment_2d<T>& other) const {
    return other.intersection(*this);
  }

  template <typename T>
  bool line_2d<T>::operator==(const tools::line_2d<T>& other) const {
    return this->b() * other.c() == this->c() * other.b() && this->c() * other.a() == this->a() * other.c() && this->a() * other.b() == this->b() * other.a();
  }

  template <typename T>
  line_2d<T> line_2d<T>::through(const vector2<T>& p1, const vector2<T>& p2) {
    return line_2d(p1.y - p2.y, p2.x - p1.x, (p2.y - p1.y) * p1.x - (p2.x - p1.x) * p1.y);
  }
}

#endif

// lib/half_line_2d.hpp
#ifndef HALF_LINE_2D_HPP
#define HALF_LINE_2D_HPP


#endif

// lib/directed_line_segment_2d.hpp
#ifndef DIRECTED_LINE_SEGMENT_2D_HPP
#define DIRECTED_LINE_SEGMENT_2D_HPP


#endif

// main.cpp

class area {
public:
  tools::half_line_2d<tools::fraction> left;
  tools::directed_line_segment_2d<tools::fraction> center;
  tools::half_line_2d<tools::fraction> right;

  area(const tools::fraction& t_begin, const tools::fraction& t_end, const tools::fraction& v) :
    left(tools::vector2<tools::fraction>(t_begin, v), tools::vector2<tools::fraction>(-1, 1)),
    center(tools::vector2<tools::fraction>(t_begin, v), tools::vector2<tools::fraction>(t_end, v)),
    right(tools::vector2<tools::fraction>(t_end, v), tools::vector2<tools::fraction>(1, 1)) {
  }

  const tools::fraction& t_begin() const {
    return this->center.p1().x;
  }
  const tools::fraction& t_end() const {
    return this->center.p2().x;
  }
  const tools::fraction& velocity() const {
    return this->center.p1().y;
  }
};

class velocity_diagram {
public:
  std::vector<tools::directed_line_segment_2d<tools::fraction>> segments;
  tools::half_line_2d<tools::fraction> last_half_line;

  velocity_diagram() :
    segments(),
    last_half_line(tools::vector2<tools::fraction>(0, 0), tools::vector2<tools::fraction>(1, 1)) {
  }

  velocity_diagram& operator<<(const area& area) {
    const tools::vector2<tools::fraction> joint = *this->last_half_line.to_line().cross_point(tools::line_2d<tools::fraction>(1, 0, -area.t_begin()));
    if (joint.y < area.velocity()) {
      const tools::optional<tools::vector2<tools::fraction>> possible_cross_point = this->last_half_line.cross_point(area.center);
      if (possible_cross_point) {
        const tools::vector2<tools::fraction>& cross_point = *possible_cross_point;
        if (cross_point.x < area.t_end()) {
          this->segments.emplace_back(this->last_half_line.a(), cross_point);
          this->segments.emplace_back(cross_point, area.center.p2());
          this->last_half_line = area.right;
        } else {
          // do nothing
        }
      } else {
        // do nothing
      }
    } else if (joint.y == area.velocity()) {
      if (this->last_half_line.a().x < area.t_begin()) {
        this->segments.emplace_back(this->last_half_line.a(), joint);
      }
      this->segments.emplace_back(area.center.p1(), area.center.p2());
      this->last_half_line = area.right;
    } else {
      if (this->last_half_line.a().x < area.t_begin()) {
        const tools::optional<tools::vector2<tools::fraction>> possible_cross_point = this->last_half_line.cross_point(area.left);
        if (possible_cross_point) {
          const tools::vector2<tools::fraction>& cross_point = *possible_cross_point;
          if (this->last_half_line.a().x < cross_point.x) {
            this->segments.emplace_back(this->last_half_line.a(), cross_point);
          }
          this->segments.emplace_back(cross_point, area.left.a());
          this->segments.emplace_back(area.center.p1(), area.center.p2());
          this->last_half_line = area.right;
          goto MATCHED;
        }
      }
      for (std::int_fast64_t i = tools::to_signed(this->segments.size()) - 1; i >= 0; --i) {
        const tools::optional<tools::vector2<tools::fraction>> possible_cross_point = this->segments[i].cross_point(area.left);
        if (possible_cross_point) {
          const tools::vector2<tools::fraction>& cross_point = *possible_cross_point;
          if (cross_point.x == this->segments[i].p1().x) {
            this->segments.erase(this->segments.begin() + i, this->segments.end());
            this->segments.emplace_back(cross_point, area.left.a());
            this->segments.emplace_back(area.center.p1(), area.center.p2());
            this->last_half_line = area.right;
          } else {
            const tools::vector2<tools::fraction> p = this->segments[i].p1();
            this->segments.erase(this->segments.begin() + i, this->segments.end());
            this->segments.emplace_back(p, cross_point);
            this->segments.emplace_back(cross_point, area.left.a());
            this->segments.emplace_back(area.center.p1(), area.center.p2());
            this->last_half_line = area.right;
          }
          goto MATCHED;
        }
      }
    MATCHED:
      ;
    }
    return *this;
  }

  velocity_diagram& operator<<(const tools::fraction& last_t) {
    const tools::vector2<tools::fraction> last_point(last_t, 0);
    const tools::half_line_2d<tools::fraction> cut_line(last_point, tools::vector2<tools::fraction>(-1, 1));
    if (this->last_half_line.a().x < last_t) {
      const tools::optional<tools::vector2<tools::fraction>> possible_cross_point = this->last_half_line.cross_point(cut_line);
      if (possible_cross_point) {
        const tools::vector2<tools::fraction>& cross_point = *possible_cross_point;
        if (this->last_half_line.a().x < cross_point.x) {
          this->segments.emplace_back(this->last_half_line.a(), cross_point);
        }
        this->segments.emplace_back(cross_point, last_point);
        this->last_half_line = tools::half_line_2d<tools::fraction>(last_point, tools::vector2<tools::fraction>(1, 1));
        goto MATCHED;
      }
    }
    for (std::int_fast64_t i = tools::to_signed(this->segments.size()) - 1; i >= 0; --i) {
      const tools::optional<tools::vector2<tools::fraction>> possible_cross_point = this->segments[i].cross_point(cut_line);
      if (possible_cross_point) {
        const tools::vector2<tools::fraction>& cross_point = *possible_cross_point;
        if (cross_point.x == this->segments[i].p1().x) {
          this->segments.erase(this->segments.begin() + i, this->segments.end());
          this->segments.emplace_back(cross_point, last_point);
          this->last_half_line = tools::half_line_2d<tools::fraction>(last_point, tools::vector2<tools::fraction>(1, 1));
        } else {
          const tools::vector2<tools::fraction> p = this->segments[i].p1();
          this->segments.erase(this->segments.begin() + i, this->segments.end());
          this->segments.emplace_back(p, cross_point);
          this->segments.emplace_back(cross_point, last_point);
          this->last_half_line = tools::half_line_2d<tools::fraction>(last_point, tools::vector2<tools::fraction>(1, 1));
        }
        goto MATCHED;
      }
    }
  MATCHED:
    return *this;
  }

  tools::fraction distance() const {
    return std::accumulate(
      this->segments.begin(),
      this->segments.end(),
      tools::fraction(0, 1),
      [](const tools::fraction& sum, const tools::directed_line_segment_2d<tools::fraction>& segment) {
        const tools::fraction min_velocity = std::min(segment.p1().y, segment.p2().y);
        const tools::fraction diff_velocity = std::max(segment.p1().y, segment.p2().y) - min_velocity;
        const tools::fraction interval = segment.p2().x - segment.p1().x;
        return sum + interval * (min_velocity + diff_velocity / 2);
      }
    );
  }

  friend std::ostream& operator<<(std::ostream& os, velocity_diagram& self) {
    for (const tools::directed_line_segment_2d<tools::fraction>& segment : self.segments) {
      os << '[' << segment.p1() << ", " << segment.p2() << ']' << std::endl;
    }
    return os;
  }
};

int main() {
  std::int_fast64_t n;
  std::cin >> n;
  std::vector<std::int_fast64_t> t, v;
  t.reserve(n);
  v.reserve(n);
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), n, std::back_inserter(t));
  std::copy_n(std::istream_iterator<std::int_fast64_t>(std::cin), n, std::back_inserter(v));

  std::vector<area> areas;
  areas.reserve(n);
  for (std::int_fast64_t i = 0; i < n; ++i) {
    const tools::fraction prev_t = i == 0 ? 0 : areas.back().t_end();
    areas.emplace_back(prev_t, prev_t + t[i], v[i]);
  }

  velocity_diagram diagram;
  for (const area& area : areas) {
    diagram << area;
  }
  diagram << areas.back().t_end();

  std::cout << std::fixed << std::setprecision(6) << static_cast<double>(diagram.distance()) << std::endl;
  return 0;
}

Measured memory_bytes: 256