#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;
}
}
