其实一大半都是岛娘的,好吧几乎都是。。。
出处——岛娘的头文件
#define LOCAL /** ` Micro Mezzo Macro Flation -- Overheated Economy ., Ver 0.1 **/ #include <functional> #include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cstring> #include <cassert> #include <cstdio> #include <string> #include <vector> #include <bitset> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <list> #include <set> #include <map> using namespace std; #define REP(i, n) for (int i=0;i<int(n);++i) #define FOR(i, a, b) for (int i=int(a);i<int(b);++i) #define DWN(i, b, a) for (int i=int(b-1);i>=int(a);--i) #define REP_1(i, n) for (int i=1;i<=int(n);++i) #define FOR_1(i, a, b) for (int i=int(a);i<=int(b);++i) #define DWN_1(i, b, a) for (int i=int(b);i>=int(a);--i) #define REP_C(i, n) for (int n____=int(n),i=0;i<n____;++i) #define FOR_C(i, a, b) for (int b____=int(b),i=a;i<b____;++i) #define DWN_C(i, b, a) for (int a____=int(a),i=b-1;i>=a____;--i) #define REP_N(i, n) for (i=0;i<int(n);++i) #define FOR_N(i, a, b) for (i=int(a);i<int(b);++i) #define DWN_N(i, b, a) for (i=int(b-1);i>=int(a);--i) #define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i) #define FOR_1_C(i, a, b) for (int b____=int(b),i=a;i<=b____;++i) #define DWN_1_C(i, b, a) for (int a____=int(a),i=b;i>=a____;--i) #define REP_1_N(i, n) for (i=1;i<=int(n);++i) #define FOR_1_N(i, a, b) for (i=int(a);i<=int(b);++i) #define DWN_1_N(i, b, a) for (i=int(b);i>=int(a);--i) #define REP_C_N(i, n) for (n____=int(n),i=0;i<n____;++i) #define FOR_C_N(i, a, b) for (b____=int(b),i=a;i<b____;++i) #define DWN_C_N(i, b, a) for (a____=int(a),i=b-1;i>=a____;--i) #define REP_1_C_N(i, n) for (n____=int(n),i=1;i<=n____;++i) #define FOR_1_C_N(i, a, b) for (b____=int(b),i=a;i<=b____;++i) #define DWN_1_C_N(i, b, a) for (a____=int(a),i=b;i>=a____;--i) //#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it) #define ECH(it, A) for (__typeof(A.begin()) it=A.begin(); it != A.end(); ++it) #define REP_S(it, str) for (char*it=str;*it;++it) #define REP_G(it, u) for (int it=hd[u];it;it=suc[it]) #define DO(n) for ( int ____n ## __line__ = n; ____n ## __line__ -- ; ) #define REP_2(i, j, n, m) REP(i, n) REP(j, m) #define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m) #define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l) #define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l) #define ALL(A) A.begin(), A.end() #define LLA(A) A.rbegin(), A.rend() #define CPY(A, B) memcpy(A, B, sizeof(A)) #define INS(A, P, B) A.insert(A.begin() + P, B) #define ERS(A, P) A.erase(A.begin() + P) #define BSC(A, X) find(ALL(A), X) // != A.end() #define CTN(T, x) (T.find(x) != T.end()) #define SZ(A) int(A.size()) #define PB push_back #define MP(A, B) make_pair(A, B) #define PTT pair<T, T> #define fi first #define se second #define Rush int T____; RD(T____); DO(T____) #define Display(A, n, m) { \ REP(i, n){ \ REP(j, m) cout << A[i][j] << " "; \ cout << endl; \ } \ } #define Display_1(A, n, m) { \ REP_1(i, n){ \ REP_1(j, m) cout << A[i][j] << " "; \ cout << endl; \ } \ } #pragma comment(linker, "/STACK:36777216") //#pragma GCC optimize ("O2") #define Ruby system("ruby main.rb") #define Haskell system("runghc main.hs") #define Python system("python main.py") #define Pascal system("fpc main.pas") typedef long long LL; //typedef long double DB; typedef double DB; typedef unsigned UINT; typedef unsigned long long ULL; typedef vector<int> VI; typedef vector<char> VC; typedef vector<string> VS; typedef vector<LL> VL; typedef vector<DB> VD; typedef set<int> SI; typedef set<string> SS; typedef set<LL> SL; typedef set<DB> SD; typedef map<int, int> MII; typedef map<string, int> MSI; typedef map<LL, int> MLI; typedef map<DB, int> MDI; typedef pair<int, int> PII; typedef pair<int, bool> PIB; typedef pair<LL, LL> PLL; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; template<class T> inline T& RD(T &); template<class T> inline void OT(const T &); inline LL RD(){LL x; return RD(x);} inline char& RC(char &c){scanf(" %c", &c); return c;} inline char RC(){char c; return RC(c);} //inline char& RC(char &c){c = getchar(); return c;} //inline char RC(){return getchar();} inline DB& RF(DB &x){scanf("%lf", &x); return x;} inline DB RF(){DB x; return RF(x);} inline char* RS(char *s){scanf("%s", s); return s;} 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 DB& RF(DB &a, DB &b){RF(a), RF(b); return a;} inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &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 T> inline void RST(T &A){memset(A, 0, sizeof(A));} 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 T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));} 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(T &A){A.clear();} 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){REP(i, n) CLR(A[i]);} template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;} template<class T, class C> inline T& SRT(T &A, C B){sort(ALL(A), B); return A;} /** Add - On **/ const int dx4[] = {-1, 0, 1, 0}; const int dy4[] = {0, 1, 0, -1}; const int dx8[] = {-1, 0, 1, 0 , -1 , -1 , 1 , 1}; const int dy8[] = {0, 1, 0, -1 , -1 , 1 , -1 , 1}; const int dxhorse[] = {-2 , -2 , -1 , -1 , 1 , 1 , 2 , 2}; const int dyhorse[] = {1 , -1 , 2 , -2 , 2 ,-2 , 1 ,-1}; const int MOD = 1000000007; //int MOD = 99990001; const int INF = 0x3f3f3f3f; const LL INFF = 1LL << 60; const DB EPS = 1e-9; const DB OO = 1e15; const DB PI = acos(-1.0); //M_PI; // <<= ` 0. Daily Use ., template<class T> inline void checkMin(T &a,const T b){if (b<a) a=b;} template<class T> inline void checkMax(T &a,const T b){if (a<b) a=b;} template<class T> inline void checkMin(T &a, T &b, const T x){checkMin(a, x), checkMin(b, x);} template<class T> inline void checkMax(T &a, T &b, const T x){checkMax(a, x), checkMax(b, x);} template <class T, class C> inline void checkMin(T& a, const T b, C c){if (c(b,a)) a = b;} template <class T, class C> inline void checkMax(T& a, const T b, C c){if (c(a,b)) a = b;} 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;} inline int Ceil(int x, int y){return (x - 1) / y + 1;} // <<= ` 1. Bitwise Operation ., namespace BO{ inline bool _1(int x, int i){return bool(x&1<<i);} inline bool _1(LL x, int i){return bool(x&1LL<<i);} inline LL _1(int i){return 1LL<<i;} inline LL _U(int i){return _1(i) - 1;}; inline int reverse_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 LL reverse_bits(LL 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 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;} inline int low_idx(int x){return __builtin_ffs(x);} inline int low_idx(LL x){return __builtin_ffsll(x);} inline int high_idx(int x){return low_idx(reverse_bits(x));} inline int high_idx(LL x){return low_idx(reverse_bits(x));} inline int clz(int x){return __builtin_clz(x);} inline int clz(LL x){return __builtin_clzll(x);} inline int ctz(int x){return __builtin_ctz(x);} inline int ctz(LL x){return __builtin_ctzll(x);} inline int parity(int x){return __builtin_parity(x);} inline int parity(LL x){return __builtin_parityll(x);} inline int lg2(int a){return 31 - __builtin_clz(a);} inline int count_bits(int x){return __builtin_popcount(x);} inline int count_bits(LL x){return __builtin_popcountll(x);} } ;//using namespace BO; // <<= ` 2. Number theory ., namespace NT{ inline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;} inline int sum(int a, int b){a += b; if (a >= MOD) a -= MOD; return a;} inline void DEC(int &a, int b){a -= b; if (a < 0) a += MOD;} inline int dff(int a, int b){a -= b; if (a < 0) a += MOD; return a;} inline void MUL(int &a, int b){a = (LL)a * b % MOD;} inline int pdt(int a, int b){return (LL)a * b % MOD;} inline int sum(int a, int b, int c){return sum(sum(a, b), c);} inline int sum(int a, int b, int c, int d){return sum(sum(a, b), sum(c, d));} inline int pdt(int a, int b, int c){return pdt(pdt(a, b), c);} inline int pdt(int a, int b, int c, int d){return pdt(pdt(pdt(a, b), c), d);} inline int pow(int a, LL b){ int c(1); while (b){ if (b&1) MUL(c, a); MUL(a, a), b >>= 1; } return c; } template<class T> inline T pow(T a, LL b){ T c(1); while (b){ if (b&1) c *= a; a *= a, b >>= 1; } return c; } inline int _I(int b){ int a = MOD, x1 = 0, x2 = 1, q; while (true){ q = a / b, a %= b; if (!a) return (x2 + MOD) % MOD; DEC(x1, pdt(q, x2)); q = b / a, b %= a; if (!b) return (x1 + MOD) % MOD; DEC(x2, pdt(q, x1)); } } inline void DIA(int &a, int b){MUL(a, _I(b));} inline int qtt(int a, int b){return pdt(a, _I(b));} inline int phi(int n){ int res = n; for (int i=2;sqr(i)<=n;++i) if (!(n%i)){ DEC(res, qtt(res, i)); do{n /= i;} while(!(n%i)); } if (n != 1) DEC(res, qtt(res, n)); return res; } template <class T> T GCD(T a, T b) { return b ? GCD(b, a % b) : a; } template <class T> T extendGCD(T a, T b, T& x, T& y) { if(!b) return x = 1, y = 0, a; T res = extendGCD(b, a % b, x, y), tmp = x; x = y, y = tmp - (a / b) * y; return res; } template <class T> inline T inv(T w , T M){ if (M <= 0) return -1; T x , y , d; d = extendGCD(w , M , x , y); if (d != 1) return -1; x = ((x % M) + M) % M; return x; } } ;//using namespace NT; // <<= ' A. Random Event .. namespace RNG{ //srand((unsigned)time(NULL)); inline unsigned int rand16(){return (bool(rand()&1) << 15) | rand();} inline unsigned int rand32(){return (rand16() << 16) | rand16();} inline ULL rand64(){return ((LL)rand32() << 32) | rand32();} inline ULL random(LL l, LL r){return rand64() % (r - l) + l;} int dice(){return rand() % 6;} bool coin(){return bool(rand() % 2);} } ;//using namespace RNG; // <<= ' B. Clock namespace CLOCK{ DB s0, s1, rd, k, T; inline DB getTime(){ #ifdef LOCAL return 1.0 * clock() / CLOCKS_PER_SEC; #else timeval tv; gettimeofday(&tv, 0); return tv.tv_sec + tv.tv_usec * 1e-6; #endif } inline void st0(DB _T = 0.98){T = _T, s0 = getTime();} inline void st1(DB _k = 1.618){k = _k, s1 = getTime();} inline void ed1(){rd = getTime() - s1;} inline DB elapsed(){return getTime() - s0;} inline bool safe(){return elapsed() + rd * k < T;} } //using namespace CLOCK; // <<= ' C. Temp .. . template<class T> PTT operator+(const PTT &p1, const PTT &p2) { return PTT(p1.fi + p2.fi, p1.se + p2.se); } template<class T> PTT operator-(const PTT &p1, const PTT &p2) { return PTT(p1.fi - p2.fi, p1.se - p2.se); } template<class T> PTT operator*(const PTT &lhs, T k){ return PTT(lhs.fi * k, lhs.se * k); } namespace Math{ typedef long long typec; ///Lib functions typec GCD(typec a, typec b) { return b ? GCD(b, a % b) : a; } typec extendGCD(typec a, typec b, typec& x, typec& y) { if(!b) return x = 1, y = 0, a; typec res = extendGCD(b, a % b, x, y), tmp = x; x = y, y = tmp - (a / b) * y; return res; } ///for x^k typec power(typec x, typec k) { typec res = 1; while(k) { if(k&1) res *= x; x *= x, k >>= 1; } return res; } ///for x^k mod m typec powerMod(typec x, typec k, typec m) { typec res = 1; while(x %= m, k) { if(k&1) res *= x, res %= m; x *= x, k >>=1; } return res; } /*************************************** Inverse in mod p^t system ***************************************/ typec inverse(typec a, typec p, typec t = 1) { typec pt = power(p, t); typec x, y; y = extendGCD(a, pt, x, y); return x < 0 ? x += pt : x; } /*************************************** Linear congruence theorem x = a (mod p) x = b (mod q) for gcd(p, q) = 1, 0 <= x < pq ***************************************/ typec linearCongruence(typec a, typec b, typec p, typec q) { typec x, y; y = extendGCD(p, q, x, y); while(b < a) b += q / y; x *= b - a, x = p * x + a, x %= p * q; if(x < 0) x += p * q; return x; } /*************************************** prime table O(n) ***************************************/ const int PRIMERANGE = 1000000; int prime[PRIMERANGE + 1]; int getPrime() { memset (prime, 0, sizeof (int) * (PRIMERANGE + 1)); for (int i = 2; i <= PRIMERANGE; i++) { if (!prime[i]) prime[++prime[0]] = i; for (int j = 1; j <= prime[0] && prime[j] <= PRIMERANGE / i; j++) { prime[prime[j]*i] = 1; if (i % prime[j] == 0) break; } } return prime[0]; } /*************************************** get factor of n O(sqrt(n)) factor[][0] is prime factor factor[][1] is factor generated by this prime factor[][2] is factor counter need: Prime Table ***************************************/ ///you should init the prime table before int factor[100][3], facCnt; int getFactors(int x) { facCnt = 0; int tmp = x; for(int i = 1; prime[i] <= tmp / prime[i]; i++) { factor[facCnt][1] = 1, factor[facCnt][2] = 0; if(tmp % prime[i] == 0) factor[facCnt][0] = prime[i]; while(tmp % prime[i] == 0) factor[facCnt][2]++, factor[facCnt][1] *= prime[i], tmp /= prime[i]; if(factor[facCnt][1] > 1) facCnt++; } if(tmp != 1) factor[facCnt][0] = tmp, factor[facCnt][1] = tmp, factor[facCnt++][2] = 1; return facCnt; } typec combinationModP(typec n, typec k, typec p) { if(k > n) return 0; if(n - k < k) k = n - k; typec a = 1, b = 1, x, y; int pcnt = 0; for(int i = 1; i <= k; i++) { x = n - i + 1, y = i; while(x % p == 0) x /= p, pcnt++; while(y % p == 0) y /= p, pcnt--; x %= p, y %= p, a *= x, b *= y; b %= p, a %= p; } if(pcnt) return 0; extendGCD(b, p, x, y); if(x < 0) x += p; a *= x, a %= p; return a; } };//using namespace Math; // <<= ' 0. I/O Accelerator interface ., namespace Geo{ #define typec double const typec eps=1e-8; int dblcmp(double d){ if (fabs(d)<eps)return 0; return d>eps?1:-1; } int sgn(double a) {return a<-eps?-1:a>eps;} inline double sqr(double x){return x*x;} struct Point2D{ typec x,y; Point2D(){} Point2D(typec _x,typec _y):x(_x),y(_y){}; void input(){ scanf("%lf%lf",&x,&y); } void output(){ printf("%.2f %.2f\n",x,y); } bool operator==(Point2D a)const{ return dblcmp(a.x-x)==0&&dblcmp(a.y-y)==0; } bool operator<(Point2D a)const{ return dblcmp(a.x-x)==0?dblcmp(y-a.y)<0:x<a.x; } typec len(){ return hypot(x,y); } typec len2(){ return x*x+y*y; } Point2D operator + (const Point2D &A) const{ return Point2D(x + A.x , y + A.y); } Point2D operator - (const Point2D &A) const{ return Point2D(x - A.x , y - A.y); } Point2D operator * (const typec _x) const{ return Point2D(x * _x , y * _x); } typec operator * (const Point2D &A) const{ return x * A.x + y * A.y; } typec operator ^ (const Point2D &A) const{ return x * A.y - y * A.x; } Point2D operator / (const typec _p) const{ return Point2D(x / _p , y / _p); } typec distance(Point2D p){ return hypot(x-p.x,y-p.y); } Point2D add(Point2D p){ return Point2D(x+p.x,y+p.y); } Point2D sub(Point2D p){ return Point2D(x-p.x,y-p.y); } Point2D mul(typec b){ return Point2D(x*b,y*b); } Point2D div(typec b){ return Point2D(x/b,y/b); } typec dot(Point2D p){ return x*p.x+y*p.y; } typec det(Point2D p){ return x*p.y-y*p.x; } typec rad(Point2D a,Point2D b){ Point2D p=*this; return fabs(atan2(fabs(a.sub(p).det(b.sub(p))),a.sub(p).dot(b.sub(p)))); } Point2D trunc(typec r){ typec l=len(); if (!dblcmp(l))return *this; r/=l; return Point2D(x*r,y*r); } Point2D rotleft(){ return Point2D(-y,x); } Point2D rotright(){ return Point2D(y,-x); } Point2D rotate(Point2D p,typec angle)//ÈƵãpÄæʱÕëÐýתangle½Ç¶È { Point2D v=this->sub(p); typec c=cos(angle),s=sin(angle); return Point2D(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c); } }; typec cross(Point2D a,Point2D b,Point2D c){ return (b.sub(a)).det(c.sub(a)); } }using namespace Geo; template<class T> inline T& RD(T &x){ //cin >> x; //scanf("%d", &x); char c; for (c = getchar(); c < '0'; c = getchar()); x = c - '0'; for (c = getchar(); '0' <= c && c <= '9'; c = getchar()) x = x * 10 + c - '0'; //char c; c = getchar(); x = c - '0'; for (c = getchar(); c >= '0'; c = getchar()) x = x * 10 + c - '0'; return x; } int ____Case; template<class T> inline void OT(const T &x){ //if (x == -1) printf("Case %d: NO\n", ++____Case); //else printf("Case %d: %d\n", ++____Case, x); //printf("%I64d\n", x); //printf("%.2lf\n", x); printf("%d\n", x); //cout << x << endl; } /* .................................................................................................................................. */