#include <bits/stdc++.h>
using LL = long long;
using ULL = unsigned long long;
using LLL = __int128;
using ULLL = unsigned __int128;
namespace std {
void swap(int& x, int& y) { x ^= y ^= x ^= y; }
void swap(LL& x, LL& y) { x ^= y ^= x ^= y; }
};  // namespace std
using std::swap;
template <typename T, typename P>
inline auto max(const T& x, const P& y) -> decltype(x < y ? y : x) {
  return x < y ? y : x;
}
template <typename T, typename P>
inline auto min(const T& x, const P& y) -> decltype(x < y ? x : y) {
  return x < y ? x : y;
}
template <typename T, typename... Args>
inline auto max(const T& x, const Args&... args)
    -> decltype(max(x, max(args...))) {
  return max(x, max(args...));
}
template <typename T, typename... Args>
inline auto min(const T& x, const Args&... args)
    -> decltype(min(x, min(args...))) {
  return min(x, min(args...));
}
template <typename T>
inline T max(const T& x) {
  return x;
}
template <typename T>
inline T min(const T& x) {
  return x;
}
template <typename T, typename... Args>
inline void chkmax(T& d, const Args&... args) {
  d = max(d, args...);
}
template <typename T, typename... Args>
inline void chkmin(T& d, const Args&... args) {
  d = min(d, args...);
}
class IO {
  static const int MAXSIZE = 1 << 20;
  char buf[MAXSIZE], *p1, *p2;
  char pbuf[MAXSIZE], *pp;
  long double eps = 1e-8L;
  LLL pow10 = 1000000;
  int precision;
  FILE *infile, *outfile;

 public:
  IO(FILE* in = nullptr, FILE* out = nullptr)
      : precision(6), infile(in), outfile(out) {
    p1 = p2 = buf;
    pp = pbuf;
  }
  ~IO() { fwrite(pbuf, 1, pp - pbuf, outfile); }
  inline static constexpr bool blank(char ch);
  inline void flush();
  inline void input(const char* str);
  inline void output(const char* str);
  inline void input(FILE* f);
  inline void output(FILE* f);
  inline int getch();
  template <typename T, typename... Args>
  bool read(T& x, Args&... args);
  inline bool read() const { return true; }
  template <typename T>
  typename std::enable_if<
      std::is_integral<T>::value || std::is_floating_point<T>::value ||
          std::is_same<T, LLL>::value || std::is_same<T, ULLL>::value,
      bool>::type
  read(T& x);
  bool read(char& ch);
  bool read(char* s);
  bool readline(char* s);
  inline void putch(const char c);
  inline void putback(const char c);
  inline void setprecision(int n = 6);
  template <typename T, typename... Args>
  void write(const T& x, const Args&... args);
  inline void write() const {}
  template <typename T>
  typename std::enable_if<std::is_integral<T>::value ||
                              std::is_same<T, LLL>::value ||
                              std::is_same<T, ULLL>::value,
                          void>::type
  write(T x);
  inline void write(char c);
  template <typename T>
  typename std::enable_if<std::is_floating_point<T>::value, void>::type write(
      T x);
  inline void write(bool x);
  void write(char* s);
  void write(const char* s);
  template <typename... Args>
  void writeln(Args... x) {
    write(x...), putch('\n');
  }
} io(stdin, stdout), err(nullptr, stderr);
template <typename... Args>
inline void writeln(Args... x) {
  io.write(x...), io.putch('\n');
}
int main() { return 0; }
inline constexpr bool IO::blank(char ch) {
  return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void IO::flush() {
  fwrite(pbuf, 1, pp - pbuf, outfile), pp = pbuf;
  fflush(outfile);
}
inline void IO::input(const char* str) {
  FILE* file = fopen(str, "rb");
  infile = file;
}
inline void IO::output(const char* str) {
  FILE* file = fopen(str, "wb");
  outfile = file;
}
inline void IO::input(FILE* f) { infile = f; }
inline void IO::output(FILE* f) { outfile = f; }
inline int IO::getch() {
  return (p1 == p2 ? (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, infile)) : 0),
         (p1 == p2) ? EOF : *p1++;
}
inline void IO::putback(const char c) { *(--p1) = c; }
template <typename T, typename... Args>
bool IO::read(T& x, Args&... args) {
  return read(x) && read(args...);
}
template <typename T>
typename std::enable_if<
    std::is_integral<T>::value || std::is_floating_point<T>::value ||
        std::is_same<T, LLL>::value || std::is_same<T, ULLL>::value,
    bool>::type
IO::read(T& x) {
  T tmp = 1;
  bool sign = false;
  x = 0;
  int ch = getch();
  for (; !(ch >= '0' && ch <= '9') && ~ch; ch = getch()) sign = !(ch ^ '-');
  if (!(~ch)) return false;
  for (; (ch >= '0' && ch <= '9'); ch = getch()) x = x * 10 + (ch ^ '0');
  if (ch == '.' && std::is_floating_point<T>::value)
    for (ch = getch(); (ch >= '0' && ch <= '9'); ch = getch())
      tmp /= 10.0, x += tmp * (ch ^ '0');
  if (~ch) putback(ch);
  if (sign) x = -x;
  return true;
}
bool IO::read(char& ch) {
  for (ch = getch(); blank(ch) && ~ch; ch = getch())
    ;
  return ~ch;
}
bool IO::read(char* s) {
  int ch = getch();
  while (blank(ch)) ch = getch();
  if (!(~ch)) return false;
  while (!blank(ch) && ~ch) *s++ = ch, ch = getch();
  *s = 0;
  if (~ch) putback(ch);
  return true;
}
bool IO::readline(char* s) {
  int ch = getch();
  while (blank(ch) && (ch ^ '\n')) ch = getch();
  if (!(~ch)) return false;
  while ((ch ^ '\n') && ~ch) *s++ = ch, ch = getch();
  *s = 0;
  if (~ch) putback(ch);
  return true;
}
inline void IO::putch(const char c) {
  ((pp - pbuf == MAXSIZE) ? fwrite(pbuf, 1, MAXSIZE, outfile), pp = pbuf : 0),
      *pp++ = c;
}
inline void IO::setprecision(int n) {
  precision = n;
  eps = powl(10.0L, -precision - 2);
  pow10 = powl(10.0L, precision) + eps;
}
template <typename T, typename... Args>
void IO::write(const T& x, const Args&... args) {
  write(x);
  if (sizeof...(args)) write(args...);
}
template <typename T>
typename std::enable_if<std::is_integral<T>::value ||
                            std::is_same<T, LLL>::value ||
                            std::is_same<T, ULLL>::value,
                        void>::type
IO::write(T x) {
  if (x < 0) x = ~x + 1, putch('-');
  static T sta[100];
  int top = 0;
  do sta[top++] = x % 10, x /= 10;
  while (x);
  while (top) putch(sta[--top] + '0');
}
inline void IO::write(bool x) { putch(x ^ 48); }
inline void IO::write(char c) { putch(c); }
template <typename T>
typename std::enable_if<std::is_floating_point<T>::value>::type IO::write(T x) {
  if (x == 0) {
    putch('0'), putch('.');
    for (int i = 1; i <= precision; i++) putch('0');
    return;
  }
  if (x < 0) putch('-'), x = -x;
  T res = (LLL)(x * pow10 + 0.5) / (pow10 * 1.0);
  LLL y = LLL(res * pow10 + eps) % pow10;
  write(LLL(res + eps));
  if (precision) {
    putch('.');
    static int sta[100], p = 0;
    for (; p < precision; y /= 10) sta[++p] = y % 10;
    for (int i = p; i >= 1; i--) putch(sta[i] ^ 48);
  }
}
void IO::write(char* s) {
  while (*s) putch(*s++);
}
void IO::write(const char* s) {
  while (*s) putch(*s++);
}
