#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:36777216")
using namespace std;
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline double &RF(double &);
inline double RF() {
  double x;
  return RF(x);
}
inline char *RS(char *s);
inline char &RC(char &c);
inline char RC();
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
template <class T>
inline T &RDD(T &);
inline long long RDD() {
  long long x;
  return RDD(x);
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline double &RF(double &a, double &b) {
  RF(a), RF(b);
  return a;
}
inline double &RF(double &a, double &b, double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f, double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T0, class T1>
inline void RDD(T0 &a, T1 &b) {
  RDD(a), RDD(b);
}
template <class T0, class T1, class T2>
inline void RDD(T0 &a, T1 &b, T2 &c) {
  RDD(a), RDD(b), RDD(c);
}
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
      FLC(A6, x);
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, less<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(stack<T> &S) {
  while (!S.empty()) S.pop();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < n; ++i) CLR(A[i]);
}
template <class T>
inline bool EPT(T &a) {
  return a.empty();
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
  return A;
}
template <class T>
inline T &RVS(T &A) {
  r0erse(A.begin(), A.end());
  return A;
}
template <class T>
inline T &UNQQ(T &A) {
  A.resize(unique(A.begin(), A.end()) - A.begin());
  return A;
}
template <class T>
inline T &UNQ(T &A) {
  SRT(A);
  return UNQQ(A);
}
const int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
const double OO = 1e20;
const double PI = acos(-1.0);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <class T>
inline T &checkMin(T &a, const T b) {
  if (b < a) a = b;
  return a;
}
template <class T>
inline T &checkMax(T &a, const T b) {
  if (a < b) a = b;
  return a;
}
template <class T>
inline T &checkMin(T &a, T &b, const T x) {
  checkMin(a, x), checkMin(b, x);
  return a;
}
template <class T>
inline T &checkMax(T &a, T &b, const T x) {
  checkMax(a, x), checkMax(b, x);
  return a;
}
template <class T, class C>
inline T &checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
  return a;
}
template <class T, class C>
inline T &checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
  return a;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
template <class T>
inline T ceil(T x, T y) {
  return (x - 1) / y + 1;
}
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
inline int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
inline int sgn(double x, double y) { return sgn(x - y); }
inline double cos(double a, double b, double c) {
  return (sqr(a) + sqr(b) - sqr(c)) / (2 * a * b);
}
inline double cot(double x) { return 1. / tan(x); };
inline double sec(double x) { return 1. / cos(x); };
inline double csc(double x) { return 1. / sin(x); };
namespace BO {
inline bool _1(int x, int i) { return bool(x & 1 << i); }
inline bool _1(long long x, int i) { return bool(x & 1LL << i); }
inline long long _1(int i) { return 1LL << i; }
inline long long _U(int i) { return _1(i) - 1; };
inline int r0erse_bits(int x) {
  x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
  x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
  x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
  x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
  x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
  return x;
}
inline long long r0erse_bits(long long x) {
  x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
  x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
  x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
  x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
  x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
  return x;
}
template <class T>
inline bool odd(T x) {
  return x & 1;
}
template <class T>
inline bool even(T x) {
  return !odd(x);
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
template <class T>
inline T cover_bit(T x) {
  T p = 1;
  while (p < x) p <<= 1;
  return p;
}
template <class T>
inline int cover_idx(T x) {
  int p = 0;
  while (_1(p) < x) ++p;
  return p;
}
inline int clz(int x) { return __builtin_clz(x); }
inline int clz(long long x) { return __builtin_clzll(x); }
inline int ctz(int x) { return __builtin_ctz(x); }
inline int ctz(long long x) { return __builtin_ctzll(x); }
inline int lg2(int x) { return !x ? -1 : 31 - clz(x); }
inline int lg2(long long x) { return !x ? -1 : 63 - clz(x); }
inline int low_idx(int x) { return !x ? -1 : ctz(x); }
inline int low_idx(long long x) { return !x ? -1 : ctz(x); }
inline int high_idx(int x) { return lg2(x); }
inline int high_idx(long long x) { return lg2(x); }
inline int parity(int x) { return __builtin_parity(x); }
inline int parity(long long x) { return __builtin_parityll(x); }
inline int count_bits(int x) { return __builtin_popcount(x); }
inline int count_bits(long long x) { return __builtin_popcountll(x); }
}  // namespace BO
using namespace BO;
namespace CG {
inline double dist2(double x, double y) { return sqr(x) + sqr(y); }
struct Po {
  double x, y;
  Po(double x = 0, double y = 0) : x(x), y(y) {}
  void in() { RF(x, y); }
  void out() { printf("(%.2f,%.2f)", x, y); }
  inline friend istream &operator>>(istream &i, Po &p) {
    return i >> p.x >> p.y;
  }
  inline friend ostream &operator<<(ostream &o, Po p) {
    return o << "(" << p.x << ", " << p.y << ")";
  }
  Po operator-() const { return Po(-x, -y); }
  Po &operator+=(const Po &p) {
    x += p.x, y += p.y;
    return *this;
  }
  Po &operator-=(const Po &p) {
    x -= p.x, y -= p.y;
    return *this;
  }
  Po &operator*=(double k) {
    x *= k, y *= k;
    return *this;
  }
  Po &operator/=(double k) {
    x /= k, y /= k;
    return *this;
  }
  Po &operator*=(const Po &p) { return *this = *this * p; }
  Po &operator/=(const Po &p) { return *this = *this / p; }
  Po operator+(const Po &p) const { return Po(x + p.x, y + p.y); }
  Po operator-(const Po &p) const { return Po(x - p.x, y - p.y); }
  Po operator*(double k) const { return Po(x * k, y * k); }
  Po operator/(double k) const { return Po(x / k, y / k); }
  Po operator*(const Po &p) const {
    return Po(x * p.x - y * p.y, y * p.x + x * p.y);
  }
  Po operator/(const Po &p) const {
    return Po(x * p.x + y * p.y, y * p.x - x * p.y) / p.len2();
  }
  bool operator==(const Po &p) const { return !sgn(x, p.x) && !sgn(y, p.y); };
  bool operator!=(const Po &p) const { return sgn(x, p.x) || sgn(y, p.y); }
  bool operator<(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) < 0;
  }
  bool operator<=(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) <= 0;
  }
  bool operator>(const Po &p) const { return !(*this <= p); }
  bool operator>=(const Po &p) const { return !(*this < p); }
  double len2() const { return dist2(x, y); }
  double len() const { return sqrt(len2()); }
  double arg() const { return atan2(y, x); }
  Po &_1() { return *this /= len(); }
  Po &conj() {
    y = -y;
    return *this;
  }
  Po &lt() {
    swap(x, y), x = -x;
    return *this;
  }
  Po &rt() {
    swap(x, y), y = -y;
    return *this;
  }
  Po &rot(double a, const Po &o = Po()) {
    *this -= o;
    *this *= Po(cos(a), sin(a));
    return *this += o;
  }
  inline int q() const { return (y > 0 || y == 0 && x >= 0) ? 0 : 1; }
};
inline double dot(double x1, double y1, double x2, double y2) {
  return x1 * x2 + y1 * y2;
}
inline double dot(const Po &a, const Po &b) { return dot(a.x, a.y, b.x, b.y); }
inline double dot(const Po &p0, const Po &p1, const Po &p2) {
  return dot(p1 - p0, p2 - p0);
}
inline double det(double x1, double y1, double x2, double y2) {
  return x1 * y2 - x2 * y1;
}
inline double det(const Po &a, const Po &b) { return det(a.x, a.y, b.x, b.y); }
inline double det(const Po &p0, const Po &p1, const Po &p2) {
  return det(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1) {
  return acos(dot(p0, p1) / p0.len() / p1.len());
}
inline double ang(const Po &p0, const Po &p1, const Po &p2) {
  return ang(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1, const Po &p2, const Po &p3) {
  return ang(p1 - p0, p3 - p2);
}
inline double dist2(const Po &a, const Po &b) {
  return dist2(a.x - b.x, a.y - b.y);
}
template <class T1, class T2>
inline int dett(const T1 &x, const T2 &y) {
  return sgn(det(x, y));
}
template <class T1, class T2, class T3>
inline int dett(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(det(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(det(x, y, z, w));
}
template <class T1, class T2>
inline int dott(const T1 &x, const T2 &y) {
  return sgn(dot(x, y));
}
template <class T1, class T2, class T3>
inline int dott(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(dot(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(dot(x, y, z, w));
}
template <class T1, class T2>
inline double arg(const T1 &x, const T2 &y) {
  double a = ang(x, y);
  return ~dett(x, y) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3>
inline double arg(const T1 &x, const T2 &y, const T3 &z) {
  double a = ang(x, y, z);
  return ~dett(x, y, z) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3, class T4>
inline double arg(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  double a = ang(x, y, z, w);
  return ~dett(x, y, z, w) ? a : 2 * PI - a;
}
template <class T1, class T2>
inline double dist(const T1 &x, const T2 &y) {
  return sqrt(dist2(x, y));
}
template <class T1, class T2, class T3>
inline double dist(const T1 &x, const T2 &y, const T3 &z) {
  return sqrt(dist2(x, y, z));
}
inline Po _1(Po p) { return p._1(); }
inline Po conj(Po p) { return p.conj(); }
inline Po lt(Po p) { return p.lt(); }
inline Po rt(Po p) { return p.rt(); }
inline Po rot(Po p, double a, const Po &o = Po()) { return p.rot(a, o); }
inline Po operator*(double k, const Po &p) { return p * k; }
inline Po operator/(double k, const Po &p) { return conj(p) * k / p.len2(); }
struct Line {
  Po a, b;
  Line(const Po &a = Po(), const Po &b = Po()) : a(a), b(b) {}
  Line(double x0, double y0, double x1, double y1)
      : a(Po(x0, y0)), b(Po(x1, y1)) {}
  Line(const Line &l) : a(l.a), b(l.b) {}
  Line(double A, double B, double C) {
    C = -C;
    if (!::sgn(A))
      a = Po(0, C / B), b = Po(1, C / B);
    else if (!::sgn(B))
      a = Po(C / A, 0), b = Po(C / A, 1);
    else
      a = Po(0, C / B), b = Po(1, (C - A) / B);
  }
  void in() { a.in(), b.in(); }
  inline friend istream &operator>>(istream &i, Line &p) {
    return i >> p.a >> p.b;
  }
  inline friend ostream &operator<<(ostream &o, Line p) {
    return o << p.a << "-" << p.b;
  }
  Line operator+(const Po &x) const { return Line(a + x, b + x); }
  Line operator-(const Po &x) const { return Line(a - x, b - x); }
  Line operator*(double k) const { return Line(a * k, b * k); }
  Line operator/(double k) const { return Line(a / k, b / k); }
  Po operator*(const Line &) const;
  Po d() const { return b - a; }
  double len2() const { return d().len2(); }
  double len() const { return d().len(); }
  double arg() const { return d().arg(); }
  int sgn(const Po &p) const { return dett(a, b, p); }
  int sgn(const Line &) const;
  bool sameSgn(const Po &p1, const Po &p2) const { return sgn(p1) == sgn(p2); }
  void getEquation(double &K, double &B) const {
    K = ::sgn(a.x, b.x) ? (b.y - a.y) / (b.x - a.x) : OO;
    B = a.y - K * a.x;
  }
  void getEquation(double &A, double &B, double &C) const {
    A = a.y - b.y, B = b.x - a.x, C = det(a, b);
  }
  Line &push(double r) {
    Po v = d()._1().lt() * r;
    a += v, b += v;
    return *this;
  }
};
inline double dot(const Line &l1, const Line &l2) {
  return dot(l1.d(), l2.d());
}
inline double dot(const Line &l, const Po &p) { return dot(l.a, l.b, p); }
inline double dot(const Po &p, const Line &l) { return dot(p, l.a, l.b); }
inline double det(const Line &l1, const Line &l2) {
  return det(l1.d(), l2.d());
}
inline double det(const Line &l, const Po &p) { return det(l.a, l.b, p); }
inline double det(const Po &p, const Line &l) { return det(p, l.a, l.b); }
inline double ang(const Line &l0, const Line &l1) {
  return ang(l0.d(), l1.d());
}
inline double ang(const Line &l, const Po &p) { return ang(l.a, l.b, p); }
inline double ang(const Po &p, const Line &l) { return ang(p, l.a, l.b); }
inline int Line::sgn(const Line &l) const { return dett(*this, l); }
inline Po Line::operator*(const Line &l) const {
  return a + d() * det(a, l) / det(*this, l);
}
inline Po operator&(const Po &p, const Line &l) {
  return l * Line(p, p + l.d().lt());
}
inline Po operator%(const Po &p, const Line &l) { return p & l * 2 - p; }
inline Line push(Line l, double r) { return l.push(r); }
struct Seg : public Line {
  Seg(const Po &a = Po(), const Po &b = Po()) : Line(a, b) {}
  Seg(double x0, double y0, double x1, double y1) : Line(x0, y0, x1, y1) {}
  Seg(const Line &l) : Line(l) {}
  Seg(const Po &a, double alpha) : Line(a, alpha) {}
  Seg(double A, double B, double C) : Line(A, B, C) {}
  inline int sgn(const Po &p) const;
  inline int sgn(const Line &l) const;
  inline bool qrt(const Seg &l) const;
  inline int sgn(const Seg &l) const;
};
inline int Seg::sgn(const Po &p) const {
  if (dett(p, a, b)) return -1;
  if (a == p || b == p) return 0;
  return -dott(p, a, b);
}
inline int Seg::sgn(const Line &l) const { return sgn(*this * l); }
inline bool Seg::qrt(const Seg &l) const {
  return min(a.x, b.x) <= max(l.a.x, l.b.x) &&
         min(l.a.x, l.b.x) <= max(a.x, b.x) &&
         min(a.y, b.y) <= max(l.a.y, l.b.y) &&
         min(l.a.y, l.b.y) <= max(a.y, b.y);
}
inline int Seg::sgn(const Seg &l) const {
  if (!qrt(l)) return -1;
  int d1 = dett(a, b, l.a), d2 = dett(a, b, l.b), d3 = dett(l.a, l.b, a),
      d4 = dett(l.a, l.b, b);
  if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 1;
  return ((!d1 && dott(l.a - a, l.a - b) <= 0) ||
          (!d2 && dott(l.b - a, l.b - b) <= 0) ||
          (!d3 && dott(a - l.a, a - l.b) <= 0) ||
          (!d4 && dott(b - l.a, b - l.b) <= 0))
             ? 0
             : -1;
}
inline double dist2(const Line &l, const Po &p) {
  return sqr(fabs(det(l.d(), p - l.a))) / l.len2();
}
inline double dist2(const Line &l1, const Line &l2) {
  return dett(l1, l2) ? 0 : dist2(l1, l2.a);
}
inline double dist2(const Seg &l, const Po &p) {
  Po pa = p - l.a, pb = p - l.b;
  if (dott(l.d(), pa) <= 0) return pa.len2();
  if (dott(l.d(), pb) >= 0) return pb.len2();
  return dist2(Line(l), p);
}
inline double dist2(const Seg &s, const Line &l) {
  Po v1 = s.a - l.a, v2 = s.b - l.a;
  double d1 = det(l.d(), v1), d2 = det(l.d(), v2);
  return sgn(d1) != sgn(d2) ? 0 : sqr(min(fabs(d1), fabs(d2))) / l.len2();
}
inline double dist2(const Seg &l1, const Seg &l2) {
  if (~l1.sgn(l2))
    return 0;
  else
    return min(dist2(l2, l1.a), dist2(l2, l1.b), dist2(l1, l2.a),
               dist2(l1, l2.b));
}
template <class T1, class T2>
inline double dist2(const T1 &a, const T2 &b) {
  return dist2(b, a);
}
}  // namespace CG
using namespace CG;
template <class T>
inline T &RD(T &x) {
  char c;
  while (!isdigit((c = getchar())))
    ;
  x = c - '0';
  while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  return x;
}
template <class T>
inline T &RDD(T &x) {
  char c;
  while ((c = getchar()), c != '-' && !isdigit(c))
    ;
  if (c == '-') {
    x = '0' - (c = getchar());
    while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  }
  return x;
}
inline double &RF(double &x) {
  char c;
  while ((c = getchar()), c != '-' && c != '.' && !isdigit(c))
    ;
  if (c == '-')
    if ((c = getchar()) == '.') {
      x = 0;
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
      x *= l;
    } else {
      x = '0' - c;
      while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
      if (c == '.') {
        double l = 1;
        while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
        x *= l;
      }
    }
  else if (c == '.') {
    x = 0;
    double l = 1;
    while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
    x *= l;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
    if (c == '.') {
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
      x *= l;
    }
  }
  return x;
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
long long last_ans;
int Case;
template <class T>
inline void OT(const T &x) {
  printf("%d\n", x);
}
const int N = int(1e6) + 9;
struct rec {
  int x;
  double h;
  bool operator<(const rec &rhs) const {
    return sgn(h, rhs.h) > 0 || sgn(h, rhs.h) == 0 && x < rhs.x;
  }
};
int n;
double l[N], r[N], h[N];
int fa[N];
void makeSet(int size) {
  for (int i = 0; i < size; i++) fa[i] = i;
  return;
}
int find(int x) {
  if (x != fa[x]) fa[x] = find(fa[x]);
  return fa[x];
}
priority_queue<rec> Q;
int main() {
  cin >> n;
  makeSet(n);
  for (int i = 0; i < n; ++i) {
    h[i] = RD();
    l[i] = r[i] = i;
    rec t;
    t.x = i;
    t.h = h[i];
    Q.push(t);
  }
  while (!Q.empty()) {
    rec t = Q.top();
    Q.pop();
    int l1 = find(t.x);
    if (l1 != 0) {
      int l0 = find(l1 - 1);
      if (sgn(h[l1], h[l0]) <= 0) {
        h[l0] = (h[l0] * (r[l0] - l0 + 1) + h[l1] * (r[l1] - l1 + 1)) /
                (r[l1] - l0 + 1);
        r[l0] = r[l1];
        fa[l1] = l0;
        rec tt;
        tt.x = l0;
        tt.h = h[l0];
        Q.push(tt);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    int x = find(i);
    printf("%.9f\n", h[x]);
  }
}

### Prompt

Please formulate a cpp solution to the following problem:

There are n water tanks in a row, i-th of them contains a_i liters of water. The tanks are numbered from 1 to n from left to right.

You can perform the following operation: choose some subsegment [l, r] (1≤ l ≤ r ≤ n), and redistribute water in tanks l, l+1, ..., r evenly. In other words, replace each of a_l, a_{l+1}, ..., a_r by \frac{a_l + a_{l+1} + ... + a_r}{r-l+1}. For example, if for volumes [1, 3, 6, 7] you choose l = 2, r = 3, new volumes of water will be [1, 4.5, 4.5, 7]. You can perform this operation any number of times.

What is the lexicographically smallest sequence of volumes of water that you can achieve?

As a reminder:

A sequence a is lexicographically smaller than a sequence b of the same length if and only if the following holds: in the first (leftmost) position where a and b differ, the sequence a has a smaller element than the corresponding element in b.

Input

The first line contains an integer n (1 ≤ n ≤ 10^6) — the number of water tanks.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^6) — initial volumes of water in the water tanks, in liters.

Because of large input, reading input as doubles is not recommended.

Output

Print the lexicographically smallest sequence you can get. In the i-th line print the final volume of water in the i-th tank.

Your answer is considered correct if the absolute or relative error of each a_i does not exceed 10^{-9}.

Formally, let your answer be a_1, a_2, ..., a_n, and the jury's answer be b_1, b_2, ..., b_n. Your answer is accepted if and only if \frac{|a_i - b_i|}{max{(1, |b_i|)}} ≤ 10^{-9} for each i.

Examples

Input


4
7 5 5 7


Output


5.666666667
5.666666667
5.666666667
7.000000000


Input


5
7 8 8 10 12


Output


7.000000000
8.000000000
8.000000000
10.000000000
12.000000000


Input


10
3 9 5 5 1 7 5 3 8 7


Output


3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000

Note

In the first sample, you can get the sequence by applying the operation for subsegment [1, 3].

In the second sample, you can't get any lexicographically smaller sequence.

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:36777216")
using namespace std;
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline double &RF(double &);
inline double RF() {
  double x;
  return RF(x);
}
inline char *RS(char *s);
inline char &RC(char &c);
inline char RC();
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
template <class T>
inline T &RDD(T &);
inline long long RDD() {
  long long x;
  return RDD(x);
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline double &RF(double &a, double &b) {
  RF(a), RF(b);
  return a;
}
inline double &RF(double &a, double &b, double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f, double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T0, class T1>
inline void RDD(T0 &a, T1 &b) {
  RDD(a), RDD(b);
}
template <class T0, class T1, class T2>
inline void RDD(T0 &a, T1 &b, T2 &c) {
  RDD(a), RDD(b), RDD(c);
}
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
      FLC(A6, x);
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, less<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(priority_queue<T, vector<T>, greater<T> > &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(stack<T> &S) {
  while (!S.empty()) S.pop();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < n; ++i) CLR(A[i]);
}
template <class T>
inline bool EPT(T &a) {
  return a.empty();
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C B) {
  sort(A.begin(), A.end(), B);
  return A;
}
template <class T>
inline T &RVS(T &A) {
  r0erse(A.begin(), A.end());
  return A;
}
template <class T>
inline T &UNQQ(T &A) {
  A.resize(unique(A.begin(), A.end()) - A.begin());
  return A;
}
template <class T>
inline T &UNQ(T &A) {
  SRT(A);
  return UNQQ(A);
}
const int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
const double OO = 1e20;
const double PI = acos(-1.0);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template <class T>
inline T &checkMin(T &a, const T b) {
  if (b < a) a = b;
  return a;
}
template <class T>
inline T &checkMax(T &a, const T b) {
  if (a < b) a = b;
  return a;
}
template <class T>
inline T &checkMin(T &a, T &b, const T x) {
  checkMin(a, x), checkMin(b, x);
  return a;
}
template <class T>
inline T &checkMax(T &a, T &b, const T x) {
  checkMax(a, x), checkMax(b, x);
  return a;
}
template <class T, class C>
inline T &checkMin(T &a, const T b, C c) {
  if (c(b, a)) a = b;
  return a;
}
template <class T, class C>
inline T &checkMax(T &a, const T b, C c) {
  if (c(a, b)) a = b;
  return a;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
template <class T>
inline T ceil(T x, T y) {
  return (x - 1) / y + 1;
}
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
inline int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
inline int sgn(double x, double y) { return sgn(x - y); }
inline double cos(double a, double b, double c) {
  return (sqr(a) + sqr(b) - sqr(c)) / (2 * a * b);
}
inline double cot(double x) { return 1. / tan(x); };
inline double sec(double x) { return 1. / cos(x); };
inline double csc(double x) { return 1. / sin(x); };
namespace BO {
inline bool _1(int x, int i) { return bool(x & 1 << i); }
inline bool _1(long long x, int i) { return bool(x & 1LL << i); }
inline long long _1(int i) { return 1LL << i; }
inline long long _U(int i) { return _1(i) - 1; };
inline int r0erse_bits(int x) {
  x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
  x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
  x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
  x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
  x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
  return x;
}
inline long long r0erse_bits(long long x) {
  x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
  x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
  x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
  x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
  x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
  x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
  return x;
}
template <class T>
inline bool odd(T x) {
  return x & 1;
}
template <class T>
inline bool even(T x) {
  return !odd(x);
}
template <class T>
inline T low_bit(T x) {
  return x & -x;
}
template <class T>
inline T high_bit(T x) {
  T p = low_bit(x);
  while (p != x) x -= p, p = low_bit(x);
  return p;
}
template <class T>
inline T cover_bit(T x) {
  T p = 1;
  while (p < x) p <<= 1;
  return p;
}
template <class T>
inline int cover_idx(T x) {
  int p = 0;
  while (_1(p) < x) ++p;
  return p;
}
inline int clz(int x) { return __builtin_clz(x); }
inline int clz(long long x) { return __builtin_clzll(x); }
inline int ctz(int x) { return __builtin_ctz(x); }
inline int ctz(long long x) { return __builtin_ctzll(x); }
inline int lg2(int x) { return !x ? -1 : 31 - clz(x); }
inline int lg2(long long x) { return !x ? -1 : 63 - clz(x); }
inline int low_idx(int x) { return !x ? -1 : ctz(x); }
inline int low_idx(long long x) { return !x ? -1 : ctz(x); }
inline int high_idx(int x) { return lg2(x); }
inline int high_idx(long long x) { return lg2(x); }
inline int parity(int x) { return __builtin_parity(x); }
inline int parity(long long x) { return __builtin_parityll(x); }
inline int count_bits(int x) { return __builtin_popcount(x); }
inline int count_bits(long long x) { return __builtin_popcountll(x); }
}  // namespace BO
using namespace BO;
namespace CG {
inline double dist2(double x, double y) { return sqr(x) + sqr(y); }
struct Po {
  double x, y;
  Po(double x = 0, double y = 0) : x(x), y(y) {}
  void in() { RF(x, y); }
  void out() { printf("(%.2f,%.2f)", x, y); }
  inline friend istream &operator>>(istream &i, Po &p) {
    return i >> p.x >> p.y;
  }
  inline friend ostream &operator<<(ostream &o, Po p) {
    return o << "(" << p.x << ", " << p.y << ")";
  }
  Po operator-() const { return Po(-x, -y); }
  Po &operator+=(const Po &p) {
    x += p.x, y += p.y;
    return *this;
  }
  Po &operator-=(const Po &p) {
    x -= p.x, y -= p.y;
    return *this;
  }
  Po &operator*=(double k) {
    x *= k, y *= k;
    return *this;
  }
  Po &operator/=(double k) {
    x /= k, y /= k;
    return *this;
  }
  Po &operator*=(const Po &p) { return *this = *this * p; }
  Po &operator/=(const Po &p) { return *this = *this / p; }
  Po operator+(const Po &p) const { return Po(x + p.x, y + p.y); }
  Po operator-(const Po &p) const { return Po(x - p.x, y - p.y); }
  Po operator*(double k) const { return Po(x * k, y * k); }
  Po operator/(double k) const { return Po(x / k, y / k); }
  Po operator*(const Po &p) const {
    return Po(x * p.x - y * p.y, y * p.x + x * p.y);
  }
  Po operator/(const Po &p) const {
    return Po(x * p.x + y * p.y, y * p.x - x * p.y) / p.len2();
  }
  bool operator==(const Po &p) const { return !sgn(x, p.x) && !sgn(y, p.y); };
  bool operator!=(const Po &p) const { return sgn(x, p.x) || sgn(y, p.y); }
  bool operator<(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) < 0;
  }
  bool operator<=(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) <= 0;
  }
  bool operator>(const Po &p) const { return !(*this <= p); }
  bool operator>=(const Po &p) const { return !(*this < p); }
  double len2() const { return dist2(x, y); }
  double len() const { return sqrt(len2()); }
  double arg() const { return atan2(y, x); }
  Po &_1() { return *this /= len(); }
  Po &conj() {
    y = -y;
    return *this;
  }
  Po &lt() {
    swap(x, y), x = -x;
    return *this;
  }
  Po &rt() {
    swap(x, y), y = -y;
    return *this;
  }
  Po &rot(double a, const Po &o = Po()) {
    *this -= o;
    *this *= Po(cos(a), sin(a));
    return *this += o;
  }
  inline int q() const { return (y > 0 || y == 0 && x >= 0) ? 0 : 1; }
};
inline double dot(double x1, double y1, double x2, double y2) {
  return x1 * x2 + y1 * y2;
}
inline double dot(const Po &a, const Po &b) { return dot(a.x, a.y, b.x, b.y); }
inline double dot(const Po &p0, const Po &p1, const Po &p2) {
  return dot(p1 - p0, p2 - p0);
}
inline double det(double x1, double y1, double x2, double y2) {
  return x1 * y2 - x2 * y1;
}
inline double det(const Po &a, const Po &b) { return det(a.x, a.y, b.x, b.y); }
inline double det(const Po &p0, const Po &p1, const Po &p2) {
  return det(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1) {
  return acos(dot(p0, p1) / p0.len() / p1.len());
}
inline double ang(const Po &p0, const Po &p1, const Po &p2) {
  return ang(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1, const Po &p2, const Po &p3) {
  return ang(p1 - p0, p3 - p2);
}
inline double dist2(const Po &a, const Po &b) {
  return dist2(a.x - b.x, a.y - b.y);
}
template <class T1, class T2>
inline int dett(const T1 &x, const T2 &y) {
  return sgn(det(x, y));
}
template <class T1, class T2, class T3>
inline int dett(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(det(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(det(x, y, z, w));
}
template <class T1, class T2>
inline int dott(const T1 &x, const T2 &y) {
  return sgn(dot(x, y));
}
template <class T1, class T2, class T3>
inline int dott(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(dot(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(dot(x, y, z, w));
}
template <class T1, class T2>
inline double arg(const T1 &x, const T2 &y) {
  double a = ang(x, y);
  return ~dett(x, y) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3>
inline double arg(const T1 &x, const T2 &y, const T3 &z) {
  double a = ang(x, y, z);
  return ~dett(x, y, z) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3, class T4>
inline double arg(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  double a = ang(x, y, z, w);
  return ~dett(x, y, z, w) ? a : 2 * PI - a;
}
template <class T1, class T2>
inline double dist(const T1 &x, const T2 &y) {
  return sqrt(dist2(x, y));
}
template <class T1, class T2, class T3>
inline double dist(const T1 &x, const T2 &y, const T3 &z) {
  return sqrt(dist2(x, y, z));
}
inline Po _1(Po p) { return p._1(); }
inline Po conj(Po p) { return p.conj(); }
inline Po lt(Po p) { return p.lt(); }
inline Po rt(Po p) { return p.rt(); }
inline Po rot(Po p, double a, const Po &o = Po()) { return p.rot(a, o); }
inline Po operator*(double k, const Po &p) { return p * k; }
inline Po operator/(double k, const Po &p) { return conj(p) * k / p.len2(); }
struct Line {
  Po a, b;
  Line(const Po &a = Po(), const Po &b = Po()) : a(a), b(b) {}
  Line(double x0, double y0, double x1, double y1)
      : a(Po(x0, y0)), b(Po(x1, y1)) {}
  Line(const Line &l) : a(l.a), b(l.b) {}
  Line(double A, double B, double C) {
    C = -C;
    if (!::sgn(A))
      a = Po(0, C / B), b = Po(1, C / B);
    else if (!::sgn(B))
      a = Po(C / A, 0), b = Po(C / A, 1);
    else
      a = Po(0, C / B), b = Po(1, (C - A) / B);
  }
  void in() { a.in(), b.in(); }
  inline friend istream &operator>>(istream &i, Line &p) {
    return i >> p.a >> p.b;
  }
  inline friend ostream &operator<<(ostream &o, Line p) {
    return o << p.a << "-" << p.b;
  }
  Line operator+(const Po &x) const { return Line(a + x, b + x); }
  Line operator-(const Po &x) const { return Line(a - x, b - x); }
  Line operator*(double k) const { return Line(a * k, b * k); }
  Line operator/(double k) const { return Line(a / k, b / k); }
  Po operator*(const Line &) const;
  Po d() const { return b - a; }
  double len2() const { return d().len2(); }
  double len() const { return d().len(); }
  double arg() const { return d().arg(); }
  int sgn(const Po &p) const { return dett(a, b, p); }
  int sgn(const Line &) const;
  bool sameSgn(const Po &p1, const Po &p2) const { return sgn(p1) == sgn(p2); }
  void getEquation(double &K, double &B) const {
    K = ::sgn(a.x, b.x) ? (b.y - a.y) / (b.x - a.x) : OO;
    B = a.y - K * a.x;
  }
  void getEquation(double &A, double &B, double &C) const {
    A = a.y - b.y, B = b.x - a.x, C = det(a, b);
  }
  Line &push(double r) {
    Po v = d()._1().lt() * r;
    a += v, b += v;
    return *this;
  }
};
inline double dot(const Line &l1, const Line &l2) {
  return dot(l1.d(), l2.d());
}
inline double dot(const Line &l, const Po &p) { return dot(l.a, l.b, p); }
inline double dot(const Po &p, const Line &l) { return dot(p, l.a, l.b); }
inline double det(const Line &l1, const Line &l2) {
  return det(l1.d(), l2.d());
}
inline double det(const Line &l, const Po &p) { return det(l.a, l.b, p); }
inline double det(const Po &p, const Line &l) { return det(p, l.a, l.b); }
inline double ang(const Line &l0, const Line &l1) {
  return ang(l0.d(), l1.d());
}
inline double ang(const Line &l, const Po &p) { return ang(l.a, l.b, p); }
inline double ang(const Po &p, const Line &l) { return ang(p, l.a, l.b); }
inline int Line::sgn(const Line &l) const { return dett(*this, l); }
inline Po Line::operator*(const Line &l) const {
  return a + d() * det(a, l) / det(*this, l);
}
inline Po operator&(const Po &p, const Line &l) {
  return l * Line(p, p + l.d().lt());
}
inline Po operator%(const Po &p, const Line &l) { return p & l * 2 - p; }
inline Line push(Line l, double r) { return l.push(r); }
struct Seg : public Line {
  Seg(const Po &a = Po(), const Po &b = Po()) : Line(a, b) {}
  Seg(double x0, double y0, double x1, double y1) : Line(x0, y0, x1, y1) {}
  Seg(const Line &l) : Line(l) {}
  Seg(const Po &a, double alpha) : Line(a, alpha) {}
  Seg(double A, double B, double C) : Line(A, B, C) {}
  inline int sgn(const Po &p) const;
  inline int sgn(const Line &l) const;
  inline bool qrt(const Seg &l) const;
  inline int sgn(const Seg &l) const;
};
inline int Seg::sgn(const Po &p) const {
  if (dett(p, a, b)) return -1;
  if (a == p || b == p) return 0;
  return -dott(p, a, b);
}
inline int Seg::sgn(const Line &l) const { return sgn(*this * l); }
inline bool Seg::qrt(const Seg &l) const {
  return min(a.x, b.x) <= max(l.a.x, l.b.x) &&
         min(l.a.x, l.b.x) <= max(a.x, b.x) &&
         min(a.y, b.y) <= max(l.a.y, l.b.y) &&
         min(l.a.y, l.b.y) <= max(a.y, b.y);
}
inline int Seg::sgn(const Seg &l) const {
  if (!qrt(l)) return -1;
  int d1 = dett(a, b, l.a), d2 = dett(a, b, l.b), d3 = dett(l.a, l.b, a),
      d4 = dett(l.a, l.b, b);
  if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 1;
  return ((!d1 && dott(l.a - a, l.a - b) <= 0) ||
          (!d2 && dott(l.b - a, l.b - b) <= 0) ||
          (!d3 && dott(a - l.a, a - l.b) <= 0) ||
          (!d4 && dott(b - l.a, b - l.b) <= 0))
             ? 0
             : -1;
}
inline double dist2(const Line &l, const Po &p) {
  return sqr(fabs(det(l.d(), p - l.a))) / l.len2();
}
inline double dist2(const Line &l1, const Line &l2) {
  return dett(l1, l2) ? 0 : dist2(l1, l2.a);
}
inline double dist2(const Seg &l, const Po &p) {
  Po pa = p - l.a, pb = p - l.b;
  if (dott(l.d(), pa) <= 0) return pa.len2();
  if (dott(l.d(), pb) >= 0) return pb.len2();
  return dist2(Line(l), p);
}
inline double dist2(const Seg &s, const Line &l) {
  Po v1 = s.a - l.a, v2 = s.b - l.a;
  double d1 = det(l.d(), v1), d2 = det(l.d(), v2);
  return sgn(d1) != sgn(d2) ? 0 : sqr(min(fabs(d1), fabs(d2))) / l.len2();
}
inline double dist2(const Seg &l1, const Seg &l2) {
  if (~l1.sgn(l2))
    return 0;
  else
    return min(dist2(l2, l1.a), dist2(l2, l1.b), dist2(l1, l2.a),
               dist2(l1, l2.b));
}
template <class T1, class T2>
inline double dist2(const T1 &a, const T2 &b) {
  return dist2(b, a);
}
}  // namespace CG
using namespace CG;
template <class T>
inline T &RD(T &x) {
  char c;
  while (!isdigit((c = getchar())))
    ;
  x = c - '0';
  while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  return x;
}
template <class T>
inline T &RDD(T &x) {
  char c;
  while ((c = getchar()), c != '-' && !isdigit(c))
    ;
  if (c == '-') {
    x = '0' - (c = getchar());
    while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  }
  return x;
}
inline double &RF(double &x) {
  char c;
  while ((c = getchar()), c != '-' && c != '.' && !isdigit(c))
    ;
  if (c == '-')
    if ((c = getchar()) == '.') {
      x = 0;
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
      x *= l;
    } else {
      x = '0' - c;
      while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
      if (c == '.') {
        double l = 1;
        while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
        x *= l;
      }
    }
  else if (c == '.') {
    x = 0;
    double l = 1;
    while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
    x *= l;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
    if (c == '.') {
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
      x *= l;
    }
  }
  return x;
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
long long last_ans;
int Case;
template <class T>
inline void OT(const T &x) {
  printf("%d\n", x);
}
const int N = int(1e6) + 9;
struct rec {
  int x;
  double h;
  bool operator<(const rec &rhs) const {
    return sgn(h, rhs.h) > 0 || sgn(h, rhs.h) == 0 && x < rhs.x;
  }
};
int n;
double l[N], r[N], h[N];
int fa[N];
void makeSet(int size) {
  for (int i = 0; i < size; i++) fa[i] = i;
  return;
}
int find(int x) {
  if (x != fa[x]) fa[x] = find(fa[x]);
  return fa[x];
}
priority_queue<rec> Q;
int main() {
  cin >> n;
  makeSet(n);
  for (int i = 0; i < n; ++i) {
    h[i] = RD();
    l[i] = r[i] = i;
    rec t;
    t.x = i;
    t.h = h[i];
    Q.push(t);
  }
  while (!Q.empty()) {
    rec t = Q.top();
    Q.pop();
    int l1 = find(t.x);
    if (l1 != 0) {
      int l0 = find(l1 - 1);
      if (sgn(h[l1], h[l0]) <= 0) {
        h[l0] = (h[l0] * (r[l0] - l0 + 1) + h[l1] * (r[l1] - l1 + 1)) /
                (r[l1] - l0 + 1);
        r[l0] = r[l1];
        fa[l1] = l0;
        rec tt;
        tt.x = l0;
        tt.h = h[l0];
        Q.push(tt);
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    int x = find(i);
    printf("%.9f\n", h[x]);
  }
}

```