#include #define gc getchar_unlocked #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define sz size() #define ff first #define ss second #define all(x) (x).begin(),(x).end() #define mset(m,v) memset(m,v,sizeof(m)) #define ABS(a,b) ((a) < (b) ? (b)-(a) : (a)-(b)) #define max(a,b) a>b?a:b #define min(a,b) a vi; typedef vector vl; typedef stack sti; typedef stack stc; typedef queue qi; typedef pair ii; typedef pair il; typedef pair si; typedef pair ss; typedef pair ssi; typedef pair is; typedef pair iii; typedef vector vvi; typedef vector vii; typedef vector vil; typedef vector vsi; typedef vector vis; typedef vector vvii; typedef vector vs; typedef vector vss; typedef vector vssi; typedef map mci; typedef unordered_map umsi; inline int inp() { int NR=0,sign=1; char c=gc(); while( c < 48 || c > 57 ){if(c=='-')sign=0; c=gc();} while(c>47 && c< 58) { NR = (NR << 3) + (NR << 1) + (c - 48); c=gc(); } return (sign?NR:(-NR)); } inline int inpl() { ll NR=0; int sign=1; char c=gc(); while( c < 48 || c > 57 ){if(c=='-')sign=0; c=gc();} while(c>47 && c< 58) { NR = (NR << 3) + (NR << 1) + (c - 48); c=gc(); } return (sign?NR:(-NR)); } inline int in() { int NR=0; char c=gc(); while( c < 48 || c > 57 ){c=gc();} while(c>47 && c< 58) { NR = (NR << 3) + (NR << 1) + (c - 48); c=gc(); } return NR; } inline ll inl() { ll NR=0; char c=gc(); while( c < 48 || c > 57 ){c=gc();} while(c>47 && c< 58) { NR = (NR << 3) + (NR << 1) + (c - 48); c=gc(); } return NR; } inline bool inb() { char c=gc(); while( c < 48 || c > 57 ){c=gc();} return(c=='0'?0:1); } inline ll modpow(ll base, ll exp, ll modulus) { base %= modulus; ll result = 1; while (exp) { if (exp & 1) result = (result * base) % modulus; base = (base * base) % modulus; exp >>= 1; } return result; } inline ll ModP(ll base, ll exp) { base %= MOD; ll result = 1; while (exp) { if (exp & 1) result = (result * base) % MOD; base = (base * base) % MOD; exp >>= 1; } return result; } inline ll gcd(ll u, ll v) { if (u == v) return u; if (!u) return v; if (!v) return u; if (~u & 1) { if (v & 1) return gcd(u >> 1, v); else return gcd(u >> 1, v >> 1) << 1; } if (~v & 1) return gcd(u, v >> 1); if (u > v) return gcd((u - v) >> 1, v); return gcd((v - u) >> 1, u); } inline ll rev_num(ll n) { ll r=n%10; for(;n/=10;r=r*10+n%10); return r; } inline string itos(int i) { string s="",nm="0123456789"; if(i==0) s="0"; while(i) { s+=nm[i%10]; i/=10; } return s; } inline string revstr (string a) { string b=""; int l=a.length(); while(l--) { b+=a[l]; } return b; } bool pri[pnu]={1,1,0,0}; vl prm; int pn[nu]={0,0,1}; inline void prime_init() { ll i,j; for(i=3;i*i1) c++; return(c); } inline int nf(int s) { if(s==1) return 1; int j,x,f=1; int c=1; for(j=0;((x=prm[j])*prm[j])<=s;c=1,j++) { if(!(s%x)) { while(!(s%x)) { s/=x; c++; } f=f*c; } } if(s>1) { f=f<<1; } return(f); } int nCrModpDP(int n, int r, int p) { int C[r+1]; //memset(C, 0, sizeof(C)); C[0] = 1; for (int i = 1; i <= n; i++) { for (int j = min(i, r); j > 0; j--) C[j] = (C[j] + C[j-1])%p; } return C[r]; } int nCrModp(int n, int r, int p) { if (r==0) return 1; int ni = n%p, ri = r%p; return (nCrModp(n/p, r/p, p) * nCrModpDP(ni, ri, p)) % p; } inline bool subseq(string &sub, string &big,int m, int n) { int i,j; for(i=j=0;i