#include <fstream>
using namespace std;
ifstream fi("evaluare.in");
ofstream fo("evaluare.out");
char s[100003];
int i;
int expresie();
int termen(){ //termen=(expresie) sau termen=213
int rez=0;
if(s[i]=='('){ //daca este ceva de genul (.......)
i++; //paranteza (
rez=expresie();
i++; //paranteza )
}
else //daca este ceva de genul 12372 (un numar)
while(s[i]>='0' && s[i]<='9'){ rez=rez*10+s[i]-'0'; i++; }
return rez;
}
int factor(){ //factor=termen*termen/termen*termen/termen.....
int rez=termen(); //se calculeaza primul termen din cadrul factorului
while(s[i]=='*' || s[i]=='/')
if(s[i]=='*'){ i++; rez*=termen(); } //pt "*" => urmeaza un termen(care se va inmultii!)
else{ i++; rez/=termen(); } //pentru div =>analog
return rez;
}
int expresie(){ //expresie =factor+factor-factor+factor-factor+.....
int rez=factor(); //se calculeaza primul factor
while(s[i]=='+' || s[i]=='-')
if(s[i]=='+'){ i++; rez+=factor(); }//pt "+" => urmeaza un factor(care se va aduna!)
else{ i++; rez-=factor(); }
return rez;
}
int main(){
fi>>s;
fo<<expresie()<<'\n';
return 0;
}
////dimensiunea matricii de adiacenta adi[M][M] si viz[M] dau 50p!!!!!!! intuitie frate!!!!!
//#include <fstream>//100p
//#include <iomanip>
//#define M 103
//#include <cstring>
//using namespace std;
//ifstream fi("rebus.in");
//ofstream fo("rebus.out");
//int m,j,t,z,k,i,n,b[M][M],a[M][M],adi[5*M][5*M],viz[5*M];
//char s[M];
//void DF(int nod){
// int i;
// viz[nod]=1;
// for(i=1;i<=k;i++)
// if(adi[i][nod]==1 and viz[i]==0)DF(i);
//}
//int main()
//{
//fi>>m>>n;fi.get();
//for (i=1;i<=m;i++)
// {
// fi.get(s,M);fi.get();
// for(j=0;j<n;j++)
// if(s[j]=='*')a[i][j+1]=-1;
// else if(s[j]=='#')a[i][j+1]=-2;
// }
//for(i=0;i<=m+1;i++)a[i][0]=a[i][n+1]=-2;//bordare matrice ci -2 (#)
//for(j=0;j<=n+1;j++)a[0][j]=a[m+1][j]=-2;
//for(i=1;i<=m;i++) //se parcurge pe linii si se determina grupele
// for(j=1;j<=n;j++)
// if(a[i][j]==-1)
// {t=j+1;while(a[i][t]==-1)t++;
// if(a[i][j-1]==-2 and a[i][t]==-2)
// { k++;
// for(z=j;z<=t-1;z++)b[i][z]=k;
// }
// j=t;
// }
//for(j=1;j<=n;j++) //se parcurge pe coloane si se determina grupele
// for(i=1;i<=m;i++)
// if(a[i][j]==-1)
// {
// t=i+1;while(a[t][j]==-1)t++;
// if(a[i-1][j]==-2 and a[t][j]==-2)
// { k++; //numar componenta identificata
// for(z=i;z<=t-1;z++) //se coloreaza componenta identificata
// {
// if(b[z][j]!=0) //daca se suprapune peste alte componente
// {adi[k][b[z][j]]=1; //se pune in matricea de adiacenta pe 1
// adi[b[z][j]][k]=1;
// }
// b[z][j]=k; //se coloreaza componenta identificata
// }
// }
// i=t;
// }
//int nrc=0;
//for(i=1;i<=k;i++)
// if(viz[i]==0){DF(i);nrc++;}
//fo<<nrc<<'\n';
////for(i=0;i<=m+1;i++)
////{for(j=0;j<=n+1;j++)fo<<setw(3)<<a[i][j]<<" ";
//// fo<<endl;
////}
////for(i=1;i<=m;i++)
////{for(j=1;j<=n;j++)fo<<setw(1)<<b[i][j]<<" ";
//// fo<<endl;
////}fo<<endl;
////for(i=1;i<=m;i++)
////{for(j=1;j<=n;j++)fo<<setw(1)<<adi[i][j]<<" ";
//// fo<<endl;
////}
//return 0;
//}
//
////punctul initial p, punctul i si punctul j sunt pe aceiasi dreapta
////daca se respecta teorema asemanarii al[i]-al[0])*(ac[j]-ac[0])==(al[j]-al[0])*(ac[i]-ac[0])
//// j li-lp lj-lp l este linia
//// i ----- = ------
//// P ci-cp cj-cp c este coloana
//#include <fstream>//100p
//#define M 2003
//using namespace std;
//ifstream fi("turist.in");
//ofstream fo("turist.out");
//int k,m,n,maxi,i,j,p,q,t1,t2,al[M],ac[M],viz[M];
//int main(){
// fi>>m>>n;
// fi>>al[0]>>ac[0];
// fi>>k;
// for(i=1;i<=k;i++)fi>>al[i]>>ac[i];
//
// t1=t2=0; //pe aceiasi orizontala
// for(i=1;i<=k;i++)
// if(al[i]==al[0])
// {if(ac[i]<ac[0])t1++; //t1= numar puncte in stanga
// else t2++; //t2 numar puncte in dreapta
// viz[i]=1;
// }
// maxi=max(maxi,max(t1,t2));
//
// t1=t2=0; //pe aceiasi verticala
// for(i=1;i<=k;i++)
// if(ac[i]==ac[0])
// {if(al[i]<al[0])t1++; //t1= numar puncte in jos
// else t2++; //t2 numar puncte in sus
// viz[i]=1;
// }
// maxi=max(maxi,max(t1,t2));
//
// for(i=1;i<=k;i++) //pe oblice
// if(viz[i]==0)
// if(ac[0]<ac[i]){ //pe aceiasi oblica in dreapta punctul i si j
// t1=1;
// for(j=i+1;j<=k;j++)
// if(viz[j]==0)
// {
// if(ac[0]<ac[j])
// if((al[i]-al[0])*(ac[j]-ac[0])==(al[j]-al[0])*(ac[i]-ac[0]))t1++,viz[j]=1;
// }
// maxi=max(maxi,t1);
// }
// else
// { //pe aceiasi oblica in stanga punctul i si j
// t2=1;
// for(j=i+1;j<=k;j++)
// if(viz[j]==0)
// {
// if(ac[0]>ac[j])
// if((al[i]-al[0])*(ac[j]-ac[0])==(al[j]-al[0])*(ac[i]-ac[0]))t2++,viz[j]=1;
// }
// maxi=max(maxi,t2);
// viz[i]=1;
// }
// fo<<maxi<<'\n';
//return 0;
//}
//#include <cstdio> //100p campion si infoarena
//#include <cstring>
//#define M 303
//using namespace std;
//int j,y,q,z,x,semn,t,i,n,m,a[M][M];
//char c,s[10000];
//int main(){
// freopen("placare.in","r",stdin);
// freopen("placare.out","w",stdout);
// scanf("%d%d",&n,&m);
//
// for(i=1;i<=n;i++){
// j=1;
// while(a[i][j]!=0) j++; //sar peste elementele deja completete
// do
// {
// scanf("%d",&x);y=x;
// if(y>0) //se completeaza pe orizontala
// for(;y;j++){a[i][j]=x;y--;}
// if(y<0) //se completeaza pe verticala
// {
// x=y=-y;
// for(q=1;q<=x;q++) a[i+q-1][j]=x;
// j++;
// }
// while(a[i][j]!=0) j++; //sar peste elementele deja completete
// }while(j<=m); //pana se termina toate coloanele de completat
// }
// for(i=1;i<=n;i++){
// for(j=1;j<=m;j++)printf("%d ",a[i][j]);
// printf("\n");
// }
// return 0;
//}
//#include <cstdio> //90p 1 test gresit dar e identic cu cel corect
//#include <cstring>
//#define M 303
//using namespace std;
//int j,y,q,z,x,semn,t,i,n,m,a[M][M];
//char c,s[10000];
//int main(){
// freopen("placare.in","r",stdin);
// freopen("placare.out","w",stdout);
// scanf("%d%d",&n,&m);
// c = getchar(); //trecere de '\n'
// for(i=1;i<=n;i++){
// j=0;
// while ((c = getchar()) != '\n' && c!= EOF )
// s[j++] = c;
// s[j++] =' ';
// s[j]='\0';
// t=j;
// x=0;
// semn=1; //+
// for(j=0;j<t;j++)
// if(s[j]=='-')semn=-1;
// else
// if(s[j]>='0' and s[j]<='9')x=x*10+s[j]-'0';
// else {
// x=x*semn;semn=1;y=x;
// if(y>0)
// for(z=1;z<=m and y;z++)
// if(a[i][z]==0){a[i][z]=x;y--;}
// if(y<0)
// for(z=1;z<=m;z++)
// if(a[i][z]==0){
// y=-y;
// for(q=1;q<=-x and y;q++)
// {a[i+q-1][z]=-x;y--;}
// break;
// }
// x=0;
// }
// }
// for(i=1;i<=n;i++){
// for(j=1;j<m;j++)printf("%d ",a[i][j]);printf("%d",a[i][m]);
// printf("\n");
// }
// return 0;
//}
//#include <fstream> //70p 2 teste timpul ,si 1 test gresit
//#include <cstring>
//#define M 303
//using namespace std;
//ifstream fi("placare.in");
//ofstream fo("placare.out");
//int j,y,q,z,x,semn,t,i,n,m,a[M][M];
//char c,s[10000];
//int main(){
// fi>>n>>m;
// fi.get();
// for(i=1;i<=n;i++){
// fi.getline(s,10000);
// strcat(s," ");
// t=strlen(s);
// x=0;
// semn=1; //+
// for(j=0;j<t;j++)
// if(s[j]=='-')semn=-1;
// else
// if(s[j]>='0' and s[j]<='9')x=x*10+s[j]-'0';
// else {
// x=x*semn;semn=1;y=x;
// if(y>0)
// for(z=1;z<=m and y;z++)
// if(a[i][z]==0){a[i][z]=x;y--;}
// if(y<0)
// for(z=1;z<=m;z++)
// if(a[i][z]==0){
// y=-y;
// for(q=1;q<=-x and y;q++)
// {a[i+q-1][z]=-x;y--;}
// break;
// }
// x=0;
// }
// }
// for(i=1;i<=n;i++){
// for(j=1;j<=m;j++)fo<<a[i][j]<<' ';
// fo<<'\n';
// }
// return 0;
//}
////var V lbd Campion 100p
////cu o singura coada cu struct (este mai rapida)!!!!!
////( /10000 si %10000 ia timp!!!!!!)
//#include <fstream>
//#include <iostream>
//#include<iomanip>
//#define M 1503
//using namespace std;
//ifstream f("lbd.in");
//ofstream g("lbd.out");
//struct coada{short int i,j;};
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//short int a[M][M];char b[M][M]; //matricea b este char !!
//int i,j,n,m,il,jl,iil,jjl,ok,sol;
//coada c[2040000];coada el; //cu c[2000000] nu ajunge
//string s;
//int Lee(int i,int j,int k){ //se face Lee din (i,j) prin celule de valoare maxima k
//int p,u,el,d,i_i,j_j;
//c[1].i=i;c[1].j=j; //pune punctul de pornire
//p=1;u=1;
//for(i=0;i<=n+1;i++) //toate elementele <= k vor fi bune se considera dezgheatate(se pun pe 0)
// for(j=0;j<=m+1;j++)
// if(a[i][j]<=k)b[i][j]=0;
// else b[i][j]=1; //refolosim matricea b
//b[i][j]=1; //Lee cu notarea celuleler deja luate b[i][j]=1 altfel coada devine f.f. mare!!!
//while(p<=u){
// i=c[p].i;j=c[p].j;p++;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(b[i_i][j_j]==0){b[i_i][j_j]=1; u++; c[u].i=i_i; c[u].j=j_j; }
// if(iil==i_i&&jjl==j_j) return 1;
// }
//}
//return 0;
//}
//int main()
//{
// f>>n>>m;f.get();
// for(i=0;i<=n+1;i++){a[i][0]=6000;a[i][m+1]=6000; } //bordare cu 6000
// for(i=0;i<=m+1;i++){a[0][i]=6000;a[n+1][i]=6000; }
// for(i=1;i<=n;i++){
// getline(f,s);
// for(j=0;j<m;j++){ //apa e notata cu 0
// if(s[j]=='X')a[i][j+1]=3000; //gheata e notata cu 3000
// if(s[j]=='L')
// if(!ok) il=i,jl=j+1,ok=1;
// else iil=i,jjl=j+1;
// }
//
// }
// // for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// int p1,u1,p2,u2,t,i_i,j_j,d,pas=0;
// p1=1;u1=0;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==0)
// if(a[i][j]==3000&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))
// u1++,c[u1].i=i,c[u1].j=j,b[i][j]=1;
// while(1){ //calculeaza pt. fiecare celule la ce moment se topeste
// pas++; //trebie doua cozi la dezghetate alfel de incurca dezghetarea
// for(t=p1;t<=u1;t++)a[c[t].i][c[t].j]=pas;
// u2=u1;
// for(t=p1;t<=u1;t++)
// {
// i=c[t].i;j=c[t].j;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(a[i_i][j_j]==3000 and b[i_i][j_j]==0)u2++,c[u2].i=i_i,c[u2].j=j_j,b[i_i][j_j]=1;
// }
// }
// if(u1==u2)break;
// p1=u1+1;u1=u2;
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
// }
//
//int st=1,dr=pas,mij; //cu cautare binara caut solutia!!!!
//while(st<dr){
// mij=(st+dr)/2;
// if(Lee(il,jl,mij)==0) st=mij+1;
// else dr=mij;
//}
//g<<st;
//return 0;
//}
////var V
////lbd Campion 80p cu o singura coada !!!!! (timp la limita - din cauza /10000 si %10000)
//#include <fstream>
//#include <iostream>
//#include<iomanip>
//#define M 1503
//using namespace std;
//ifstream f("lbd.in");
//ofstream g("lbd.out");
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//short int a[M][M];char b[M][M]; //matricea b este char !!
//int i,j,n,m,il,jl,iil,jjl,ok,sol,c[2040000]; //cu c[2000000] nu ajunge
//string s;
//int Lee(int i,int j,int k){ //se face Lee din (i,j) prin celule de valoare maxima k
//int p,u,el,d,i_i,j_j;
//c[1]=i*10000+j;p=1;u=1;
//for(i=0;i<=n+1;i++)
// for(j=0;j<=m+1;j++)
// if(a[i][j]<=k)b[i][j]=0;
// else b[i][j]=1; //refolosim matricea b
////for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<(int)b[i][j];g<<'\n';}g<<'\n';
//
//b[i][j]=1;
//while(p<=u){
// el=c[p]; p++;i=el/10000;j=el%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(b[i_i][j_j]==0){b[i_i][j_j]=1;u++;c[u]=i_i*10000+j_j; }
// if(iil==i_i&&jjl==j_j){
// //cout<<"<< "<<k<<" "<<u<<">>";
// return 1;
// }
// }
//}
////cout<<"<< "<<k<<" "<<u<<">>";
//return 0;
//}
//int main()
//{
// f>>n>>m;f.get();
// for(i=0;i<=n+1;i++){a[i][0]=6000;a[i][m+1]=6000; } //bordare cu 6000
// for(i=0;i<=m+1;i++){a[0][i]=6000;a[n+1][i]=6000; }
// for(i=1;i<=n;i++){
// getline(f,s);
// for(j=0;j<m;j++){ //apa e notata cu 0
// if(s[j]=='X')a[i][j+1]=3000; //gheata e notata cu 3000
// if(s[j]=='L')
// if(!ok) il=i,jl=j+1,ok=1;
// else iil=i,jjl=j+1;
// }
//
// }
// // for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// int p1,u1,p2,u2,t,i_i,j_j,d,pas=0;
// p1=1;u1=0;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==0)
// if(a[i][j]==3000&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))
// c[++u1]=i*10000+j,b[i][j]=1;
// while(1){ //calculeaza pt. fiecare celule la ce moment se topeste
// pas++;//cout<<pas<<" "<<u_old<<"|";
// for(t=p1;t<=u1;t++)a[c[t]/10000][c[t]%10000]=pas;
// u2=u1;
// for(t=p1;t<=u1;t++)
// {
// i=c[t]/10000;j=c[t]%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(a[i_i][j_j]==3000 and b[i_i][j_j]==0)c[++u2]=i_i*10000+j_j,b[i_i][j_j]=1;
// }
// }
// if(u1==u2)break;
// p1=u1+1;u1=u2;
////cout<<u2<<" ";
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
// }
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
//int st=1,dr=pas,mij;
//while(st<dr){
// mij=(st+dr)/2;
// if(Lee(il,jl,mij)==0) st=mij+1;
// else dr=mij;
//}
//g<<st;
// f.close();g.close();
// return 0;
//}
////var V cu fill //60p crapa fill-ul (nu stiu de ce)
////face 43000 de apeluri si apoi gata!!!!
////lbd Campion
//#include <fstream>
//#include <iostream>
//#include<iomanip>
//#define M 1503
//using namespace std;
//ifstream f("lbd.in");
//ofstream g("lbd.out");
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//short int a[M][M], b[M][M];
//int z,i,j,n,m,il,jl,iil,jjl,ok,sol,c_old[250000],c_new[250000];//cu coada c de 1,5 nu incape in mem!!!
//string s;
//void Fill(int i,int j){
// int d;//z++;cout<<z<<" ";
// b[i][j]=9;
// for(d=1;d<=4;d++)
// if(b[i+diri[d]][j+dirj[d]]==0)
// Fill(i+diri[d],j+dirj[d]);
//// for(d=1;d<=4;d++) //ambele variante creapa!!!
//// {
//// i_i=i+diri[d]; j_j=j+dirj[d];
//// if(b[i_i][j_j]==0)Fill(i_i,j_j);
//// }
//}
//
//int main()
//{
// f>>n>>m;f.get();
// for(i=0;i<=n+1;i++){a[i][0]=6000;a[i][m+1]=6000; } //bordare cu 8
// for(i=0;i<=m+1;i++){a[0][i]=6000;a[n+1][i]=6000; }
// for(i=1;i<=n;i++){
// getline(f,s);
// for(j=0;j<m;j++){ //apa e notata cu 0
// if(s[j]=='X')a[i][j+1]=3000; //gheata e notata cu 3000
// if(s[j]=='L')
// if(!ok) il=i,jl=j+1,ok=1;
// else iil=i,jjl=j+1;
// }
//
// }
// // for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// int u_old,u_new,t,i_i,j_j,d,pas=0;
// u_old=0;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==0)
// if(a[i][j]==3000&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))
// c_old[++u_old]=i*10000+j,b[i][j]=1;
// while(1){ //calculeaza pt. fiecare celule la ce moment se topeste
// pas++;//cout<<pas<<" "<<u_old<<"|";
// for(t=1;t<=u_old;t++)a[c_old[t]/10000][c_old[t]%10000]=pas;
// u_new=0;
// for(t=1;t<=u_old;t++)
// {
// i=c_old[t]/10000;j=c_old[t]%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(a[i_i][j_j]==3000 and b[i_i][j_j]==0)c_new[++u_new]=i_i*10000+j_j,b[i_i][j_j]=1;
// }
// }
// for(t=1;t<=u_new;t++)c_old[t]=c_new[t]; u_old=u_new;
// if(u_old==0)break;
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
// }
//int k=584;
// for(i=0;i<=n+1;i++)
// for(j=0;j<=m+1;j++)
// if(a[i][j]<=k)b[i][j]=0;
// else b[i][j]=1;
// Fill(il,jl);
// //for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// g<<'\n';
////int st=1,dr=pas,mij,k;
////while(st<dr){
//// mij=(st+dr)/2;
//// //
//// k=mij;
//// for(i=0;i<=n+1;i++)
//// for(j=0;j<=m+1;j++)
//// if(a[i][j]<=k)b[i][j]=0;
//// else b[i][j]=1;
//// Fill(il,jl);
//// //for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<b[i][j];g<<'\n';}g<<'\n';
//// // g<<'\n';
//// if(b[iil][jjl]==0) st=mij+1;
//// else dr=mij;
////}
////g<<st;
// f.close();g.close();
// return 0;
//}
////var IV
////lbd Campion 70p coada c prea mica(la 3 teste!!)
//#include <fstream>
//#include <iostream>
//#include<iomanip>
//#define M 1503
//using namespace std;
//ifstream f("lbd.in");
//ofstream g("lbd.out");
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//short int a[M][M];char b[M][M]; //matricea b este char !!
//int i,j,n,m,il,jl,iil,jjl,ok,sol,c[1500000],c_old[250000],c_new[250000];//cu coada c de 1,5 nu incape in mem!!!
//string s;
//int Lee(int i,int j,int k){ //se face Lee din (i,j) prin celule de valoare maxima k
//int p,u,el,d,i_i,j_j;
//c[1]=i*10000+j;p=1;u=1;
//for(i=0;i<=n+1;i++)
// for(j=0;j<=m+1;j++)
// if(a[i][j]<=k)b[i][j]=0;
// else b[i][j]=1; //refolosim matricea b
////for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<(int)b[i][j];g<<'\n';}g<<'\n';
//
//b[i][j]=1;
//while(p<=u){
// el=c[p]; p++;i=el/10000;j=el%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(b[i_i][j_j]==0){b[i_i][j_j]=1;u++;c[u]=i_i*10000+j_j; }
// if(iil==i_i&&jjl==j_j){
// //cout<<"<< "<<k<<" "<<u<<">>";
// return 1;
// }
// }
//}
////cout<<"<< "<<k<<" "<<u<<">>";
//return 0;
//}
//int main()
//{
// f>>n>>m;f.get();
// for(i=0;i<=n+1;i++){a[i][0]=6000;a[i][m+1]=6000; } //bordare cu 8
// for(i=0;i<=m+1;i++){a[0][i]=6000;a[n+1][i]=6000; }
// for(i=1;i<=n;i++){
// getline(f,s);
// for(j=0;j<m;j++){ //apa e notata cu 0
// if(s[j]=='X')a[i][j+1]=3000; //gheata e notata cu 3000
// if(s[j]=='L')
// if(!ok) il=i,jl=j+1,ok=1;
// else iil=i,jjl=j+1;
// }
//
// }
// // for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// int u_old,u_new,t,i_i,j_j,d,pas=0;
// u_old=0;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==0)
// if(a[i][j]==3000&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))
// c_old[++u_old]=i*10000+j,b[i][j]=1;
// while(1){ //calculeaza pt. fiecare celule la ce moment se topeste
// pas++;//cout<<pas<<" "<<u_old<<"|";
// for(t=1;t<=u_old;t++)a[c_old[t]/10000][c_old[t]%10000]=pas;
// u_new=0;
// for(t=1;t<=u_old;t++)
// {
// i=c_old[t]/10000;j=c_old[t]%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(a[i_i][j_j]==3000 and b[i_i][j_j]==0)c_new[++u_new]=i_i*10000+j_j,b[i_i][j_j]=1;
// }
// }
// for(t=1;t<=u_new;t++)c_old[t]=c_new[t]; u_old=u_new;
// if(u_old==0)break;
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
// }
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
//int st=1,dr=pas,mij;
//while(st<dr){
// mij=(st+dr)/2;
// if(Lee(il,jl,mij)==0) st=mij+1;
// else dr=mij;
//}
//g<<st;
// f.close();g.close();
// return 0;
//}
////var III
////lbd Campion 60p timp depasit (coada cu pointeri merge mai incet ca vectorul c)
////implementare Lee cu coada cu pionteri ! merge incet la 2 milioane de elemente!!!(2-3 ori mai lent)
////nu sunt probleme cu memoria NU se contorizeaza Heap-ul(pointerii)
//
//#include <fstream>
//#include <iostream>
//#include<iomanip>
//#define M 1503
//using namespace std;
//ifstream f("lbd.in");
//ofstream g("lbd.out");
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//short int a[M][M],b[M][M];
//int i,j,n,m,il,jl,iil,jjl,ok,sol,c_old[250000],c_new[250000];//cu coada c de 1,5 nu incape in mem!!!
//string s;
//struct Nod{
// int i,j;
// Nod *urm;
//};
//void adauga(Nod *&p,Nod *&u,int i,int j){
// Nod *c=new Nod;
// c->i=i;c->j=j;
// c->urm=0;
// u->urm=c;
// u=c;
//}
//int Lee(int i,int j,int k){ //se face Lee din (i,j) prin celule de valoare maxima k
//int d,i_i,j_j;
//Nod *p,*u,*t,*c;
// b[i][j]=1;
// c=new Nod; //se pune in coada nodul de pornire
// c->i=i;c->j=j;
// c->urm=0;
// p=c;u=c;
//
// for(i=0;i<=n+1;i++)
// for(j=0;j<=m+1;j++)
// if(a[i][j]<=k)b[i][j]=0;
// else b[i][j]=a[i][j]; //refolosim matricea b
// while(p!=0){
// i=p->i;j=p->j;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(b[i_i][j_j]==0){b[i_i][j_j ]=1;adauga(p,u,i_i,j_j);}
// if(iil==i_i&&jjl==j_j) return 1;
// }
// t=p; //sterge nodul din capul cozii si inainteaza in coada
// p=p->urm;
// delete t;
// }
//return 0;
//}
//
//int main()
//{
// f>>n>>m;f.get();
// for(i=0;i<=n+1;i++){a[i][0]=6000;a[i][m+1]=6000; } //bordare cu 8
// for(i=0;i<=m+1;i++){a[0][i]=6000;a[n+1][i]=6000; }
// for(i=1;i<=n;i++){
// getline(f,s);
// for(j=0;j<m;j++){ //apa e notata cu 0
// if(s[j]=='X')a[i][j+1]=3000; //gheata e notata cu 3000
// if(s[j]=='L')
// if(!ok) il=i,jl=j+1,ok=1;
// else iil=i,jjl=j+1;
// }
//
// }
// // for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// int u_old,u_new,t,i_i,j_j,d,pas=0;
// u_old=0;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==0)
// if(a[i][j]==3000&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))
// c_old[++u_old]=i*10000+j,b[i][j]=1;
// while(1){ //calculeaza pt. fiecare celule la ce moment se topeste
// pas++;//cout<<pas<<" "<<u_old<<"|";
// for(t=1;t<=u_old;t++)a[c_old[t]/10000][c_old[t]%10000]=pas;
// u_new=0;
// for(t=1;t<=u_old;t++)
// {
// i=c_old[t]/10000;j=c_old[t]%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(a[i_i][j_j]==3000 and b[i_i][j_j]==0)c_new[++u_new]=i_i*10000+j_j,b[i_i][j_j]=1;
// }
// }
// for(t=1;t<=u_new;t++)c_old[t]=c_new[t]; u_old=u_new;
// if(u_old==0)break;
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
// }
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
//int st=1,dr=pas,mij;
//while(st<dr){
// mij=(st+dr)/2;
// if(Lee(il,jl,mij)==0) st=mij+1;
// else dr=mij;
//}
//g<<st;
//return 0;
//}
////var II
////lbd Campion 60p coada prea mica(la 3 teste!!)
//#include <fstream>
//#include <iostream>
//#include<iomanip>
//#define M 1503
//using namespace std;
//ifstream f("lbd.in");
//ofstream g("lbd.out");
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//short int a[M][M],b[M][M];
//int i,j,n,m,il,jl,iil,jjl,ok,sol,c[1000000],c_old[150000],c_new[150000];//cu coada c de 1,5 nu incape in mem!!!
//string s;
//int Lee(int i,int j,int k){ //se face Lee din (i,j) prin celule de valoare maxima k
//int p,u,el,d,i_i,j_j;
//c[1]=i*10000+j;p=1;u=1;
//for(i=0;i<=n+1;i++)
// for(j=0;j<=m+1;j++)
// if(a[i][j]<=k)b[i][j]=0;
// else b[i][j]=a[i][j]; //refolosim matricea b
//b[i][j]=1;
//while(p<=u){
// el=c[p]; p++;i=el/10000;j=el%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(b[i_i][j_j]==0){b[i_i][j_j ]=1;u++;c[u]=i_i*10000+j_j; }
// if(iil==i_i&&jjl==j_j){
// //cout<<"<< "<<k<<" "<<u<<">>";
// return 1;
// }
// }
//}
////cout<<"<< "<<k<<" "<<u<<">>";
//return 0;
//}
//int main()
//{
// f>>n>>m;f.get();
// for(i=0;i<=n+1;i++){a[i][0]=6000;a[i][m+1]=6000; } //bordare cu 8
// for(i=0;i<=m+1;i++){a[0][i]=6000;a[n+1][i]=6000; }
// for(i=1;i<=n;i++){
// getline(f,s);
// for(j=0;j<m;j++){ //apa e notata cu 0
// if(s[j]=='X')a[i][j+1]=3000; //gheata e notata cu 3000
// if(s[j]=='L')
// if(!ok) il=i,jl=j+1,ok=1;
// else iil=i,jjl=j+1;
// }
//
// }
// // for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// int u_old,u_new,t,i_i,j_j,d,pas=0;
// u_old=0;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==0)
// if(a[i][j]==3000&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))
// c_old[++u_old]=i*10000+j,b[i][j]=1;
// while(1){ //calculeaza pt. fiecare celule la ce moment se topeste
// pas++;//cout<<pas<<" "<<u_old<<"|";
// for(t=1;t<=u_old;t++)a[c_old[t]/10000][c_old[t]%10000]=pas;
// u_new=0;
// for(t=1;t<=u_old;t++)
// {
// i=c_old[t]/10000;j=c_old[t]%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(a[i_i][j_j]==3000 and b[i_i][j_j]==0)c_new[++u_new]=i_i*10000+j_j,b[i_i][j_j]=1;
// }
// }
// for(t=1;t<=u_new;t++)c_old[t]=c_new[t]; u_old=u_new;
// if(u_old==0)break;
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
// }
//// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
//// g<<'\n';
//int st=1,dr=pas,mij;
//while(st<dr){
// mij=(st+dr)/2;
// if(Lee(il,jl,mij)==0) st=mij+1;
// else dr=mij;
//}
//g<<st;
// f.close();g.close();
// return 0;
//}
//var I
////lbd Campion 30p timp de executie si coada prea mica(la 2 teste!!)
//#include <fstream>
//#include<iomanip>
//#define M 1503
//using namespace std;
//ifstream f("lbd.in");
//ofstream g("lbd.out");
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//char a[M][M],b[M][M];
//int i,j,n,m,il,jl,iil,jjl,ok,sol,c[700000];
//string s;
//int LeeFill(int i,int j){
//int p,u,el,d,i_i,j_j;
//c[1]=i*10000+j;p=1;u=1;
//for(i=0;i<=n+1;i++)
// for(j=0;j<=m+1;j++)
// b[i][j]=a[i][j];
//b[i][j]=1;
//while(p<=u){
// el=c[p]; p++;i=el/10000;j=el%10000;
// for(d=1;d<=4;d++){
// i_i=i+diri[d]; j_j=j+dirj[d];
// if(b[i_i][j_j]==0){b[i_i][j_j ]=1;u++;c[u]=i_i*10000+j_j; }
// if(iil==i_i&&jjl==j_j)return 1;
// }
//}
//return 0;
//}
//int main()
//{
// f>>n>>m;f.get();
// for(i=0;i<=n+1;i++){a[i][0]=8;a[i][m+1]=8; } //bordare cu 8
// for(i=0;i<=m+1;i++){a[0][i]=8;a[n+1][i]=8; }
// for(i=1;i<=n;i++){
// getline(f,s);
// for(j=0;j<m;j++){ //apa e notata cu 0
// if(s[j]=='X')a[i][j+1]=2; //gheata e notata cu 2
// if(s[j]=='L')
// if(!ok) il=i,jl=j+1,ok=1;
// else iil=i,jjl=j+1;
// }
//
// }
// // for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// while(1){
// if(LeeFill(il,jl)) {g<<sol<<'\n';break;}
// sol++; //se parcurge mat. pt. fiecare zi si se dezgheata(lent)!!!
// for(i=1;i<=n;i++) for(j=1;j<=m;j++)
// if(a[i][j]==2&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))a[i][j]=1;
// //for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]==1)a[i][j]=0;
// //for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
// }
// f.close();g.close();
// return 0;
//}
/*
//lbd Campion 30p
#include <fstream>
#include<iomanip>
#define M 1005
using namespace std;
ifstream f("lbd.in");
ofstream g("lbd.out");
int diri[]={0,-1,0,1, 0};//N E S V
int dirj[]={0, 0,1,0,-1};
int i,j,n,m,a[M][M],il,jl,iil,jjl,ok,sol,c[100000];
string s;
int LeeFill(int i,int j){
int p,u,el,d,i_i,j_j;
c[1]=i*1000+j;p=1;u=1;a[i][j]=1;
while(p<=u){
el=c[p];i=el/1000;j=el%1000;
for(d=1;d<=4;d++){
i_i=i+diri[d]; j_j=j+dirj[d];
if(a[i_i][j_j]==0){a[i_i][j_j ]=1;u++;c[u]=i_i*1000+j_j; }
if(iil==i_i&&jjl==j_j)return 1;
}
p++;
}
return 0;
}
int main()
{
f>>n>>m;f.get();
for(i=0;i<=n+1;i++){a[i][0]=-1;a[i][m+1]=-1; }
for(i=0;i<=m+1;i++){a[0][i]=-1;a[n+1][i]=-1; }
for(i=1;i<=n;i++){
getline(f,s);
for(j=0;j<m;j++){
if(s[j]=='X')a[i][j+1]=-2;
if(s[j]=='L')
if(!ok) il=i,jl=j+1,ok=1;
else iil=i,jjl=j+1;
}
}
// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
while(1){
if(LeeFill(il,jl)) {g<<sol<<'\n';break;}
sol++;
for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]>0)a[i][j]=0;
for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]==-2&&(a[i+1][j]==0||a[i-1][j]==0||a[i][j+1]==0||a[i][j-1]==0))a[i][j]=1;
// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(a[i][j]==1)a[i][j]=0;
// for(i=0;i<=n+1;i++) {for(j=0;j<=m+1;j++)g<<setw(2)<<a[i][j];g<<'\n';}g<<'\n';
}
f.close();g.close();
return 0;
}
*/
//# include <fstream>
//# include<iomanip>
//# define M 102
//using namespace std;
//ifstream fi("alpinist.in");
//ofstream fo("alpinist.out");
//int t,ip,jp,i,m,n,j,a[M][M],b[M][M];
//int sol[M*M]; char dir[M*M];
//void Lee(){ //face Lee pornind din toate celulele de zero deodata!!!
// int i,j,x,u,p,c[250000];
// for(i=0;i<=m+1;i++)a[i][0]=a[i][n+1]=2000; //bordare
// for(j=0;j<=n+1;j++) a[0][j]=a[m+1][j]=2000;
// p=1;u=0;
// for(i=1;i<=m;i++)
// for(j=1;j<=n;j++)
// if(a[i][j]==0){c[++u]=i*1000+j;b[i][j]=1;} //se pun in coada celule cu 0
// while(p<=u){
// x=c[p];p++;
// i=x/1000;j=x%1000;
// if(a[i-1][j]<=a[i][j]+100 and (b[i-1][j]>b[i][j]+1 or b[i-1][j]==0)) //diferenta 100+drum mai scurt+drum necalculat inca
// {b[i-1][j]=b[i][j]+1;c[++u]=(i-1)*1000+j;}//N
// if(a[i+1][j]<=a[i][j]+100 and (b[i+1][j]>b[i][j]+1 or b[i+1][j]==0))
// {b[i+1][j]=b[i][j]+1;c[++u]=(i+1)*1000+j;}//S
// if(a[i][j-1]<=a[i][j]+100 and (b[i][j-1]>b[i][j]+1 or b[i][j-1]==0))
// {b[i][j-1]=b[i][j]+1;c[++u]=(i)*1000+(j-1);}//W
// if(a[i][j+1]<=a[i][j]+100 and (b[i][j+1]>b[i][j]+1 or b[i][j+1]==0))
// {b[i][j+1]=b[i][j]+1;c[++u]=(i)*1000+(j+1);}//E
// }
//}
//void drum(int ip,int jp){ //reface drumul invers de la un varf maxim cu drumul cel mai scurt
// int i=ip,j=jp;
// sol[++t]=i*1000+j; //in sol[] se pun pasii drumului
// while(b[i][j]>1){ // conditie de pas-1 si diferenta 100 maxim!!!!
// if(b[i][j]-1==b[i-1][j] and a[i-1][j]>=a[i][j]-100) {dir[t-1]='S';i--;sol[++t]=i*1000+j;} //N
// else if(b[i][j]-1==b[i+1][j] and a[i+1][j]>=a[i][j]-100) {dir[t-1]='N';i++;sol[++t]=i*1000+j;} //S
// else if(b[i][j]-1==b[i][j-1] and a[i][j-1]>=a[i][j]-100) {dir[t-1]='E';j--;sol[++t]=i*1000+j;} //W
// else if(b[i][j]-1==b[i][j+1] and a[i][j+1]>=a[i][j]-100) {dir[t-1]='W';j++;sol[++t]=i*1000+j;} //E
// }
//}
//int main(){
// fi>>m>>n;
// for(i=1;i<=m;i++)
// for(j=1;j<=n;j++)
// fi>>a[i][j];
// Lee();
//// for(i=0;i<=m+1;i++){for(j=0;j<=n+1;j++)fo<<setw(5)<<a[i][j]<<" ";fo<<endl;}
//// fo<<endl;
//// for(i=1;i<=m;i++){for(j=1;j<=n;j++)fo<<setw(5)<<b[i][j]<<" ";fo<<endl;}
// int maxi=-1,maxi2=-1;
// for(i=1;i<=m;i++) //calcul varf maxim atins
// for(j=1;j<=n;j++)
// if(b[i][j]!=0 and a[i][j]>maxi)maxi=a[i][j];
// for(i=1;i<=m;i++) //aleg din varfurile maxime cel cu drumul cel mai scurt =>(ip,jp) varful cautat
// for(j=1;j<=n;j++)
// if(b[i][j]>maxi2 and a[i][j]==maxi){maxi2=b[i][j];ip=i;jp=j;}
//
// drum(ip,jp); //refac drum invers
// fo<<a[ip][jp]<<'\n';
// fo<<sol[t]/1000<<" "<<sol[t]%1000<<" "<<ip<<" "<<jp<<'\n';
// fo<<t-1<<'\n';
// for(i=t-2;i>=0;i--) fo<<dir[i]<<" ";
//return 0;
//}
//#include <cstdio>//var I 90p timpul fara backtraking generarea cu next permutation)
//#include <cstring>
//#include <algorithm>
//#define M 13
//using namespace std;
//int t,k,j,mini,i,n,a[M],ap[M];
//char s[M],b[M],ss[M];
//void tip(int i){
// int j;
// for(j=1; j<=i; j++) ss[j-1]=b[a[j]];
// ss[j]=0;
// printf("%s\n",ss);
//}
//int valid(int i){
// int j,t;
// for(t=1; t<=i; t++)
// for(j=1;j<t;j++)
// if( a[j]>a[t] and b[a[j]]==b[a[t]])return 0;
// return 1;
//}
//int main()
//{
// freopen("anag.in","r",stdin);
// freopen("anag.out","w",stdout);
// scanf("%s",&s);
// n=strlen(s);
// sort(s,s+n);
// for(i=0; i<n; i++)b[i+1]=s[i];
// for(i=1; i<=n; i++) a[i]=i;
// if(valid(n))tip(n);
// //for(i=1; i<=n; i++) g<<a[i]<<" ";g<<endl;
// do
// {
// j=n;
// while(a[j-1]>a[j] && j>1) j--;
// j--;
// if(j)
// {
// mini=a[j+1]; t=j+1;
// for(i=j+1; i<=n; i++)
// if(mini>a[i] && a[i]>a[j]) mini=a[i], t=i;
// k=a[j], a[j]=a[t]; a[t]=k;
// for(i=1; i<=(n-j)/2; i++) k=a[j+i],a[j+i]=a[n-i+1],a[n-i+1]=k;
// if(valid(n))tip(n);
// //for(i=1; i<=n; i++) g<<a[i]<<" "; g<<endl;
// }
// }
// while(j);
// return 0;
//}
//#include <cstdio>//var II backtraking 90p timpul
//#include <cstring>
//#include <algorithm>
//#define M 13
//using namespace std;
//int n,a[M],ap[M];
//char s[M],b[M],ss[M];
//void tip(int i)
//{
// int j;
// for(j=1; j<=i; j++) ss[j-1]=b[a[j]];
// ss[j]=0;
// printf("%s\n",ss);
//}
//int valid(int i)
//{
// int j;
// for(j=0; j<i; j++)
// if( a[j]>a[i] and b[a[j]]==b[a[i]])return 0;
// return 1;
//}
//void back(int i)
//{
// int val;
// for(val=1; val<=n; val++)
// {
// a[i]=val;
// ap[val]++;
// if(ap[val]==1 and valid(i))
// if(i==n)tip(i);
// else back(i+1);
// ap[val]--;
// }
//}
//int main()
//{
// freopen("anag.in","r",stdin);
// freopen("anag.out","w",stdout);
// scanf("%s",&s);
// n=strlen(s);
// sort(s,s+n);
// for(int i=0; i<n; i++)b[i+1]=s[i];
// back(1);
// return 0;
//}
////#include <fstream>//var III fara afisare rapida 80p timpul
////#include <cstring>
////#include <algorithm>
////#define M 13
////using namespace std;
////ifstream fi("anag.in");
////ofstream fo("anag.out");
////int n,a[M];char s[M],b[M];
////void tip(int i){
////for(int j=1;j<=i;j++)fo<<b[a[j]];
////fo<<'\n';
////}
//////void tip(int i){ //+10p afisare mai rapida
//////int j;
//////for(j=1;j<=i;j++) ss[j-1]=b[a[j]];
//////ss[j]=0;
//////fo<<ss<<'\n';
//////}
////int valid(int i){
//// int j;
//// for(j=0;j<i;j++)
//// if(a[j]==a[i])return 0;
//// for(j=0;j<i;j++)
//// if(b[a[j]]==b[a[i]] and a[j]>a[i])return 0;
//// return 1;
////}
////void back(int i){
////int val;
////for(val=1;val<=n;val++){
//// a[i]=val;
//// if(valid(i))
//// if(i==n)tip(i);
//// else back(i+1);
//// }
////}
////int main(){
////fi.get(s,M);
////n=strlen(s);
////sort(s,s+n);
////for(int i=0;i<n;i++)b[i+1]=s[i];
////back(1);
////return 0;
////}
////se face d ce reprezinta diferenta dintre nr. de 0 si 1 in i
////intre doua numere egale ca diferenta avem o solutie
////d= 1 0 1 0 0 1 0 1 0 pt. 1 avem 4*3/2 solutii
////d= 1 0 1 0 0 1 0 1 0 pt. 0 avem 5*4/2 solutii+ 5 solutii (pt 0 daca luam de la inceput!!)
//#include <fstream>
//#include <cstring>
//#define M 1000003
//using namespace std;
//ifstream fi("ab.in");
//ofstream fo("ab.out");
//int i,n,m,j;long long sol;
//int d[M],fr[2*M];
//char a[M];
//int main(){
//char s[M];
//fi.get(s,M);
//n=strlen(s);
//for(i=0;i<n;i++)
// a[i+1]=s[i]-'a';
////for(i=1;i<=n;i++)fo<<a[i]<<" ";fo<<endl;
//for(i=1;i<=n;i++)
// if(a[i]==0)d[i]=d[i-1]-1;
// else d[i]=d[i-1]+1;
////for(i=1;i<=n;i++)fo<<d[i]<<" ";fo<<endl;
//for(i=1;i<=n;i++)fr[M+d[i]]++;
//int t=2*M-2; //fara asta da 85
//for(i=0;i<=t;i++)
// if(fr[i]>1) //fara asta da 85
// sol+=(long long)fr[i]*(fr[i]-1)/2;
//sol+=(long long)fr[M];
//fo<<sol;
//return 0;
//}
//#include <cstdio>
//#define M 1003
//using namespace std;
//int k,t,i,n,m,j,nr,ii,jj,iii,jjj,p,q;
//int a[M][M],b[M][M];
//int main(){
//freopen("acces.in","r",stdin);
//freopen("acces.out","w",stdout);
//scanf("%d%d",&n,&m);
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// scanf("%d",&a[i][j]);
////for(i=1;i<=n;i++){for(j=1;j<=m;j++)printf("%d ",a[i][j]);printf("\n");}
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]==0)
// {
// if(a[i-1][j]==0 and a[i][j-1]==1)b[i][j]=1+b[i-1][j]; // 1 0 sau 1 1
// if(a[i-1][j]==1 and a[i][j-1]==0)b[i][j]=1+b[i][j-1]; // 1 ? 0 ?
// if(a[i-1][j]==0 and a[i][j-1]==0)
// if(a[i-1][j-1]==0)b[i][j]=1+b[i-1][j]+b[i][j-1]-b[i-1][j-1]; // 0 0
// else //* 0 0 0 // 0 ?
// { //0 1 1 0
// ii=i-1;jj=j-1; //0 1 1 0
// while(a[ii][jj]==1)ii--; //0 0 0 ?
// iii=i-1;jjj=j-1;
// while(a[iii][jjj]==1)jjj--;
// b[i][j]=1+b[i-1][j]+b[i][j-1]-b[ii][jjj];
// }
// }
////for(i=1;i<=n;i++){for(j=1;j<=m;j++)printf("%d ",b[i][j]);printf("\n");}
//scanf("%d",&t);
//for(i=1;i<=t;i++)
//{
// scanf("%d%d",&p,&q);
// printf("%d\n",b[p][q]);
//}
//return 0;
//}//
//#include <fstream>
//#define M 203
//using namespace std;
//ifstream fi("oras1.in");
//ofstream fo("oras1.out");
//int sum,k,t,i,n,m,j,nr,maxi;
//char s[M];
//int a[M][M];
//void Fill(int i,int j){ //algoritm de fill
// if(a[i][j]==1){ //umple zonele de 1 cu 6
// a[i][j]=1+5;
// Fill(i-1,j);Fill(i,j+1);
// Fill(i+1,j);Fill(i,j-1);
// }
//}
//void Fill2(int i,int j,int &k){ //algoritm de fill
// if(a[i][j]==2){ //umple zonele de 2 cu 7
// a[i][j]=2+5;k++; //si numara in k cate elemente de 2 are zona
// Fill2(i-1,j,k);Fill2(i,j+1,k);
// Fill2(i+1,j,k);Fill2(i,j-1,k);
// }
//}
//int main(){
//fi>>n>>m;fi.get();
//for(i=1;i<=n;i++)
//{
// fi.get(s,M);fi.get();
// for(j=0;j<m;j++){
// if(s[j]=='C')a[i][j+1]=1;
// if(s[j]=='P')a[i][j+1]=2;
// if(s[j]=='S')a[i][j+1]=3;
// }
//}
////for(i=1;i<=n;i++){for(j=1;j<=m;j++)fo<<a[i][j]<<" ";fo<<endl;}
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]!=0)
// if(a[i-1][j-1]==0 or a[i-1][j]==0 or a[i-1][j+1]==0
// or a[i][j+1]==0
// or a[i+1][j+1]==0 or a[i+1][j]==0 or a[i+1][j-1]==0
// or a[i][j-1]==0) t++;
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]==1){Fill(i,j);nr++;}
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]==2){k=0;
// Fill2(i,j,k);
// maxi=max(maxi,k);}
//fo<<t<<" "<<nr<<" "<<maxi;
//return 0;
//}
//
//#include <fstream>
//using namespace std;
//ifstream fi("puncte2.in");
//ofstream fo("puncte2.out");
//int s,sum,k,t,i,n,m,j;
//int a[100];
//int main(){
//fi>>n;;
//a[0]=1;
//for(i=1;i<=n;i++)
// {
// s=0;
// for(k=0;k<i;k++)s+=a[(i-1)-k]*a[k];
// a[i]=s;
// }
// fo<<a[n];
//return 0;
//}
//#include <fstream>//100p
//#include<iomanip>//da 90p ca are o litera lipsa la un test un a lipsa
//#define M 203
//using namespace std;
//ifstream fi("abq.in");
//ofstream fo("abq.out");
//int t,i,n,m,j,xs,ys,xf,yf;
//int a[M][M],c[300000];
//char ch;
//int Lee(int xs,int ys,int xf, int yf){
// int i,j,x,p,u; bool gata;
// int b[M][M];
// if((a[xs][ys]==1) or a[xf][yf]==1)return -1;
// for(i=0;i<=n+1;i++)b[i][0]=b[i][m+1]=1; //bordare
// for(j=0;j<=m+1;j++)b[0][j]=b[n+1][j]=1; //bordare
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++) b[i][j]=a[i][j];
// i=xs;j=ys;
// b[i][j]=1; //Lee
// c[1]=i*1000+j;p=u=1;
// gata=false;
// while(p<=u &&gata==false){
// x=c[p];p++;
// i=x/1000;j=x%1000;
// if(b[i-1][j]==0){b[i-1][j]=b[i][j]+1;c[++u]=(i-1)*1000+j;}//N
// if(b[i+1][j]==0){b[i+1][j]=b[i][j]+1;c[++u]=(i+1)*1000+j;}//S
// if(b[i][j+1]==0){b[i][j+1]=b[i][j]+1;c[++u]=(i)*1000+(j+1);}//E
// if(b[i][j-1]==0){b[i][j-1]=b[i][j]+1;c[++u]=(i)*1000+(j-1);}//V
// if(b[xf][yf]!=0)gata = true;
// }
// //for(i=0;i<=n+1;i++){ for(j=0;j<=m+1;j++)fo<<setw(3)<<b[i][j];fo<<endl;}fo<<endl;
// if(gata==false)return -1;
// else return b[xf][yf];
//}
//int main(){
//char s[M];
//fi>>n>>m;fi.get();
//for(i=1;i<=n;i++){
// fi.get(s,M);
// for(j=0;j<m;j++){a[i][j+1]=s[j]-'a';}
// fi.get();
//}
////for(i=1;i<=n;i++){ for(j=1;j<=m;j++)fo<<setw(3)<<a[i][j];fo<<endl;}fo<<endl;
//fi>>t;
//for(i=1;i<=t;i++)
//{
// fi>>xs>>ys>>xf>>yf;
// fo<<Lee(xs,ys,xf,yf)<<'\n';
//}
//return 0;
//}
bodnariuc danut danutbod