#include #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define vec_input(v) for(auto it=v.begin();it!=v.end();it++){cin>>*it;} #define vec_output(v) for(auto it=v.begin();it!=v.end();it++){if(it!=v.begin())cout<<" ";cout<<*it;}cout<T digitsum(T n); template bool isPrime(T n); template vector> prime_factor(T n); long long int intpow(long long int,long long int); template T intlog(T); long long int combination(long long int,long long int); long long int series_sum(long long int); int main(){ int n,k; cin>>n>>k; cout<<((n>=k)?intpow(2,n-k):0)<>n; vector vec(n),vec2(n); rep(i,n){ cin>>vec[i]; maxv=max(maxv,vec[i]); } ll ans=0; rep(i,n){ vec2[i]=maxv-vec[i]; if(vec2[i]>maxv2){ maxv2=vec2[i]; } } while(maxv2>=1){ ans++; } }*/ /*int main(){ int x,i; cin>>x; if(360%x==0)cout<<360/x<>n>>m; a=n/m; b=n-a*m; rep(i,m-b){ cout< vec(4); vec_input(vec); sort(all(vec)); cout<>t; rep(l,t){ cin>>a>>b>>c; maxv=max(a,max(b,c)); minv=min(a,min(b,c)); mid=a+b+c-minv-maxv; YN(maxv*maxv==minv*minv+mid*mid); } }*/ /*int main(){ int a,b; while(scanf("%d %d",&a,&b)!=EOF){ cout< vec(10); vec_input(vec); sort(rall(vec)); rep(i,3){ cout<>n; cout<<(ll)(n*1.5)<>n>>x; vector vec(n); rep(i,n){ cin>>vec[i]; if(i==0) ans=abs(vec[i]-x); else ans=__gcd(ans,abs(vec[i]-x)); } cout<>n>>k; vector vec(n); vec_input(vec); sort(all(vec)); double ans=0; for(int i=n-k;i>s>>t; if(s=="Sat"||s=="Sun"){ans++; if(t=="Sat"||t=="Sun")ans++; } cout<<"8/"<>t; rep(l,t){ cin>>n; YN(n%4==0); if(n%4==0){ a=0,b=0; rep(i,n/2){ cout<<2*(i+1)<<" "; a+=2*(i+1); } rep(i,n/2-1){ cout<<2*(i+1)-1<<" "; b+=2*(i+1)-1; } cout<>s; reverse(all(s)); rep(i,s.length()){ if(i%2==0)a+=stoi(s.substr(i,1)); else b+=stoi(s.substr(i,1)); } cout<>t; rep(l,t){ cin>>n; a=0,b=0; a+=pow(2,n); for(int i=1;i=n/2)b+=pow(2,i); } cout<>t; ll a,b; rep(l,t){ cin>>a>>b; cout<>a>>b; if(a>b)ans=0; else if(a==b)ans=4; else if(a*a>b*b/4)ans=8; else if(a*a==b*b/4)ans=4; else ans=0; cout<>s; ll ans=0,d=0,m=0,p=0,l=0,r=0,minv=0; rep(i,s.length()){ if(s[i]=='>'){ if(d==1){ l=abs(minv)+(p-m); ans+=max(r,l); ans+=abs(minv)*(p+m-1); d=0; m=0; p=0; }else{ m++; minv=min(minv,-m); } }else{ d=1; p++; } cerr<>a>>b; if(b==1){ ans=1; }else{ vector vec; for(int i=2;i<=a;i++){ if(a%i==0)vec.push_back(i); } rep(i,vec.size()){ if(vec[i]%b==0){ ans=1; break; } } } YN(ans); }*/ /*int main(){ ll a,b,i; cin>>a>>b; for(i=0;a<=b;i++){ a=3*a; b=2*b; } cout<>n>>m; if(m>2*n){ ans+=n; m-=2*n; ans+=m/4; }else{ ans+=m/2; } cout<>t; rep(i,t){ cin>>a; cur-=a; cerr<>a; cur+=a; maxv=max(maxv,cur); } cout<>x>>y>>n; if(x<=n&&y<=n)n-=2; else if(x<=n)n--; else if(y<=n)n--; cout<>s; int j=0; rep(i,s.length()){ if(s[i]==t[j]){ j++; } } YN(t.length()==j); }*/ /*int main(){ ll n; cin>>n; vector vec(n); vec_input(vec); list list; rep(i,n){ if(i%2==0){ list.push_back(vec[i]); }else{ list.push_front(vec[i]); } } if(n%2==1)reverse(all(list)); vec_output(list); }*/ /*int main(){ ll n,p,ans=1,counter=0,j; cin>>n>>p; vector> vec=prime_factor(p); rep(i,vec.size()){ if(vec[i].second>=n){ for(j=1;j*n<=vec[i].second;j++){} ans*=pow(vec[i].first,j-1); } } cout<>k>>n>>w; while(ansmoney? 0:money-n)< vec(3); vec[0].x=2; vec[0].y=8; vec[1].x=3; vec[1].y=9; vec[2].x=7; vec[2].y=9; point p1,p2; ll n; cin>>n; rep(i,n){ cin>>p1.x>>p1.y>>p2.x>>p2.y; rep(j,3){ if(p1.x==vec[j].x&&p1.y==vec[j].y){ vec[j].x=p2.x; vec[j].y=p2.y; } } } YN(vec[0].x==5&&vec[0].y==8 &&vec[1].x==4&&vec[1].y==8 &&vec[2].x==6&&vec[2].y==8); }*/ /*int main(){ ll r,g,b,n,ans=0,b2; cin>>r>>g>>b>>n; for(int i=0;i*r<=n;i++){ for(int j=0;j*g<=n;j++){ b2=n-i*r-j*g; if(b2<0)break; if(b2%b==0){ //cerr<>n; vector vec(n); vec_input(vec); sort(vec.rbegin(),vec.rend()); vector time(2,0); rep(i,n){ sort(all(time)); time[0]+=vec[i]; } sort(all(time)); cout<>a>>b>>c>>d; ans=b-a+1; long long int e=0; e+=(b/c)-(a/c); if(a%c==0)e++; e+=(b/d)-(a/d); if(a%d==0)e++; long long int f=c*d/__gcd(c,d); e-=(b/f)-(a/f); if(a%(f)==0)e--; cout<>s; int ans=1; rep(i,s.length()){ if(s[i]!='4'&&s[i]!='7'){ ans=0; break; } } int n=stoi(s); int d=1,a,digit,counter=0; for(int i=4;i<=n;i++){ if(n%i==0){ d=1; digit=intlog(i)+1; cerr<>p; //0.5=p*n; double ans=p/(1-p); printf("%.8lf\n",ans); }*/ /*int main(){ ll n; cin>>n; ll maxv=n,i=0; while(n!=1){ i++; if(n%2==0)n/=2; else n=3*n+1; if(n>maxv){ maxv=n; } } cout<>n; point input,sum; sum.x=0; sum.y=0; sum.z=0; rep(i,n){ cin>>input.x>>input.y>>input.z; sum.x+=input.x; sum.y+=input.y; sum.z+=input.z; } YN(sum.x==0&&sum.y==0&&sum.z==0); }*/ /*int main(){ ll n,m,ans; cin>>n>>m; if(n==1||m==1){ if(n==1&&m==1)ans=1; else if(n==1)ans=m-2; else if(m==1)ans=n-2; }else if(n==2||m==2){ ans=0; }else{ ans=(m-2)*(n-2); } cout<>a>>b; if(a%2==1)odd++; } if(odd%2==0)ans=1; cout<<(ans?":-)":":-(")<>s; set set; rep(i,s.length()){ set.insert(s[i]); } cout<<(set.size()%2==0?"CHAT WITH HER!":"IGNORE HIM!")<>n>>k; vector vec(n); vector p(n); rep(i,n){ cin>>vec[i]; p[i]=(double)series_sum(vec[i])/vec[i]; } double ans=0,value=0; rep(i,n){ if(i<=k-1){ value+=p[i]; ans=value; }else{ value+=p[i]-p[i-k]; ans=max(ans,value); } } printf("%.8lf\n",ans); }*/ /*int main(){ int n; cin>>n; printf("%.8lf\n",(double)1/n); }*/ /*int main(){ int n; cin>>n; string s; cin>>s; ll ans=0; rep(i,n-1){ if(s[i]==s[i+1])ans++; } cout< map; unordered_set set; ll n; cin>>n; vector vec(n); rep(i,n){ cin>>vec[i]; if(set.count(vec[i])){ map[vec[i]]++; }else{ set.insert(vec[i]); map[vec[i]]=1; } } ll ans=0; for(auto it=set.begin();it!=set.end();it++){ ans+=(ll)(map[*it]*(map[*it]-1))/2; } rep(i,n){ cout< bunsi,bunbo; long long int ans=1; b=min(b,a-b); for(int i=0;i=2)bunbo.push(b-i); } while(bunsi.size()!=0||bunbo.size()!=0){ ans*=bunsi.front(); bunsi.pop(); if(ans%bunbo.front()==0){ ans/=bunbo.front(); bunbo.pop(); } } return ans; } /*int main(){ int a,b,m; cin>>a>>b>>m; vector fri(a),ran(b); con_input(fri); con_input(ran); int x,y,c,minv; rep(i,m){ cin>>x>>y>>c; if(i==0)minv=fri[x-1]+ran[y-1]-c; else{ minv=min(minv,fri[x-1]+ran[y-1]-c); } } sort(all(fri)); sort(all(ran)); minv=min(minv,fri[0]+ran[0]); cout<>h; ll ans=0,d=1; while(h>=1){ h/=2; ans+=d; d*=2; } cout<>h>>w>>n; cout<<(int)floor((n+max(h,w)-1)/max(h,w))<>a>>b; cout<<(a*b==15?"*":a+b==15?"+":"x")<>n; vector> vec(n); string s,t; rep(i,n){ cin>>t>>x; vec[i]=make_pair(t,x); } cin>>s; int ans=0; rep(i,n){ if(d==1){ ans+=vec[i].second; } if(vec[i].first==s){ d=1; } } cout<>a>>b; cout<>n; rep(i,n){ cin>>x; if(x-1!=j){ ans++; }else{ j++; } } cout<<(ans==n?-1:ans)<>m1>>d1>>m2>>d2; cout<<(m1!=m2?1:0)<>s; int ans=0,j; rep(i,s.length()){ if(i==0){ str=s.substr(0,1); ans++; }else{ j=1; if(i==s.length()-1&&s.substr(i,j)==str)break; while(s.substr(i,j)==str){ j++; } str=s.substr(i,j); i+=j-1; ans++; } } cout<>n>>a>>b; ll ans; if((b-a)%2==0)ans=(b-a)/2; else{ d1=a-1; d2=n-b; ans=min(d1,d2)+1+(b-a-1)/2; } cout<>n; vector vec(n); vector vec2(n,true); con_input(vec); rep(i,n-1){ if(vec[i]-vec[i+1]>=2){ ans=0; break; } if(vec[i]-vec[i+1]==1){ vec[i]--; vec2[i]=false; j=i; while(j>=1&&vec[j-1]>vec[j]){ if(vec2[j-1]){ vec[j-1]--; vec2[j-1]=false; j--; }else{ ans=0; break; } } } if(ans==0)break; } cout<<(ans?"Yes":"No")<>s; char c='2'; int counter=0,ans=0; rep(i,s.length()){ if(s[i]!=c){ counter=1; c=s[i]; }else{ counter++; if(counter>=7){ ans=1; break; } } } cout<<(ans?"YES":"NO")<='a'&&s[i]<='z')){ ans=0; break; } if(i%2==1&&s[i]!=' '){ ans=0; break; } } cout<<(ans?"Yes":"No")< T digitsum(T n){ string s=to_string(n); T sum=0; T d=1; for(T e=0;e bool isPrime(T n){ if(n<=1)return false; if(n==2)return true; if(n%2==0)return false; for(T q=3;q*q<=n;q+=2){ if(n%q==0)return false; } return true; } template vector> prime_factor(T n) { vector> ret; if(n%2==0){ T tmp = 0; while (n % 2 == 0) { tmp++; n /= 2; } ret.push_back(make_pair(2, tmp)); } for (T i = 3; i*i <= n; i+=2) { if(n%i==0){ T tmp = 0; while (n % i == 0) { tmp++; n /= i; } ret.push_back(make_pair( i, tmp)); } } if (n != 1) ret.push_back(make_pair(n, 1)); return ret; } long long int intpow(long long int x,long long int n){ long long int ans=1; for(int i=0;iT intlog(T x){ string a=to_string(x); return a.length()-1; }