//#include <iostream>//100p
//#include<fstream>
//#include <algorithm>
//using namespace std;
//fstream f("algsort.in",ios::in);
//fstream g("algsort.out",ios::out);
//int a[500003],n,i,j,aux;
//int main()
//{
// //sortarea elementelor de la a[1],a[2], ..a[n]
// f>>n;
// for(i=1;i<=n;i++) f>>a[i];
// sort(a+1,a+n+1);
// for(i=1;i<=n;i++) g<<a[i]<<" ";
// g<<'\n';
// f.close(); g.close();
// return 0;
//}
//ordonarea cu metoda QuickSort
#include<fstream>
using namespace std;
fstream f("algsort.in",ios::in);
fstream g("algsort.out",ios::out);
int a[500003],n,k;
void poz(int li,int ls,int&k)
{
int i=li,j=ls,c,i1=0,j1=-1;
while(i<j)
{
if(a[i]>a[j])
{
swap(a[i],a[j]);
c=i1; i1=-j1; j1=-c;
}
i=i+i1; j=j+j1;
}
k=i;
}
void quick(int li,int ls)
{
if(li<ls)
{
poz(li,ls,k);
quick(li,k-1);
quick(k+1,ls);
}
}
int main()
{
int i;
f>>n;
for(i=1;i<=n;i++) f>>a[i];
quick(1,n);
for(i=1;i<=n;i++)g<<a[i]<<" ";;
g<<'\n';
g.close(); f.close();
return 0;
}
//#include <iostream>
//#include <limits>
//using namespace std;
//unsigned long long M,i,n,a[100003],b[100003];
//int main() {
// M=numeric_limits<unsigned long long>::max();
// //M=18446744073709551615;
// cin>>n;
// for(i=1;i<=n;i++) cin>>a[i]>>b[i];
// for(i=1;i<=n;i++) {
// if((double)a[i]*(double)b[i]>(double)M) cout<<"Overflow!";
// else cout<<a[i]*b[i];
// cout<<'\n';
// }
// return 0;
//}
//#include <iostream>//75p timp depasit
//#include<fstream>
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("ov.in");
////ofstream fo("ov.out");
//unsigned long long maxi[1000]={0,5,1,6,1,5,5,9,0,7,3,7,0,4,4,7,6,4,4,8,1};
//
//unsigned long long a[1000],b[1000],n,i,c[1000],x,y,nrcif,tr,j,ka,kb,z,cif,u,q;
//
//void desf(unsigned long long x, unsigned long long a[], unsigned long long& k) {
//k=0;
//while(x)
// {
// a[++k]=x%10;
// x/=10;
// }
// }
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>x>>y;
// if(x==0 and y==0)fo<<0<<'\n';
// else {
// desf(x,a,ka);//face din numar vector
// desf(y,b,kb);
// // for(j=1;j<=ka;j++)fo<<a[j];fo<<endl;
// //for(j=1;j<=kb;j++)fo<<b[j];fo<<endl;
// for(j=1;j<=300;j++) c[j]=0;
//
// for(z=1;z<=ka;z++) //inmultirea
// for(j=1;j<=kb;j++)
// c[z+j-1]+=a[z]*b[j];
// tr=0;
// for(j=1;j<=ka+kb-1;j++)
// {
// cif=tr+c[j];
// c[j]=cif%10;
// tr=cif/10;
// }
// nrcif=ka+kb-1;
// if(tr!=0)
// {
// nrcif++;
// c[nrcif]=tr;
// }
//
// int ok=1;
// if(nrcif>20)ok=0;
// if(nrcif==20)
// for(j=nrcif;j>=1;j--)
// if(c[j]!=maxi[j])
// {
// if(maxi[j]<c[j])ok=0;
// break;
// }
// if(ok==1)fo<<x*y<<'\n';
// else fo<<"Overflow!"<<'\n';
// }}
// return 0;
//}
//#include <iostream>
//#include <cmath>
//#include<fstream>
//using namespace std;
//ifstream fi("ord.in");
//ofstream fo("ord.out");
//long long n,i,t,j,ori,sp,nr;
//int main()
//{
// cin>>n;
// if(n==1){cout<<1<<endl;return 0;} //modificare 1(cazul n==1 tratat separat)
// ori=1;//de cate ori afisez nr
// sp=n-1;//nr spatii afisare inainte de nr
// nr=1;
// for(t=1;t<=n;t++){//prima jumatate romb
// for(i=1;i<=sp;i++)
// cout<<" ";
// sp--;
// for(j=1;j<=ori;j++)
// cout<<nr;
// cout<<endl;
// // cout<<endl; //modificare 2
// nr++;
// ori+=2;
// }
// nr-=2;
// ori-=4;
//sp=1;
// for(t=1;t<=n;t++){//a doua jumatate romb
// for(i=1;i<=sp;i++)
// cout<<" ";
// sp++;
// for(j=ori;j>=1;j--)
// cout<<nr;
// if(nr!=1){
// cout<<endl;
// // cout<<endl; //modificare 3
// }
// nr--;
// ori-=2;
// }
//
//return 0;
//}
//#include <iostream>//http://www.pbinfo.ro/?pagina=judge-board&id_problema=1069
//using namespace std;
//unsigned long long M,i,n,a[100003],b[100003];
//int main() {
// M=18446744073709551615;
// cin>>n;
// for(i=1;i<=n;i++) cin>>a[i]>>b[i];
// for(i=1;i<=n;i++) {
// if(a[i]!=0 and ((long double)M/(long double)a[i]<=(long double)b[i])) cout<<"Overflow!";
// else cout<<a[i]*b[i];
// cout<<'\n';
// }
// return 0;
//}
//#include <iostream>
//#include<fstream>
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("ov.in");
////ofstream fo("ov.out");
//unsigned long long maxi[1000]={0,5,1,6,1,5,5,9,0,7,3,7,0,4,4,7,6,4,4,8,1};
//
//unsigned long long a[1000],b[1000],n,i,c[1000],x,y,nrcif,tr,j,ka,kb,z,cif,u,q;
//
//void desf(unsigned long long x, unsigned long long a[], unsigned long long& k) {
//k=0;
//while(x)
// {
// a[++k]=x%10;
// x/=10;
// }
// }
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>x>>y;
// if(x==0 and y==0)fo<<0<<'\n';
// else {
// desf(x,a,ka);//face din numar vector
// desf(y,b,kb);
// // for(j=1;j<=ka;j++)fo<<a[j];fo<<endl;
// //for(j=1;j<=kb;j++)fo<<b[j];fo<<endl;
// for(j=1;j<=300;j++) c[j]=0;
//
// for(z=1;z<=ka;z++) //inmultirea
// for(j=1;j<=kb;j++)
// c[z+j-1]+=a[z]*b[j];
// tr=0;
// for(j=1;j<=ka+kb-1;j++)
// {
// cif=tr+c[j];
// c[j]=cif%10;
// tr=cif/10;
// }
// nrcif=ka+kb-1;
// if(tr!=0)
// {
// nrcif++;
// c[nrcif]=tr;
// }
//
// int ok=1;
// if(nrcif>20)ok=0;
// if(nrcif==20)
// for(j=nrcif;j>=1;j--)
// if(c[j]!=maxi[j])
// {
// if(maxi[j]<c[j])ok=0;
// break;
// }
// if(ok==1)fo<<x*y<<'\n';
// else fo<<"Overflow!"<<'\n';
// }}
// return 0;
//}
// int ok=1;
// if(nrcif>20)fo<<"Overflow!"<<'\n';
// else if(nrcif<20)fo<<x[i]*y[i]<<'\n';
// else
// for(j=nrcif;j>=1;j--)
// if(c[j]!=maxi[j])
// {
// if(maxi[j]<c[j])fo<<"Overflow!"<<'\n';
// else fo<<x[i]*y[i]<<'\n';
// break;
// }
// if(j==0)fo<<x[i]*y[i]<<'\n';
// }
//#include <fstream>
//#include<cstring>
//#include <algorithm>
//#define M 1001
//using namespace std;
//ifstream fi("cuvinte2.in");
//ofstream fo("cuvinte2.out");
//char x[M],y[M],xx[M],yy[M];
//int i,j,n,m,maxi,frx[300],fry[300];
//
//int main() {
// fi.getline(x,M);
// fi.getline(y,M);
// strcpy(xx,x);strcpy(yy,y);
// n=strlen(x);m=strlen(y);
// for(i=0;i<n;i++)
// if(xx[i]>='A' and xx[i]<='Z')xx[i]=xx[i]+32;
// for(i=0;i<m;i++)
// if(yy[i]>='A' and yy[i]<='Z')yy[i]=yy[i]+32;
// //a)
// for(i=0;i<n;i++) frx[xx[i]]++;
// for(i=0;i<m;i++) fry[yy[i]]++;
// for(i=1;i<=126;i++)
// maxi=max(maxi,frx[i]+fry[i]);
// fo<<maxi<<'\n';
// //b)
// int d,dif=0;
// for(i=1;i<=126;i++){
// d=frx[i]-fry[i];
// if(d<0)d=-d;
// dif+=d;
// }
// fo<<dif<<'\n';
// //c)
// char *p=strstr(x,y);
// char *q=strstr(y,x);
// if(p==x)fo<<strlen(y);
// else if(q==y)fo<<strlen(x);
// else fo<<0;
// fo<<'\n';
// return 0;
//}
//#include <fstream>
//#include <iostream>
//#include<cstring>
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("plaja.in");
////ofstream fo("plaja.out");
//struct element {int c,val;}t,st[3001];
//char c,s[301];
//int k,va,vb,i,n,x,numar,paranteza;
//bool cifra(char c){
//if(c>='0' and c<='9')return true;
//else return false;
//}
//int main() {
// fi.get(s,301);
// n=strlen(s);
// k=0;
// for(i=0;i<n;i++)
// {
// if(!cifra(s[i])){t.c=s[i];t.val=1;st[++k]=t;}//push ( ) A B
// else {
// x=x*10+s[i]-'0'; //face numar
// if(!cifra(s[i+1])) //numar gata construit(terminat)
// {
// if(st[k].c=='A' or st[k].c=='B')st[k].val*=x; //Ax sau Bx
// if(st[k].c==')'){ // (A2(B4))x
// va=vb=0;//calculam tot ( ... )
// k--;
// paranteza=1;//numar paranteze ) creste la inchise ++ i scade la deschise --
// while(paranteza){
// if(st[k].c=='A'){va+=st[k].val*x;} //A
// else if(st[k].c=='B'){vb+=st[k].val*x;} //B
// else if(st[k].c==')')paranteza++; // )
// else if(st[k].c=='(')paranteza--; // (
// k--;
// }
// t.c='A';t.val=va;st[++k]=t;
// t.c='B';t.val=vb;st[++k]=t;
// }
// x=0;
// }
// }
// }
// va=vb=0;
// while(k){ //calculam ce ramane la finalul stivei A2B4(A)(B3)
// if(st[k].c=='A'){va+=st[k].val;k--;}
// else if(st[k].c=='B'){vb+=st[k].val;k--;}
// else k--;
// }
// fo<<va<<" "<<vb;
// return 0;
//}
////5 8
////10111100
////00000100
////10100100
////00100100
////00110100
////matricea b
////0 1 0 0 0 0 1 1
////1 2 1 1 1 0 2 2
////0 3 0 2 2 0 3 3
////1 4 0 3 3 0 4 4
////2 5 0 0 4 0 5 5
//#include <fstream>
//using namespace std;
//ifstream fi("plaja.in");
//ofstream fo("plaja.out");
//struct element {int p,val;}t,st[1001];
//char c;
//int z,maxi,r,j,i,n,s,x,y,k,m,a[1001][1001],b[1001][1001];
//int main() {
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// { fi>>c; a[i][j]=1-(c-'0'); } //se schimba 1 cu 0 si 0 cu 1(sa pot calcula sumele)
// for(i=1;i<=n;i++) //calculez pe fiecare linie cate el. am pe verticala
// for(j=1;j<=m;j++)
// if(a[i][j]!=0) b[i][j]=b[i-1][j]+a[i][j];
// for(i=1;i<=n;i++)
// {
// k=0;
// for(j=1;j<=m;j++) //merg pe fiecare linie din b si amalizez eleemntele anterioare
// { //pt. fiecare linie pun pe o stiva elementele in ordine crescatoare
// while(k>0 and st[k].val>b[i][j]){st[k].p=0;st[k].val=0;k--;}//pop daca stiav are elemente mai mari
// t.p=j;t.val=b[i][j];st[++k]=t;//push
// for(z=1;z<=k;z++) //compar el. din capul stivei cu cele din restul stivei si calc. dreptunghiurile
// {
// r=st[z].val*(st[k].p-st[z].p+1); //valoare dreptunghiului
// maxi=max(maxi,r);
// }
// if(k>1 and st[k-1].val==st[k].val){st[k].p=0;st[k].val=0;k--;}//pop pt. elementele egale puse in stiva
// }
// }
// // for(i=1;i<=n;i++){for(j=1;j<=m;j++)fo<<b[i][j]<<" ";fo<<endl;}
// fo<<maxi;
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("intervale4.in");
//ofstream fo("intervale4.out");
//struct interval{ int x,y;};
//bool reuniune(interval p, interval q,interval &r){
// int st=max(p.x,q.x);
// int dr=min(p.y,q.y);
// if(st<=dr){ //daca se intersecteaza
// r.x=min(p.x,q.x); //facem reuniunea
// r.y=max(p.y,q.y);
// return true;
// }
// else return false;
// }
//int i,n,s,x,y,k;
//interval rez,t,st[100001];
//int main() {
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x>>y;
// t.x=x;t.y=y;
// while(k>0 and reuniune(st[k],t,rez)){t=rez;k--;}//pop
// st[++k]=t; //push
// }
// fo<<k<<'\n';
// return 0;
//}
//#include <fstream>//tot 60p cu long long p[101]
//using namespace std;
//ifstream fi("prodmax.in");
//ofstream fo("prodmax.out");
//int a[101][101],i,j,n,m;long long p[101],maxi;
//int main() {
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// fi>>a[i][j];
// for(j=1;j<=m;j++)p[j]=1;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// p[j]=p[j]*a[i][j];
// for(j=1;j<=m;j++)
// if(p[j]>maxi)maxi=p[j];
// for(j=1;j<=m;j++)
// if(p[j]==maxi) fo<<j<<' ';
// return 0;
//}
//#include <fstream>//60p cu int p[101]
//using namespace std;
//ifstream fi("maxmat.in");
//ofstream fo("maxmat.out");
//int a[101][101],i,j,n,m,maxi,p[101];
//int main() {
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// fi>>a[i][j];
// for(j=1;j<=m;j++)p[j]=1;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// p[j]=p[j]*a[i][j];
// for(j=1;j<=m;j++)
// if(p[j]>maxi)maxi=p[j];
// for(j=1;j<=m;j++)
// if(p[j]==maxi) fo<<j<<' ';
// return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fi("maxmat.in");
//ofstream fo("maxmat.out");
//int a[101][101],i,j,n,m,maxi;
//int main() {
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// fi>>a[i][j];
// for(i=1;i<=n;i++)
// {
// maxi=-100000;
// for(j=1;j<=m;j++)
// if(a[i][j]>maxi)maxi=a[i][j];
// for(j=1;j<=m;j++)
// if(a[i][j]==maxi){fo<<maxi<<" "<<j<<'\n';break;}
// }
// return 0;
//}
//#include <iostream>
//using namespace std;
//unsigned long long M,i,n,a[100003],b[100003];
//int main() {
// M=18446744073709551615;
// cin>>n;
// for(i=1;i<=n;i++) cin>>a[i]>>b[i];
// for(i=1;i<=n;i++) {
// if(a[i]!=0 and ((long double)M/(long double)a[i]<=(long double)b[i])) cout<<"Overflow!";
// else cout<<a[i]*b[i];
// cout<<'\n';
// }
// return 0;
//}
//#include <iostream>
//#include<cstring>
//#include<stdlib.h>
//using namespace std;
//int t,p,u,i,n,k,c[100003],b[100000];
//char s[20];
//int main() {
// cin>>n;cin.get();
// p=1;
// for(i=1;i<=n;i++){
// cin.get(s,100);cin.get();
// if(strstr(s,"pop")>0 and p<=u)p++;
// if(strstr(s,"front")>0 and p<=u)b[++t]=c[p];
// if(strstr(s,"push")>0){
// strcpy(s,s+5);
// c[++u]=atoi(s);
// }
// }
// for(i=1;i<=t;i++)cout<<b[i]<<'\n';
// return 0;
//}
//#include <limits>
//#include <iostream>
//using namespace std;
//unsigned long long i,n,a[100003],b[100003];
//int main() {
//
// cin>>n;
// for(i=1;i<=n;i++) cin>>a[i]>>b[i];
// for(i=1;i<=n;i++) {
// if(a[i]!=0 and (double)18446744073709551615/a[i]<=(double)b[i]
// and (double)18446744073709551615/b[i]<=(double)a[i])cout<<"Overflow!";
// else cout<<a[i]*b[i];
// cout<<'\n';
// }
// return 0;
//}
//#include <fstream>//
//#include<iostream>
//#include<algorithm>
//#define M 103
//#define MAX 999999
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("gigel.in");
////ofstream fo("gigel.out");
//int z,dif,ssol,k,maxi,j,i,t,n,m,a[M][M],s[M],ss[M],b[M][M];
//int poz_maxi(int lin){//determina pozitia maximului de pe linia lin
//int p,j,maxi=b[lin][1];
//for(j=1;j<=m;j++)
// if(b[lin][j]>=maxi){maxi=b[lin][j];p=j;}
//return p;
//}
//int poz_mini(int lin){//determina pozitia minimului de pe linia lin
//int p,j,mini=b[lin][1];
//for(j=1;j<=m;j++)
// if(b[lin][j]<=mini){mini=b[lin][j];p=j;}
//return p;
//}
//int main(){
// fi>>n>>m>>k;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++) fi>>a[i][j];
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++) b[i][j]=a[i][j];
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)s[i]+=a[i][j];
// for(i=1;i<=n;i++)ss[i]=s[i];
// sort(ss+1,ss+n+1); //sortez sumele
// t=1;
// for(i=1;i<=n+1;i++) //aleg o suma ce apare de cele mai multe ori
// if(ss[i]==ss[i-1])t++; //si suma asta o formez pe fiecare linie
// else {if(maxi<=t){maxi=t;ssol=ss[i-1];};t=1;}
// //rez
// for(i=1;i<=n;i++){
// if(s[i]>ssol){ //daca suma pe linie este mai mare
// dif=s[i]-ssol; //scad din elementele cele mai mari
// while(dif>0){
// j=poz_maxi(i);
// if(b[i][j]>=dif){b[i][j]-=dif;dif=0;}
// else {dif-=b[i][j];b[i][j]=0;}
// }
// }
// if(s[i]<ssol){ //daca suma pe linie este mai mica
// dif=ssol-s[i]; //adun din elementele cele mai mici
// while(dif>0){
// j=poz_mini(i);
// if(MAX-b[i][j]>=dif){b[i][j]+=dif;dif=0;}
// else {dif-=MAX-b[i][j];b[i][j]=MAX;}
// }
// }
// }
// // fo<<ssol<<endl; for(i=1;i<=n;i++)fo<<s[i]<<" ";fo<<endl;fo<<endl;
//// for(i=1;i<=n;i++){for(j=1;j<=m;j++)fo<<a[i][j]<<" ";fo<<'\n';}fo<<endl;
//// for(i=1;i<=n;i++){for(j=1;j<=m;j++)fo<<b[i][j]<<" ";fo<<'\n';}
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]!=b[i][j])z++;
// fo<<z<<'\n';
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]!=b[i][j])fo<<i<<" "<<j<<" "<<b[i][j]<<'\n';;
// //fo<<k<<" " <<maxi;
//return 0;
//}
//#include<iostream>
//using namespace std;
//int n,x,k,i,p,y,s;
//int main(){
// cin>>x>>y;
// s=x+y;
// while(x!=y){
// x=y;
// cin>>y;
// s+=y;
// }
// cout<<s;
// return 0;
//}
//#include<iostream>
//using namespace std;
//int n,x,k,i,p;
//int main(){
// cin>>n;
// for(k=2;k<=n;k++)
// if((n-k*(k+1)/2)%k==0){
// p=(n-k*(k+1)/2)/k;
// if(p>=0 and p*k+k*(k+1)/2==n)
// {
// for(i=1;i<=k;i++)cout<<p+i<<" ";
// cout<<'\n';cout<<endl;
// }
// }
// return 0;
//}
//#include<iostream>
//using namespace std;
//int n;
//int main(){
// cin>>n;
// cout<<n*(n+1)/2;
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("lac.in");
//ofstream fo("lac.out");
//struct punct{
//int i,j;
//}x,y,c[900000];
//int a[1001][1001],i,j,m,n,insule,peninsule,k=1;
//void Lee(punct x,int k){
// int i,j,p,u;punct y;
// p=1;u=1;
// c[u]=x;
// while(p<=u){
// x=c[p];p++;
// i=x.i;j=x.j;a[i][j]=k;
// if(i>1 and a[i-1][j]==1){y.i=i-1;y.j=j;c[++u]=y;}//N
// if(i<n and a[i+1][j]==1){y.i=i+1;y.j=j;c[++u]=y;}//S
// if(j>1 and a[i][j-1]==1){y.i=i;y.j=j-1;c[++u]=y;}//E
// if(j<m and a[i][j+1]==1){y.i=i;y.j=j+1;c[++u]=y;}//V
// }
//}
//int main(){
//fi>>n>>m;
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)fi>>a[i][j];
//for(i=1;i<=n;i++) //determinare mai intai peninsule!!!!(altfel 20p)
// for(j=1;j<=m;j++)
// if(i==1 or j==1 or i==n or j==m)
// {if(a[i][j]==1) { x.i=i; x.j=j;k++; Lee(x,k);peninsule++;}}
//for(i=1;i<=n;i++) //determinam insulele la sfarsit
// for(j=1;j<=m;j++)
// if(i!=1 and j!=1 and i!=n and j!=m) {
// if(a[i][j]==1){ x.i=i; x.j=j;k++; Lee(x,k);insule++;}
// }
////for(i=1;i<=n;i++){
//// for(j=1;j<=m;j++)fo<<a[i][j]<<" " ;
//// fo<<endl;
////}
//fo<<insule<<" "<<peninsule;
//return 0;
//}
//
//#include<fstream>
//#include<cstring>
//using namespace std;
//ifstream fi("paranteze1.in");
//ofstream fo("paranteze1.out");
//int a,b,x,y,z,sa,sb,m,j,n,i,maxi,k,st[1000];
//char t[300];
//int numar(int &j){
// int x=0,i;
//while(t[j]>='0' and t[j]<='9' and j<m){x=x*10+t[j]-'0';j++;}
//j--;//!!!!!!!!!!!!!!!
//}
//int main(){
// fi.get(t,300);
// m=strlen(t);
// sa=sb=0;//sume generale
// a=b=0; //sume partiale
// x=0;
// for(j=0;j<m;j++)
// {
// if(t[j]=='(')st[++k]=1;
// if(t[j]==')'){k--;z=numar(j);
// if(z){a=a*z;b=b*z;}
// if(k==0)sa+=a;sb+=b;a=b=0;
// }
// if(t[j]=='A'){z=numar(j);if(z)a=a*z;}
// if(t[j]=='B'){z=numar(j);if(z)b=b*z;}
// }
// fo<<sa<<" " <<sb<<'\n';
//return 0;
//}
////deque (pronounced like "deck")(acronym of double-ended queue)
//// (nu mai trebuie sa dau lungimea cozii!!!!
////operatii
////c.empty() - da true daca c este vida
////w=c.front(); -citeste w !!! elementul din capul cozii
////w=c.back(); -citeste w !!! elementul din sfarsitul listei cozii
////c.pop_front(); - extrage elemtul de la inceputul cozii
////c.pop_back(); - extrage elemtul de la sfarsitul cozii
////c.push_back(w); -pune w la sfarsitul cozii
////c.push_front(w); -pune w inceputul cozii
////c.swap(c1); - inverseaza coada c cu c1
////c.clear() -sterge toate elementele din lista
//#include<fstream>
//#include<iostream>
//#include<deque>
//using namespace std;
//ifstream fi("muzeu.in");
//ofstream fo("muzeu.out");
//struct punct
//{ int i, j;}w;
//deque <punct> c;
//int n,i,j;
//char a[255][255];
//int b[255][255];
//int di[]={ 1, -1, 0, 0};//S N E V
//int dj[]={ 0, 0, 1, -1};
//
//void Lee()
//{
// int k, ii, jj,i,j;
// punct w, w1;
// while(!c.empty()) //daca coada nu este vida
// {
// w=c.front(); //citeste el. din coada
// i = w.i;
// j = w.j;
// c.pop_front(); //avanseaza in coada
// for(k=0;k<4;k++)
// {
// ii = i + di[k];
// jj = j + dj[k];
// if((ii > 0 && ii <= n && jj > 0 && jj <= n)
// &&(b[ii][jj]>b[i][j]+1 || b[ii][jj] ==0 ) && a[ii][jj] == '.')
// {
// b[ii][jj]=b[i][j]+1;
// w1.i = ii;
// w1.j = jj;
// c.push_back(w1); //pune in coada
// }
// }
// }
//}
//
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++){
// fi>>a[i][j];
// if(a[i][j]=='P')
// {
// w.i=i;
// w.j=j;
// c.push_back(w);
// }
// if(a[i][j]=='#')b[i][j] = -2;
// }
// Lee();
// for(i = 1; i <= n; i++)
// {for(j = 1; j <= n; j++)
// {
// if(a[i][j]!='P' && b[i][j]==0) b[i][j]=-1;
// fo<<b[i][j]<<" ";
// }
// fo<<"\n";
// }
// return 0;
//}
//#include<fstream>//deque cu struct
//#include<iostream>
//#include<deque>
//using namespace std;
//ifstream fi("masina2.in");
//ofstream fo("masina2.out");
//struct punct
//{ int i, j;}w;
//deque <punct> c;
//int i,n,x,y,t;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>w.i>>w.j;
// c.push_back(w);
// }
//for(t=0;t<c.size();t++) //afisare el.cu at()
// fo<<c.at(t).i <<" "<<c.at(t).j<<endl;;
// while(!c.empty()){ //afisare deque
// w=c.front();
// c.pop_front();
// fo<<w.i<<" "<<w.j<<endl;;
// }
//return 0;
//}
//#include<fstream>
//#include<iostream>
//#include<deque>
//using namespace std;
//ifstream fi("masina2.in");
//ofstream fo("masina2.out");
//struct punct
//{ int i, j;};
//deque <int> c;
//int i,n,x,y;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x;
// c.push_back(x);
// }
//for(i=0;i<c.size();i++) //afisare el.cu at()
// fo<<c.at(i)<<" ";
// while(!c.empty()){ //afisare deque
// y=c.front();
// c.pop_front();
// fo<<y<<" ";
// }
//return 0;
//}
//#include<fstream>
//#include<iostream>
//#include<deque>
//using namespace std;
//ifstream fi("masina2.in");
//ofstream fo("masina2.out");
//struct punct
//{ int i, j;};
//deque <punct> c1;
//deque <punct> c2;
//int n,i,j,R,C;
//char a[55][55];
//int b[55][55],viz[55][55];
//int di[]={ 1, -1, 0, 0};//S N E V
//int dj[]={ 0, 0, 1, -1};
// int k, ii, jj;char sir[10],z;
// punct w, w1;
//int main()
//{
// fi>>R>>C;
// for(i=1;i<=R;i++)
// for(j=1;j<=C;j++){
// fi>>a[i][j];
// if(a[i][j]=='*')
// { w.i=i; w.j=j; c1.push_back(w); }
// if(a[i][j]=='X')b[i][j] = -2;
// }
//
////for(z=0;z<c1.size();z++)cout<<c1.at(z).i<<" "<<c1.at(z).j<<endl;
// fi>>n;fi.get();
// for(int p=1;p<=n;p++){ //luam fiecare directie
// fi.get(sir,10);fi.get();//S N E V
// if(sir[0]=='S')k=0;
// if(sir[0]=='N')k=1;
// if(sir[0]=='E')k=2;
// if(sir[0]=='V')k=3;
// while(!c1.empty()){ //daca coada nu este vida
// w=c1.front(); //citeste el. din coada
// i = w.i; j = w.j;
// c1.pop_front(); //avanseaza in coada
// do{ //pune in coada c2 toate punctele accesibile pentru fiecare punct din coada c1
// ii = i + di[k];
// jj = j + dj[k];
// if((ii > 0 && ii <= R && jj > 0 && jj <= C)&&( b[ii][jj] ==0 )
// &&viz[ii][jj]==0) //pune de mai multe ori acelasi punct in coada fara asta!!!
// {
// w1.i = ii; w1.j = jj; c2.push_back(w1); //pune in coada
// viz[ii][jj]=1;
// }
// i=ii;j=jj;
// }while(b[i][j]==0);
// }
// // for(z=0;z<c2.size();z++)cout<<c2.at(z).i<<" "<<c2.at(z).j<<endl;
// //se pune in coada c1 coada c2
// c1.swap(c2);//inverseaza continutul cozilor
// c2.clear(); //sterge tot din coada c2
// for(i=1;i<=R;i++)
// for(j=1;j<=C;j++)viz[i][j]=0;
// //cout<<c1.size()<<" "<<c2.size()<<endl;
// }
// while(!c1.empty()){w=c1.front();c1.pop_front();b[w.i][w.j]=2;}
// for(i = 1; i <= R; i++)
// {for(j = 1; j <= C; j++)
// {
// if(b[i][j]==0) fo<<".";
// if(b[i][j]==-2) fo<<"X";
// if(b[i][j]==2) fo<<"*";
//
// }
// fo<<"\n";
// }
// return 0;
//}
//#include<fstream>//deque cu struct
//#include<iostream>
//#include<deque>
//using namespace std;
//ifstream fi("masina2.in");
//ofstream fo("masina2.out");
//struct punct
//{ int i, j;}w;
//deque <punct> c;
//int i,n,x,y,t;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>w.i>>w.j;
// c.push_back(w);
// }
//for(t=0;t<c.size();t++) //afisare el.cu at()
// fo<<c.at(t).i <<" "<<c.at(t).j<<endl;;
// while(!c.empty()){ //afisare deque
// w=c.front();
// c.pop_front();
// fo<<w.i<<" "<<w.j<<endl;;
// }
//return 0;
//}
//#include<fstream>
//#include<iostream>
//#include<deque>
//using namespace std;
//ifstream fi("masina2.in");
//ofstream fo("masina2.out");
//struct punct
//{ int i, j;};
//deque <int> c;
//int i,n,x,y;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x;
// c.push_back(x);
// }
//for(i=0;i<c.size();i++) //afisare el.cu at()
// fo<<c.at(i)<<" ";
// while(!c.empty()){ //afisare deque
// y=c.front();
// c.pop_front();
// fo<<y<<" ";
// }
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("matrice7.in");
//ofstream fo("matrice7.out");
//int m,j,n,k,i,maxi,a[101][101],mini,p;
//int main(){
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++) fi>>a[i][j];
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]>maxi)maxi=a[i][j];
//
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(a[i][j]==maxi){
// mini=a[1][j];
// for(p=1;p<=n;p++)
// if(a[p][j]<mini)mini=a[p][j];
// a[i][j]=mini;
// }
// for(i=1;i<=n;i++)
// {
// for(j=1;j<=m;j++)
// fo<<a[i][j]<<" ";
// fo<<'\n';
// }
// return 0;
//}
//#include<iostream>
//using namespace std;
//int a[102][102],i,j,n,m,sol,maxi,fr[1000001];
//int main(){
// cin>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++) cin>>a[i][j];
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++) fr[a[i][j]]++;
// for(i=1000000;i>=1;i--)
// if(fr[i]>=2){sol=i;break;}
//
// if(sol!=0)cout<<sol;
// else cout<<"IMPOSIBIL";
// return 0;
//}
//#include <iostream>
//using namespace std;
//int z,l,a,anbisect,ok;
//int main()
//{
// cin>>z>>l>>a;
// if((a%4==0 and a%100!=0)or(a%400==0))anbisect=1;
// else anbisect=0;
// if(l==1 or l==3 or l==5 or l==7 or l==8 or l==10 or l==12)
// {
// if(z<31)z++;
// else if(z==31) //sfarsit de luna
// {
// l++;
// z=1;
// if(l==13) //sfarsit de luna 12(decembrie)
// {
// l=1;
// a++;
// }
// }
// }
// else if(l==4 or l==6 or l==9 or l==11)
// {
// if(z<30)z++;
// else if(z==30) //sfarsit de luna
// {
// l++;
// z=1;
// }
// }
// else if(l==2) //februarie
// {
// if(anbisect==1)
// if(z<29)z++;
// else if(z==29)//sfarsit de luna
// {
// l++;
// z=1;
// }
// if(anbisect==0)
// if(z<28)z++;
// else if(z==28)//sfarsit de luna
// {
// l++;
// z=1;
// }
// }
// cout<<z<<" "<<l<<" "<<a;
// return 0;
//}
//#include <iostream>
//
//using namespace std;
//int n, a[102][102], i, j, m, in[102],b[102];
//int main() {
//
//cin >> n >> m;
//for(i = 1; i <= n; i++)
// for(j = 1; j <= m; j++) {
// cin >> a[i][j];
// in[j] = j;
//}
//for(j = 1;j <= m;j++)b[j]=a[1][j];//Trebuie ordonata prima linie din matrice
////in alt vector, ca altfel prima linie din matrice se ordoneaza si restul liniilor din matrice
////raman pe loc !!!!!!!!!!!!!!!
//for(i = 1; i <= m-1; i++) //ordonez vectorul b si in
// for(j =i+ 1; j <= m; j++)
// if( b[i] > b[j] )
// {
// swap( b[i] , b[j] ) ;
// swap( in[i] , in[j] ) ;
// }
//for(i = 1; i <= n; i++)//afisare solutie
// {
// for(j = 1; j <= m; j++)
// cout << a[i][in[j]] << ' ';
// cout << '\n';
//}
//return 0;
//}
//
//#include<cmath>
//#include<iostream>
//using namespace std;
//double B,b,L,h,LL;
//int main(){
// cin>>B>>b>>L;
// LL=(B-b)/2;
// h=sqrt(L*L-LL*LL);
// cout<<sqrt(h*h+(B-LL)*(B-LL));
//return 0;
//}
////deque (pronounced like "deck")(acronym of double-ended queue)
//// (nu mai trebuie sa dau lungimea cozii!!!!
////operatii
////c.empty() - da true daca c este vida
////w=c.front(); -citeste w !!! elementul din capul cozii
////c.pop_front(); - extrage elemtul de la inceputul cozii
////c.pop_back(); - extrage elemtul de la sfarsitul cozii
////c.push_back(w); -pune w la sfarsitul cozii
////c.push_front(w); -pune w inceputul cozii
////c.clear() -sterge toate elementele din lista
//#include<fstream>
//#include<iostream>
//#include<deque>
//using namespace std;
//ifstream fi("muzeu.in");
//ofstream fo("muzeu.out");
//struct punct
//{ int i, j;}w;
//deque <punct> c;
//int n,i,j;
//char a[255][255];
//int b[255][255];
//int di[]={ 1, -1, 0, 0};//S N E V
//int dj[]={ 0, 0, 1, -1};
//
//void Lee()
//{
// int k, ii, jj,i,j;
// punct w, w1;
// while(!c.empty()) //daca coada nu este vida
// {
// w=c.front(); //citeste el. din coada
// i = w.i;
// j = w.j;
// c.pop_front(); //avanseaza in coada
// for(k=0;k<4;k++)
// {
// ii = i + di[k];
// jj = j + dj[k];
// if((ii > 0 && ii <= n && jj > 0 && jj <= n)
// &&(b[ii][jj]>b[i][j]+1 || b[ii][jj] ==0 ) && a[ii][jj] == '.')
// {
// b[ii][jj]=b[i][j]+1;
// w1.i = ii;
// w1.j = jj;
// c.push_back(w1); //pune in coada
// }
// }
// }
//}
//
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++){
// fi>>a[i][j];
// if(a[i][j]=='P')
// {
// w.i=i;
// w.j=j;
// c.push_back(w);
// }
// if(a[i][j]=='#')b[i][j] = -2;
// }
// Lee();
// for(i = 1; i <= n; i++)
// {for(j = 1; j <= n; j++)
// {
// if(a[i][j]!='P' && b[i][j]==0) b[i][j]=-1;
// fo<<b[i][j]<<" ";
// }
// fo<<"\n";
// }
// return 0;
//}
////Lee cu coada dinamica queue (nu mai trebuie sa dau lungimea cozii!!!!
////operatii
////c.empty() - da true daca c este vida
////w=c.front(); -citeste w !!! elementul din capul cozii
////c.pop(); - extrage elemtul din coada
////c.push(w); -pune w in coada
//#include<fstream>
//#include<iostream>
//#include<queue>
//using namespace std;
//ifstream fi("muzeu.in");
//ofstream fo("muzeu.out");
//struct punct
//{ int i, j;}w;
//queue <punct> c;
//int n,i,j;
//char a[255][255];
//int b[255][255];
//int di[]={ 1, -1, 0, 0};//S N E V
//int dj[]={ 0, 0, 1, -1};
//
//void Lee()
//{
// int k, ii, jj,i,j;
// punct w, w1;
// while(!c.empty()) //daca coada nu este vida
// {
// w=c.front(); //citeste el. din coada
// i = w.i;
// j = w.j;
// c.pop(); //avanseaza in coada
// for(k=0;k<4;k++)
// {
// ii = i + di[k];
// jj = j + dj[k];
// if((ii > 0 && ii <= n && jj > 0 && jj <= n)
// &&(b[ii][jj]>b[i][j]+1 || b[ii][jj] ==0 ) && a[ii][jj] == '.')
// {
// b[ii][jj]=b[i][j]+1;
// w1.i = ii;
// w1.j = jj;
// c.push(w1); //pune in coada
// }
// }
// }
//}
//
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++){
// fi>>a[i][j];
// if(a[i][j]=='P')
// {
// w.i=i;
// w.j=j;
// c.push(w);
// }
// if(a[i][j]=='#')b[i][j] = -2;
// }
// Lee();
// for(i = 1; i <= n; i++)
// {for(j = 1; j <= n; j++)
// {
// if(a[i][j]!='P' && b[i][j]==0) b[i][j]=-1;
// fo<<b[i][j]<<" ";
// }
// fo<<"\n";
// }
// return 0;
//}
//#include<iostream>//413
//using namespace std;
//int a[101][101],i,j,n,m,s,maxi;
//int main(){
//cin>>m>>n;
//for(i=1;i<=m;i++)
// for(j=1;j<=n;j++)
// cin>>a[i][j];
//for(i=1;i<=m;i++)
// {
// s=0;
// for(j=1;j<=n;j++)s=s+a[i][j];
// maxi=-20000000;
// for(j=1;j<=n;j++)
// if(a[i][j]>maxi)maxi=a[i][j];
// cout<<s-maxi<<" ";
// }
//return 0;
//}
//#include<fstream>
//#include<iostream>
//using namespace std;
//ifstream f("roboti1.in");
//ofstream g("roboti1.out");
//struct robot{
// int i,j; //pozitie robot
// char d; //directie de deplasare robot
// int ok; //ok=1 =>robot dezactivat (ok=0 robot activ)
//};
//int dir,fr[51][51],a[51][51],p,q,i,n,m,k,t,comanda;
//int maxi,pi,pj,w,z,j;
//char b[51][51];
//robot r[100];
//int main(){
// f>>p>>q;
// f>>n; //n numarul de roboti
// for(k=1;k<=n;k++){f>>r[k].i>>r[k].j>>r[k].d;fr[r[k].i][r[k].j]=1;}
// f>>m; //m numarul de pasi facut de roboti
// for(k=1;k<=n;k++)f>>b[k];
// //for(k=1;k<=n;k++)g<<b[k]<<" ";
// for(k=1;k<=m;k++){
// for(t=1;t<=n;t++)//miscam fiecare robot din cei n
// if(r[t].ok==0) // t robot activ
// {
// comanda=b[t][k-1];
// if(comanda=='F'){
// if(r[t].d=='N')r[t].i--;
// if(r[t].d=='S')r[t].i++;
// if(r[t].d=='E')r[t].j++;
// if(r[t].d=='V')r[t].j--;
// fr[r[t].i][r[t].j]++;
// }
// if(comanda=='R'){
// if(r[t].d=='N')r[t].d='E';
// else if(r[t].d=='E')r[t].d='S';
// else if(r[t].d=='S')r[t].d='V';
// else if(r[t].d=='V')r[t].d='N';
// }
// if(comanda=='L'){
// if(r[t].d=='N')r[t].d='V';
// else if(r[t].d=='V')r[t].d='S';
// else if(r[t].d=='S')r[t].d='E';
// else if(r[t].d=='E')r[t].d='N';
// }
// }
// for(t=1;t<=n;t++) //se dezactiveaza robotii daca este cazul
// if(r[t].ok==0)
// {
// if(r[t].i==0 or r[t].j==0 or r[t].i==p+1 or r[t].j==q+1)//robotul iese din matrice
// r[t].ok=1; //se dezactiveaza robotul t
// w=0; //cautam roboti ce sunt in aceisi celula(pozitie)
// for(z=1;z<=n;z++)
// if(r[t].i==r[z].i and r[t].j==r[z].j and r[z].ok==0) w++;
// if(w>1)//dezactivam robotii ce sunt in aceisi celula(pozitie)
// for(z=1;z<=n;z++)
// if(r[t].i==r[z].i and r[t].j==r[z].j and r[z].ok==0)
// r[z].ok=1;
// }
//
// }
// w=0;
// for(t=1;t<=n;t++)
// if(r[t].ok==0)w++;
// g<<w<<'\n';
// for(i=1;i<=p;i++)
// for(j=1;j<=q;j++)
// if(fr[i][j]>maxi){maxi=fr[i][j];pi=i;pj=j; }
// g<<pi<<" "<<pj<<" "<<maxi;
// // for(i=1;i<=p;i++){for(j=1;j<=q;j++)cout<<fr[i][j]<<" ";cout<<endl;}
// return 0;
//}
//#include <iostream>
//using namespace std;
//unsigned long long f,c,nrfin,n10,r,b,x,n,d,k,maxi,cif,i,a,v[100],t;
//int main(){
//cin>>n>>b>>c;
//f=1;
//while(n)
//{cif=n%10;
//n10=n10+cif*f;
//f=f*b;
//n=n/10;
//}
//a=n10;
//b=c;
//do{
//r=a%b;
//v[++t]=r;
//a=a/b;
//}while(a);
//for(i=t;i>=1;i--)cout<<v[i];
//return 0;
//}
//#include <iostream>
//#include<cstring>
//using namespace std;
//int n,i,j,m,k;
//char *p,a[300],b[300],sep[]=" ",x[256][256],y[256][256],z[256][256];
//
//int main()
//{
//cin.get(a,300);
//cin.get();
//cin.get(b,300);
//for(i=0;i<strlen(a);i++)
// if(a[i]>='A' and a[i]<='Z')a[i]=a[i]+32;
//for(i=0;i<strlen(b);i++)
// if(b[i]>='A' and b[i]<='Z')b[i]=b[i]+32;
////cout<<a<<" "<<b<<endl;
//p=strtok(a,sep);
//while(p){
// n++;
// strcpy(x[n],p);
// p=strtok(0,sep);
//}
//p=strtok(b,sep);
//while(p){
// m++;
// strcpy(y[m],p);
// p=strtok(0,sep);
//}
//for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(strcmp(x[i],y[j])==0)strcpy(z[++k],x[i]);
//for(i=1;i<=k;i++)
// for(j=i+1;j<=k;j++)
// if(strcmp(z[i],z[j])>0)swap(z[i],z[j]);
//cout<<z[1]<<'\n';
//for(i=1;i<k;i++)
// if(strcmp(z[i],z[i+1])!=0)cout<<z[i+1]<<'\n';
//return 0;
//}
////nu trebuie calculat 2^20000 mod 3 ca este 1 sau 2
////2^p(p par)=4^(p/2)=(3+1)^(p/2)=M3+1
////2^p(p impar)=2*(4^(p/2))=2((3+1)^(p/2))=2(M3+1)=M3+2
//#include<fstream>
//using namespace std;
//ifstream fi("binremove.in");
//ofstream fo("binremove.out");
//int i,j,n,t,s,p;
//int a[50003];
//long long k;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// fi>>p;
// for(i=1;i<=p;i++){
// fi>>t;t=n-t;
// for(j=t;j<=n;j++) a[j]=a[j+1];
// n--;
// //for(j=1;j<=n;j++)fo<<a[j]<<" ";fo<<endl;
// s=0;
// for(j=n;j>=1;j--)
// if(a[j]==1)
// if((j-1)%2==0)s+=1;else s+=2;
// if(s%3==0)fo<<1<<'\n';
// else fo<<0<<'\n';
// }
// return 0;
//}
////n=25
////este o proggresie geometrica =>(i i*j i*j*j) !!!!
////1 5^2 =>4 solutii (1^2 5^2)(2^2 5^2)(3^2 5^2)(4^2 5^2)
////2 2*3^2 =>2 solutii (2 2*3^2)(2*2^2 2*3^2)
////de aici formula k+=j-1
////se bifeaza a[i*j*j]=1 deoarece solutii ce incep cu i*j*j sunt deja calculate
//#include<fstream> //var I
//using namespace std;
//ifstream fi("tg.in");
//ofstream fo("tg.out");
//int i,j,n;
//bool a[4000003];
//long long k;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// if(a[i]==0)
// for(j=1;i*j*j<=n;j++) {a[i*j*j]=1;k+=j-1;}
// fo<<k<<'\n';
// return 0;
//}
//#include<fstream>//brute force afiseaza toate solutiile
//using namespace std;
//ifstream fi("tg.in");
//ofstream fo("tg.out");
//int i,j,n,p;
//bool a[4000003];
//long long k;
//int main(){
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=i+1;j<=n;j++)
// for(p=j+1;p<=n;p++)
// if(i*p==j*j and i<j and j<p)
// fo<<i<<" "<<j<<" "<<p<<'\n';
// return 0;
//}
////nlog(n) 45p timpul!!! var II
//#include<fstream>
//#include<cmath>
//using namespace std;
//ifstream fi("tg.in");
//ofstream fo("tg.out");
//
//int main()
//{
// long long n,s,a,x,k1,k2,t,d,c;
// fi>>n;
// s=0;
// for (a=1;a<=n-2;a++)
// {
// x=1;
// t=a;
// d=2;
// while(d*d<=t)
// {
// c=0;
// while(t%d==0)
// {
// c++;
// t=t/d;
// }
// if(c%2==1)x=x*d;
// d++;
// }
// if(t>1)x=x*t;
// k1=sqrt((double)(a/x));
// k2=sqrt((double)(n/x));
// s=s+k2-k1;
// }
// fo<<s<<endl;
// return 0;
//}
bodnariuc danut danutbod