/**************************************************
 * Fast Algorithm Template by Richard1211.
 * Please submit with C++14 or higher version.
 * Blog on Luogu: https://www.luogu.com.cn/blog/522539/
 * Blog on Byethost: http://Richard1211.byethost5.com/
 * Blog on RBTree's: https://Richard1211.rbtr.ee/
***************************************************/
//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC target("avx2")
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
//#include <bits/extc++.h>
#else
//#include <ext/rope>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#endif
//#ifdef __linux__
//#include<sys/mman.h>
//#include<sys/types.h>
//#include<fcntl.h>
//#include<unistd.h>
//#else
//#endif
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
#define YES io.write("YES\n")
#define Yes io.write("Yes\n")
#define yes io.write("yes\n")
#define NO io.write("NO\n")
#define No io.write("No\n")
#define no io.write("no\n")
#define RYES return YES,0
#define RYes return Yes,0
#define Ryes return yes,0
#define RNO return NO,0
#define RNo return No,0
#define Rno return no,0
#define Inline __inline__ __attribute__ ((always_inline))
#define Debug(x) if(Dbg){cerr << "Debug: " << __FUNCTION__ << "() @ " << __TIMESTAMP__ << " " << __FILE__ << " L" << __LINE__ << " " << #x" = " << (x) << "\n";}
//#define Memory() if(Dbg){fprintf(stderr,"Memory: %.3lf MB\n",(&End-&Beg)/1048576.0);}
//#define Time() if(Dbg){fprintf(stderr,"Time: %.3lf s\n",tims/CLOCKS_PER_SEC);}
bool Beg;mt19937 Rd(time(0));mt19937_64 Rand(time(0));constexpr double pi=3.141592653589793238462643383279;bool Dbg;
template<class T>Inline T Min(register T a,register T b){return a<b?a:b;}
template<class T>Inline T Max(register T a,register T b){return a>b?a:b;}
template<class T>Inline bool Cmin(register T&a,register T b){return a>b?(a=b,true):false;}
template<class T>Inline bool Cmax(register T&a,register T b){return a<b?(a=b,true):false;}
template<class T>Inline T Abs(register T a){return a>0?a:-a;}
template<class T>Inline T Lowbit(register T x){return(x)&(-x);}
template<class T>Inline void Swap(register T&a,register T&b){b^=a^=b^=a;}
template<class T>inline T Gcd(T a,T b){return b?Gcd(b,a%b):a;}
template<class T>inline T Lcm(T a,T b){return a*b/Gcd(a,b);}
template<class T>inline T Exgcd(T a,T b,T&x,T&y){if(b==0){x=1;y=0;return a;}T d=Exgcd(b,a%b,x,y);T t=x;x=y;y=t-a/b*y;return d;}
template<class T>inline T ExExgcd(T a,T b,T&x,T&y,T c){if(b==0){x=c;y=0;return a;}T d=ExExgcd(b,a%b,x,y,c);T t=x;x=y;y=t-a/b*y;return d;}
template<class T>inline T Ksc(T a,T b){if(a==0||b==0){return 0;}T ans=0;while(b){if(b&1){ans=a+ans;}a=a+a;b>>=1;}return ans;}
template<class T>inline T Ksc(T a,T b,T p){if(a==0||b==0){return 0;}T ans=0;while(b){if(b&1){ans=(a+ans)%p;}a=(a+a)%p;b>>=1;}return ans;}
template<class T>inline T Ksm(T a,T b,bool f=false){if(a==0){return 0;}if(b==0){return 1;}T ans=1;while(b){if(b&1){ans=!f?a*ans:Ksc(a,ans);}a=!f?a*a:Ksc(a,a);b>>=1;}return ans;}
template<class T>inline T Ksm(T a,T b,T p,bool f=false){if(a==0){return 0;}if(b==0){return 1%p;}T ans=1;while(b){if(b&1){ans=!f?a*ans%p:Ksc(a,ans,p);}a=!f?a*a%p:Ksc(a,a,p);b>>=1;}return ans;}
template<class T>inline T Inv(T x,T p){return Ksm(x,p-2,p);}
template<class T>inline T Fac(T n){if(n==0){return 1;}int ans=1;for(register int i=1;i<=n;++i){ans*=i;}return ans;}
template<class T>inline T Fac(T n,T p){if(n==0){return 1;}register long long ans=1;for(register int i=1;i<=n;++i){ans=ans*i%p;}return ans;}
template<class T>Inline int Popcount(T x,bool f=true){return f?__builtin_popcountll(x):__builtin_popcount(x);}
template<class T>Inline int Prebit(T x,bool f=true){return f?__builtin_clzll(x):__builtin_clz(x);}
template<class T>Inline int Sufbit(T x,bool f=true){return f?__builtin_ctzll(x):__builtin_ctz(x);}
template<class T>Inline int Lowone(T x,bool f=true){return f?__builtin_ffsll(x):__builtin_ffs(x);}
template<class T>Inline int Parity(T x,bool f=true){return f?__builtin_parityll(x):__builtin_parity(x);}
template<class T>Inline bool Isdigit(T ch){return ch>='0'&&ch<='9';}
template<class T>Inline bool Isletter(T ch){return ch>='A'&&ch<='Z'||ch>='a'&&ch<='z';}
template<class T>Inline bool Isupper(T ch){return ch>='A'&&ch<='Z';}
template<class T>Inline bool Islower(T ch){return ch>='a'&&ch<='z';}
template<class T>Inline char Tolower(T ch){return ch-'A'+'a';}
template<class T>Inline char Toupper(T ch){return ch-'a'+'A';}
template<class T>inline void Memset(T*d,long long n,long long s){for(register int i=0;i<=s-1;++i){d[i]=n;}}
template<class T>inline void Bug(T x,string name){cout<<name<<": "<<x<<endl;}
template<class T>inline void Bug(T x){cout<<x<<endl;}
template<class T>inline T Sin(register T degree){return sin(degree*(pi/180));}
template<class T>inline T Cos(register T degree){return cos(degree*(pi/180));}
template<class T>inline T Tan(register T degree){return tan(degree*(pi/180));}
template<class T>inline T Asin(register T degree){return asin(degree*(pi/180));}
template<class T>inline T Acos(register T degree){return acos(degree*(pi/180));}
template<class T>inline T Atan(register T degree){return atan(degree*(pi/180));}
template<class T>inline void Radixsort(register const int n,T*a,T*b){int r1[0x100],r2[0x100],r3[0x100],r4[0x100];memset(r1,0,sizeof(r1));memset(r2,0,sizeof(r2));memset(r3,0,sizeof(r3));memset(r4,0,sizeof(r4));register int i,tmp_int;register T*j,*tar;for(j=a+1,tar=a+n+1;j!=tar;++j){tmp_int=*(int*)j;++r1[tmp_int&0xff];++r2[(tmp_int>>8)&0xff];++r3[(tmp_int>>16)&0xff];++r4[tmp_int>>24];}for(i=1;i<=0xff;++i){r1[i]+=r1[i-1];r2[i]+=r2[i-1];r3[i]+=r3[i-1];r4[i]+=r4[i-1];}for(j=a+n;j!=a;--j){tmp_int=*(int*)j;b[r1[tmp_int&0xff]--]=*j;}for(j=b+n;j!=b;--j){tmp_int=*(int*)j;a[r2[(tmp_int>>8)&0xff]--]=*j;}for(j=a+n;j!=a;--j){tmp_int=*(int*)j;b[r3[(tmp_int>>16)&0xff]--]=*j;}for(j=b+n;j!=b;--j){tmp_int=*(int*)j;a[r4[tmp_int>>24]--]=*j;}}
template<class T>inline void Radixsort(register const int n,T*a,T*b,bool op){size_t size_of_type=sizeof(T);size_t num_of_buc=size_of_type>>1;unsigned**r=new unsigned*[num_of_buc];register int i,k;for(i=0;i<num_of_buc;++i){r[i]=new unsigned[0x10000];memset(r[i],0,0x10000*sizeof(unsigned));}register unsigned short tmp_us;register T*j,*tar;for(k=0;k<num_of_buc;++k){for(j=a+1,tar=a+n+1;j!=tar;++j){tmp_us=*(((unsigned short*)j)+k);++r[k][tmp_us];}}for(k=0;k<num_of_buc;++k){for(i=1;i<=0xffff;++i){r[k][i]+=r[k][i-1];}}for(k=0;k<num_of_buc;k+=0x2){i=k;for(j=a+n;j!=a;--j){tmp_us=*(((unsigned short*)j)+i);b[r[i][tmp_us]--]=*j;}i|=1;if(i==num_of_buc){break;}for(j=b+n;j!=b;--j){tmp_us=*(((unsigned short*)j)+i);a[r[i][tmp_us]--]=*j;}}for(int i=0;i<num_of_buc;i++){delete[]r[i];}delete[]r;}
template<class T>inline void Radixsort(register const int n,T*a,T*b,bool op1,bool op2){Radixsort(n,a,b,true);reverse(a+1,a+n+1);reverse(upper_bound(a+1,a+n+1,(T)(-0.0)),a+n+1);}
//inline int rd(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
//inline long long read(){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
//inline unsigned long long Read(){unsigned long long x=0;long long f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch-'0');ch=getchar();}return x*f;}
//inline bool wrt(int x,char ch='\n'){static char buf[64];static int len=-1;if(x<0){putchar('-');x=-x;}do{buf[++len]=x%10;x/=10;}while(x);while(len>=0){putchar(buf[len--]+'0');}putchar(ch);return true;}
//inline bool write(long long x,char ch='\n'){static char buf[64];static long long len=-1;if(x<0){putchar('-');x=-x;}do{buf[++len]=x%10;x/=10;}while(x);while(len>=0){putchar(buf[len--]+'0');}putchar(ch);return true;}
//inline bool Write(unsigned long long x,char ch='\n'){static char buf[64];static long long len=-1;if(x<0){putchar('-');x=-x;}do{buf[++len]=x%10;x/=10;}while(x);while(len>=0){putchar(buf[len--]+'0');}putchar(ch);return true;}
inline void OF(string s){string IN=s+".in";string OUT=s+".out";freopen(IN.c_str(),"r",stdin);freopen(OUT.c_str(),"w",stdout);}
inline void CF(string s){fclose(stdin);fclose(stdout);}
struct DEBUG{inline DEBUG&flush(){Dbg=true;return *this;}DEBUG(){flush();}}dbg;
#define FIO
struct IO{
#ifdef FIO
    const static int BUFSIZE=1<<20;
	char buf[BUFSIZE],obuf[BUFSIZE],*p1,*p2,*pp;
	inline char getchar(){return(p1==p2&&(p2=(p1=buf)+fread(buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++);}
	inline void putchar(char x){((pp-obuf==BUFSIZE&&(fwrite(obuf,1,BUFSIZE,stdout),pp=obuf)),*pp=x,pp++);}
	inline IO&flush(){fwrite(obuf,1,pp-obuf,stdout);fflush(stdout);return*this;}
	IO(){p1=buf,p2=buf,pp=obuf;}
	~IO(){flush();}
#else
    int(*getchar)()=&::getchar;
	int(*putchar)(int)=&::putchar;
	inline IO&flush(){fflush(stdout);return*this;};
#endif
	int k=2;
    string sep=" ";
	template<typename Tp,typename std::enable_if<std::is_integral<Tp>::value||std::is_same<Tp,__int128_t>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF)f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();s*=f;return ch!=EOF;}
	template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline int read(Tp&s){int f=1;char ch=getchar();s=0;while(!isdigit(ch)&&ch!=EOF&&ch!='.')f=(ch=='-'?-1:1),ch=getchar();while(isdigit(ch))s=s*10+(ch^48),ch=getchar();if(ch==EOF)return false;if(ch=='.'){Tp eps=0.1;ch=getchar();while(isdigit(ch))s=s+(ch^48)*eps,ch=getchar(),eps/=10;}s*=f;return ch!=EOF;}
	inline int read(char&c){char ch=getchar();c=EOF;while(isspace(ch)&&ch!=EOF)ch=getchar();if(ch!=EOF)c=ch;return c!=EOF;}
	inline int read(char*c){char ch=getchar(),*s=c;while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)*(c++)=ch,ch=getchar();*c='\0';return s!=c;}
	inline int read(string&s){s.clear();char ch=getchar();while(isspace(ch)&&ch!=EOF)ch=getchar();while(!isspace(ch)&&ch!=EOF)s+=ch,ch=getchar();return s.size()>0;}
	inline int getline(char*c,const char&ed='\n'){char ch=getchar(),*s=c;while(ch!=ed&&ch!=EOF)*(c++)=ch,ch=getchar();*c='\0';return s!=c;}
	inline int getline(string&s,const char&ed='\n'){s.clear();char ch=getchar();while(ch!=ed&&ch!=EOF)s+=ch,ch=getchar();return s.size()>0;}
	template<typename Tp=int>inline Tp read(){Tp x;read(x);return x;}
	template<typename Tp,typename...Ts>int read(Tp&x,Ts&...val){return read(x)&&read(val...);}
	template<typename Tp,typename enable_if<is_integral<Tp>::value>::type* =nullptr>IO&write(Tp x){if(x<0)putchar('-'),x=-x;static char sta[20];int top=0;do sta[top++]=x%10+'0',x/=10;while(x);while(top)putchar(sta[--top]);return*this;}
	inline IO&write(const string&str){for(char ch:str)putchar(ch);return*this;}
	inline IO&write(const char*str){while(*str!='\0')putchar(*(str++));return*this;}
	inline IO&write(char*str){return write((const char*)str);}
	inline IO&write(const char&ch){return putchar(ch),*this;}
	template<typename Tp,typename enable_if<is_floating_point<Tp>::value>::type* =nullptr>inline IO&write(Tp x){if(x>1e18||x<-1e18){write("[Floating point overflow]");throw;}if(x<0)putchar('-'),x=-x;const static long long pow10[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,100000000000000000,100000000000000000};const auto&n=pow10[k];long long whole=(int)x;double tmp=(x-whole)*n;long long frac=tmp;double diff=tmp-frac;if(diff>0.5){++frac;if(frac>=n)frac=0,++whole;}else if(diff==0.5&&((frac==0U)||(frac&1U)))++frac;write(whole);if(k==0U){diff=x-(double)whole;if((!(diff<0.5)||(diff>0.5))&&(whole&1))++whole;}else{putchar('.');static char sta[20];int count=k,top=0;while(frac){sta[top++]=frac%10+'0';frac/=10,count--;}while(count--)putchar('0');while(top)putchar(sta[--top]);}return*this;}
	template<typename Tp,typename...Ts>inline IO&write(Tp x,Ts...val){write(x);write(sep);write(val...);return*this;}
	template<typename...Ts>inline IO&writeln(Ts...val){write(val...);putchar('\n');return*this;}
	inline IO&writeln(void){putchar('\n');return*this;}
	template<typename Tp>inline IO&writeWith(Tp x,const string&s=" "){write(x),write(s);return*this;}
	inline IO&setsep(const string&s){return sep=s,*this;}
	inline IO&setprec(const int&K){return k=K,*this;}
}io;
//namespace mmapreader{
// 	 inline namespace __private__{int len=0,file=-1;char*addr,*nowp,*buff;}
// 	 inline void prepareread(string filename){file=open(filename.c_str(),O_RDONLY);len=(int)lseek(file,0,SEEK_END);addr=(char*)(mmap(0,len,PROT_READ,MAP_PRIVATE,file,0));close(file);buff=(char*)malloc(len*sizeof(char));memcpy(buff,addr,len);munmap(addr,len);nowp=buff;atexit([&buff](){free(buff);});}
// 	 inline void prepareread(FILE* fileptr){file=fileno(fileptr);len=(int)lseek(file,0,SEEK_END);addr=(char*)(mmap(0,len,PROT_READ,MAP_PRIVATE,file,0));buff=(char*)malloc(len*sizeof(char));memcpy(buff,addr,len);munmap(addr,len);nowp=buff;atexit([&buff](){free(buff);});}
// 	 template<typename T>T checked_read(){if(nowp-buff>=len)throw overflow_error("Read out of range!");static T n,s;n=0,s=1;while((*nowp>'9'||*nowp<'0')&&(nowp-buff<len)){if(*nowp=='-')s=-s;nowp++;}if(nowp-buff>=len)throw overflow_error("Read out of range!");while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len)){n=10*n+(*nowp-'0');nowp++;}return n*s;}
// 	 template<typename T>T unchecked_read(){static T n,s;n=0,s=1;while(*nowp>'9'||*nowp<'0'){if(*nowp=='-')s=-s;nowp++;}while(*nowp<='9'&&*nowp>='0'){n=10*n+(*nowp-'0');nowp++;}return n*s;}template<> string checked_read<string>(){if(nowp-buff>=len)throw overflow_error("Read out of range!");static string s;s="";while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r')&&(nowp-buff<len))nowp++;if(nowp-buff>=len)throw overflow_error("Read out of range!");while(!(*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r')&&(nowp-buff<len))s+=*(nowp++);return s;}
// 	 template<> string unchecked_read<string>(){static string s;s="";while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r'))nowp++;while(!(*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r'))s+=*(nowp++);return s;}
// 	 template<> char checked_read<char>(){if(nowp-buff>=len)throw overflow_error("Read out of range!");while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r')&&(nowp-buff<len))nowp++;if(nowp-buff>=len)throw overflow_error("Read out of range!");return *(nowp++);}
// 	 template<> char unchecked_read<char>(){while((*nowp==' '||*nowp==0||*nowp==-1||*nowp=='\n'||*nowp=='\t'||*nowp=='\r'))nowp++;return *(nowp++);}
// 	 template<>long double checked_read<long double>(){if(nowp-buff>=len)throw overflow_error("Read out of range!");static long double x,s,n,p;static char*oc;oc=nowp,x=0,s=1,n=0,p=1;while((*nowp>'9'||*nowp<'0')&&(nowp-buff<len)){if(*nowp=='-')s=-s;nowp++;}if(nowp-buff>=len)throw overflow_error("Read out of range!");while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len)){n=10*n+(*nowp-'0');nowp++;}if(nowp-buff>=len||(*nowp!='.'&&*nowp!='e'&&*nowp!='E'))return n*s;if(*nowp=='E'||*nowp=='e'){nowp++;while(*nowp=='-')p=-p,nowp++;if(nowp-buff>=len)return nowp=oc,n*s;while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len))x=10*x+(*nowp-'0'),nowp++;return n*powl(10.0l,x*p);}nowp++;while((*nowp<='9'&&*nowp>='0')&&(nowp-buff<len))x=10*x+(*nowp-'0'),nowp++;return n+x/powl(10.0l,floorl(log10l(x)+1));}
// 	 template<>long double unchecked_read<long double>(){static long double x,s,n,p;static char*oc;oc=nowp,x=0,s=1,n=0,p=1;while(*nowp>'9'||*nowp<'0'){if(*nowp=='-')s=-s;nowp++;}while((*nowp<='9'&&*nowp>='0')){n=10*n+(*nowp-'0');nowp++;}if(nowp-buff>=len||(*nowp!='.'&&*nowp!='e'&&*nowp!='E'))return n*s;if(*nowp=='E'||*nowp=='e'){nowp++;while(*nowp=='-')p=-p,nowp++;while(*nowp<='9'&&*nowp>='0')x=10*x+(*nowp-'0'),nowp++;return n*powl(10.0l,x*p);}nowp++;while(*nowp<='9'&&*nowp>='0')x=10*x+(*nowp-'0'),nowp++;return n+x/powl(10.0l,floorl(log10l(x)+1));}
// 	 template<>float checked_read<float>(){return checked_read<long double>();}template<>float unchecked_read<float>(){return unchecked_read<long double>();}
// 	 template<>double checked_read<double>(){return checked_read<long double>();}
// 	 template<>double unchecked_read<double>(){return checked_read<long double>();}
// 	 template<typename T>T checked_read(T& val){return val=checked_read<T>();}
// 	 template<typename T>T unchecked_read(T& val){return val=unchecked_read<T>();}
// 	 template<typename T,typename... args>T checked_read(T& val,args&... ar){return val=checked_read<T>(),checked_read(ar...);}
// 	 template<typename T,typename... args>T unchecked_read(T& val,args&... ar){return val=unchecked_read<T>(),unchecked_read(ar...);}
//}
//namespace mmapwriter{
// 	 int maxsize=5000000,floatpos=11;
// 	 bool truncate=true;
// 	 inline namespace __private__{int len=0,file=-1;char*addr,*nowp,*buff;}
// 	 inline void preparewrite(string filename){buff=(char*)malloc(maxsize*sizeof(char));nowp=buff;file=open(filename.c_str(),O_RDWR|O_CREAT,00777);atexit([&len,&file,&addr,&buff](){/*write(file,buff,len);*/lseek(file,len-1,SEEK_END);write(file,"",1);addr=(char*)mmap(0,len,PROT_READ|PROT_WRITE,MAP_SHARED,file,0);close(file);memcpy(addr,buff,len);munmap(addr,len);});}inline void prepare(FILE* fileptr){buff=(char*)malloc(maxsize*sizeof(char));nowp=buff;file=fileno(fileptr);atexit([&len,&file,&addr,&buff](){write(file,buff,len);});}
// 	 template<typename T>bool write(T val){if(val<0)write('-'),val=-val;if(val>9)write<T>(val/10);*nowp='0'+val%10,nowp++,len++;return true;}
// 	 template<> bool write<char>(char val){*nowp=val,nowp++,len++;return true;}
// 	 template<> bool write<const char*>(const char*val){for(int i=0;i<strlen(val);i++)*nowp=val[i],nowp++,len++;return true;}
// 	 template<> bool write<char*>(char*val){for(int i=0;i<strlen(val);i++)*nowp=val[i],nowp++,len++;return true;}
// 	 template<> bool write<string>(string val){for(int i=0;i<val.size();i++)*nowp=val[i],nowp++,len++;return true;}
// 	 template<>bool write<long double>(long double x){static int k=1;if(k==1)return k=0,write(x/10.0l),*(nowp++)=floorl(fmodl(x,10.0l))+'0',len++,(~floatpos||x-floorl(x)>1e-20l?len++,*(nowp++)='.',k--,write((floorl(x)-x)):1),k=1;if(truncate&&k==-1&&fabs(x)<=1e-20l)return len-=2;if(truncate&&k<1&&fabs(x)<=1e-20l)return len--;if(-k>floatpos)return true;if(fabs(x)<=1e-20l)return*(nowp++)='0';if(x<=-1.0l)return*(nowp++)='-',len++,write(-x);if(x<0.0l)return*(nowp++)=-x*10.0l+'0',len++,k--,write(fmodl(x,0.1l)*10.0l);if(x<10.0l)return*(nowp++)=x+'0',len++;return write(x/10.0l),*(nowp++)=floorl(fmodl(x,10.0l))+'0',len++;}
// 	 template<>bool write<float>(float x){return write<long double>(x);}
// 	 template<>bool write<double>(double x){return write<long double>(x);}
// 	 template<typename T>bool writeln(T val){return write(val),write('\n');}
// 	 template<typename T,typename... args>bool write(T val,args... ar){return write(val),write(' '),write(ar...);}
// 	 template<typename T,typename... args>bool writeln(T val,args... ar){return writeln(val),writeln(ar...);}
//}
//#ifdef __linux__
//#define read unchecked_read
//using namespace mmapreader;
//using namespace mmapwriter;
//inline int rd(){return unchecked_read<int>();}
//inline long long read(){return unchecked_read<long long>();}
//inline unsigned long long Read(){return unchecked_read<unsigned long long>();}
//inline bool wrt(int x,char ch='\n'){return write<int>(x),write<char>(ch),true;}
//inline bool write(long long x,char ch='\n'){return write<long long>(x),write<char>(ch),true;}
//inline bool Write(unsigned long long x,char ch='\n'){return write<unsigned long long>(x),write<char>(ch),true;}
//#else
inline int rd(){return io.read<int>();}
inline long long read(){return io.read<long long>();}
inline unsigned long long Read(){return io.read<unsigned long long>();}
inline bool wrt(int x,const string ch="\n"){return io.writeWith(x,ch),true;}
inline bool write(long long x,string ch="\n"){return io.writeWith(x,ch),true;}
inline bool Write(unsigned long long x,string ch="\n"){return io.writeWith(x,ch),true;}
//#endif
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.......RRRRRRRRRRRRRRRRRRRR...................PPPPPPPPPPPPPPPPPPPP...............................................
//.......RRRRRRRRRRRRRRRRRRRRRR.................PPPPPPPPPPPPPPPPPPPPPP.............................................
//.......RRRRRRRRRRRRRRRRRRRRRRR................PPPPPPPPPPPPPPPPPPPPPPPP...........................................
//.......RRRR.................RRRRR.............PPPP...............PPPPP...........................................
//.......RRRR.................RRRRR.............PPPP................PPPPP..........................................
//.......RRRR.................RRRRR.............PPPP................PPPPP..........................................
//.......RRRR...............RRRRR...............PPPP...............PPPPP...........................................
//.......RRRR............RRRRRR.................PPPP.............PPPPPP............................................
//.......RRRR............RRRRRR.................PPPP............PPPPPP.............................................
//.......RRRR........RRRRRR.....................PPPP........PPPPPP.................................................
//.......RRRRRRRRRRRRRRRRRR.....................PPPPPPPPPPPPPPPPPP.................................................
//.......RRRRRRRRRRRRRRRRRR.....................PPPPPPPPPPPPPPPP...................................................
//.......RRRR..........RRRR.....................PPPPP.................................+++................+++.......
//.......RRRR...........RRRR....................PPPPP.................................+++................+++.......
//.......RRRR.............RRRR..................PPPPP.................................+++................+++.......
//.......RRRR..............RRRR.................PPPPP...........................+++++++++++++++....+++++++++++++++.
//.......RRRR...............RRRR................PPPPP...........................+++++++++++++++....+++++++++++++++.
//.......RRRR................RRRR...............PPPPP.................................+++................+++.......
//.......RRRR.................RRRR..............PPPPP.................................+++................+++.......
//.......RRRR...................RRRR............PPPPP.................................+++................+++.......
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
//.................................................................................................................
constexpr long long N=1010;
long long n,m,ans;
long long x[N],y[N];
char s[N][N];
int main(){
	n=read();
	m=read();
	for(register int i=1;i<=n;++i){
		io.read(s[i]+1);
		for(register int j=1;j<=m;++j){
			s[i][j]^'1'?++x[i],++y[j]:0;
		}
	}
	for(register int i=1;i<=n;++i){
		x[i]?++ans:0;
	}
	for(register int i=1;i<=m;++i){
		y[i]?++ans:0;
	}
	for(register int i=1;i<=n;++i){
		for(register int j=1;j<=m;++j){
			x[i]==1&&y[j]==1&&(s[i][j]^'1')?--ans:0;
		}
	}
	return !write(ans+1);
}