#include <string>
#include <stack>
#include <cstdio>
#include <cstdarg>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <cmath>

namespace meow{

  inline std::string stringPrintf(char const * fmt, ...){
    char str[8192];
    va_list args;
    va_start(args, fmt);
    vsnprintf(str, 8192, fmt, args);
    va_end(args);
    return std::string(str);
  }

  inline std::string stringReplace(std::string str,
                                   std::string const& from,
                                   std::string const& to){
    std::string out = str;
    int len = from.length();
    for(size_t pos; (pos = out.find(from)) != std::string::npos; ){
      out.replace(pos, len, to);
    }
    return out;
  }

  inline bool cstringEndWith(char const* str, int n, ...){
    int len = strlen(str);
    va_list args;
    va_start(args, n);
    for(int i = 0; i < n; i++){
      char const* arg = va_arg(args, char const*);
      int arglen = strlen(arg);
      if(arglen <= len && strcmp(str + len - arglen, arg) == 0){
        return true;
      }
    }
    va_end(args);
    return false;
  }

  inline void debugPrintf_(char const* file,
                           char const* func,
                           size_t      line,
                           char const* msg){
#ifdef    DEBUG
    fprintf(stderr, "%s[%d] %s >> %s", file, line, func, msg);
#endif // DEBUG
  }

  inline void messagePrintf(int level_change, char const* fmt, ...){
    static int      level =  0;
    static int last_level = -5;
    char str[8192];
    va_list args;
    va_start(args, fmt);
    vsnprintf(str, 8192, fmt, args);
    va_end(args);
    if(last_level == 1 && level_change == -1){
      printf(" ...%s\n", str);
    }else{
      if(last_level == 1) printf("\n");
      int level2 = level + (level_change == -1 ? -1 : 0);
      for(int i = 0; i < level2; i++) printf("|  ");
      printf("%s%s", (level_change == -1 ? "..." : ""), str);
      if(level_change != 1) printf("\n");
    }
    level     += level_change;
    last_level = level_change;
    fflush(stdout);
  }

  inline double noEPS(double value, double eps){
    return (fabs(value) <= fabs(eps) ? 0 : value);
  }

  inline double normalize(double lower, double upper, double value){
    return (value - lower) / (upper - lower);
  }

  inline double denormalize(double lower, double upper, double ratio){
    return lower + ratio * (upper - lower);
  }

  inline double ratioMapping(double l1, double u1, double m1,
                             double l2, double u2){
    return denormalize(l2, u2, normalize(l1, u1, m1));
  }

  inline bool filenameCompare(std::string const& f1, std::string const& f2){
    char const* s1 = f1.c_str();
    char const* s2 = f2.c_str();
    int l1 = f1.length();
    int l2 = f2.length();
    int i1, i2;
    for(i1 = i2 = 0; i1 < l1 || i2 < l2; i1++, i2++){
      if(isdigit(s1[i1]) && isdigit(s2[i2])){
        int n1 = atoi(s1 + i1);
        int n2 = atoi(s2 + i2);
        if(n1 != n2){
          return (n1 < n2);
        }
        while(i1 + 1 < l1 && isdigit(s1[i1 + 1])) i1++;
        while(i2 + 1 < l2 && isdigit(s2[i2 + 1])) i2++;
      }else{
        if(s1[i1] != s2[i2]){
          return s1[i1] < s2[i2];
        }
      }
    }
    return false;
  }
  template<class T>
  inline T inRange(T const& mn, T const& mx, T const& v){
    return std::min(mx, std::max(mn, v));
  }
  template<class T>
  inline T squ(T const& x){
    return x * x;
  }
  template<class T>
  inline double average( T const& beg, T const& end, double sigs){
    int N = 0;
    double av = 0;
    for(T it = beg; it != end; it++, N++){
      av += *it;
    }
    av /= N;
    double sig = 0;
    for(T it = beg; it != end; it++){
      sig += (*it - av) * (*it - av);
    }
    sig = sqrt(sig / N);
    double lower = av - sig * sigs, upper = av + sig * sigs;
    double ret = 0, retn = 0;
    for(T it = beg; it != end; it++){
      if(lower <= *it && *it <= upper){
        ret += *it;
        retn++;
      }
    }
    return ret / retn;
  }
  template<class T>
  inline double average( T const& beg, T const& end, T const& p, double sigs){
    int N = 0;
    double ps = 0;
    for(T it = beg, ip = p; it != end; it++, N++, ip++){
      ps += *ip;
    }
    double av = 0;
    for(T it = beg, ip = p; it != end; it++, ip++){
      av += *it * *ip / ps;
    }
    double sig = 0;
    for(T it = beg, ip = p; it != end; it++, ip++){
      sig += *ip / ps * (*it - av) * (*it - av);
    }
    sig = sqrt(sig);
    double lower = av - sig * sigs, upper = av + sig * sigs;
    double ret = 0, retn = 0;
    for(T it = beg, ip = p; it != end; it++, ip++){
      if(lower <= *it && *it <= upper){
        ret  += *it * *ip;
        retn += *ip;
      }
    }
    if(retn <= 1e-10) return av;
    return ret / retn;
  }
}