namespace fast_IO {
#define IOSIZE 100000
	unsigned int precision = 6, POW[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
	char obuf[IOSIZE], *p3 = obuf;
#if defined(ONLINE_JUDGE) or defined(FastIO)
	char ibuf[IOSIZE], *p1 = ibuf, *p2 = ibuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#endif 
	template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !(ch>47 and ch<58) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while ((ch>47 and ch<58)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
	template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
	inline bool read(char &s) { while (s = getchar(), isspace(s) and s != EOF); return s != EOF; }
	inline void print(char x) { putchar(x); }
	inline bool read(char *s) { char ch; while (ch = getchar(), (ch<33) && ch != EOF); if (ch == EOF) return false; while (!(ch<33) and (ch != EOF)) *s++ = ch, ch = getchar(); *s = '\0'; return true; }
	inline void print(char *x) { while (*x) putchar(*x++); }
	inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
	inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), (ch<33) and ch != EOF); if (ch == EOF) return false; while (!(ch<33)) s += ch, ch = getchar(); return true; }
	inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
	inline bool read(bool &b) { char ch; while(ch=getchar(), (ch<33) and ch != EOF); return ch == EOF ?false :(b=ch^48, true); }
	inline void print(bool b) { putchar(b+48); }
	inline bool read(double &x) { char ch = getchar(); int f = 1; for(x=0; (ch<48 or 57<ch) and (ch != EOF); ch=getchar()) if(ch == '-')	f = -1; if(ch == EOF)	return false; for(x=0; 47<ch and ch<58; ch=getchar())	x = x*10 + (ch^48); if(ch != '.')	return x *= f, true; double y = 0.1; for(ch=getchar(); 47<ch and ch<58; ch=getchar())	x += y*(ch^48), y /= 10; return x *= f, true; }
	inline void print(double x) { if(x < 0) putchar('-'), x = -x; if(!precision) print((unsigned long long)(x-(unsigned long long)(x)>=0.5 ?x+1 :x)); else { unsigned long long xx = x; double y = ((x-xx)*POW[precision]); unsigned long long yy = (y-(unsigned long long)(y)>=0.5 ?y+1 :y); if(yy == POW[precision])	xx++, yy = 0; print(xx), putchar('.'); for(int j=precision-1; ~j; j--)	putchar(48+yy/POW[j]%10); } }
	template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
	template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
	template<typename T> inline T read() { T a; return read(a), a; }
	struct Fast_IO { 
		bool flag = 1;
		inline ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } 
		inline void SetPrecision(int x) { if(x > 9)	throw std::runtime_error("Precision too high!"); else if(x < 0) throw std::runtime_error("Precision too low!"); else precision = x; }
		inline operator bool() { return flag; }
	} io;
	Fast_IO& operator >> (Fast_IO &io, char *b) { return io.flag &= read(b), io; }
	template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return io.flag &= read(b), io; }
	template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
}
#define int long long
using namespace fast_IO;