//Bellman Ford O(m*n) 100p ultima varianta cu viz[]!!!
//pun in coada numai nodurile nevizitate deja
//dar tot creapa testul 9
#include<fstream>
#include<iostream>
#define inf 1000000000
#define NMax 50003
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct Nod
{
int nod, cost;
Nod *next;
};
Nod *t,*Vecin[NMax];
int i,j,m,n,x,y,costul,p,u,nod;
int viz[NMax],d[NMax],coada[30*NMax];
void adauga(int x, int y, int costul){
Nod *q = new Nod;
q->nod = y;
q->cost = costul;
q->next = Vecin[x];
Vecin[x] = q;
}
int main()
{
//cout<<sizeof(coada);
f>>n>>m;
for(i=1;i<=m;++i)
{
f>>x>>y>>costul;
adauga(x,y,costul);
}
for(i=1;i<=n;++i) d[i]=inf;
p=1;u=1;
coada[u]=1;
viz[1]=1;
d[1]=0;
while (p<=u)
{
j=coada[p];
viz[j]=0;
p++;
t=Vecin[j];
while(t){
if(d[t->nod]>d[j]+t->cost)
{
d[t->nod]=d[j]+t->cost;
if(viz[t->nod]==0){
coada[++u]=t->nod;
viz[t->nod]=1;
}
}
t=t->next;
}
// cout<<u<<'\n';
}
for ( int i = 2; i <= n; i++ )
if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
f.close();
g.close();
}
////infoarena Dijkstra afisare valori minime de la nodul 1
////Bellman Ford O(m*n) 100p n=50.000
//// cu pointeri
//#include<fstream>
//#define inf 1000000000
//#define NMax 50003
//using namespace std;
//ifstream f("dijkstra.in");
//ofstream g("dijkstra.out");
//struct Nod
//{
// int nod, cost;
// Nod *urm;
//};
//Nod *t,*L[NMax];
//int j,m,n,x,y,costul,nod,d[NMax],coada[5*NMax];
//void adauga(int x, int y, int costul)
//{
// Nod *q = new Nod;
// q->nod = y;
// q->cost = costul;
// q->urm = L[x];
// L[x] = q;
//}
//void bellman_ford(){
// int p,u,i;
// for(i=1;i<=n;i++) d[i]=inf;
// p=1;u=1;
// coada[u]=1;
// d[1]=0;
// while (p<=u)
// {
// j=coada[p];p++;
// t=L[j];
// while(t){
// if(d[t->nod]>d[j]+t->cost)
// {
// coada[++u]=t->nod;
// d[t->nod]=d[j]+t->cost;
// }
// t=t->urm;
// }
// }
//}
//int main()
//{
// int i;
// f>>n>>m;
// for(i=1;i<=m;i++)
// {
// f>>x>>y>>costul;
// adauga(x,y,costul);
// }
// bellman_ford();
// for ( int i = 2; i <= n; i++ )
// if(d[i] == inf) g<<0<<" ";else g<< d[i]<<" ";
// f.close();
// g.close();
//}
//#include<algorithm>
//#include <fstream>
//#define N 100003
//#define M 200003
//using namespace std;
//ifstream fi("ctc.in");
//ofstream fo("ctc.out");
//struct nod{
// int x;
// nod*urm;
// };
// nod *L[N],*LT[N],*ctc[N];
// nod*p;
// int viz[N],vizt[N],i,j,k,n,m,x,y;
// int st[N],nc;
//void Adauga(nod*V[],int i,int j){//pune in coada lui i(V[i]) nodul j in graf
// nod*p; //adauga in e liste de adiacenta L,LT,ctc
// p=new nod;
// p->x=j;
// //pune in coada lui i nodul j
// p->urm=V[i];
// V[i]=p;
// }
//void dfs(int j){ //plus
// nod *p;
// viz[j]=1;
// p=L[j];
// while(p){
// if(viz[p->x]==0)dfs(p->x);
// p=p->urm;
// }
// st[++k]=j;
//}
//void dfst(int j){ //minus
// nod *p;
// Adauga(ctc,nc,j);
// vizt[j]=1;
// p=LT[j];
// while(p){
// if(vizt[p->x]==0)dfst(p->x);
// p=p->urm;
// }
//}
//int main(){
// fi>>n>>m;
// for(i=1;i<=m;i++){
// fi>>x>>y;
// Adauga(L,x,y);//mem graf normal
// Adauga(LT,y,x);//mem graf transpus
// }
// for(i=1;i<=n;i++) //parcurgere graf normal
// if(viz[i]==0)dfs(i);
// for(i=k;i>=1;i--) //parcurgere stiva pe graful transpus
// if(vizt[st[i]]==0)
// {nc++;dfst(st[i]);}
//// fo<<nc<<'\n';
//// for(i=1;i<=nc;i++){ //afisare ctc
//// p=ctc[i];
//// while(p){
//// fo<<p->x<<" ";
//// p=p->urm;
//// }
//// fo<<'\n';
//// }
//return 0;
//}
//#include <fstream>//100p O(n+m) (Kosaraju)
//#include<vector>
//#define Nmax 100001
//using namespace std;
//ifstream f("ctc.in"); ofstream g("ctc.out");
//vector <int> a[Nmax];
//vector <int> at[Nmax];vector <int> ctc[Nmax];
//int n, m,k,nrc, viz[Nmax],st[Nmax];
//void df (int nod)
//{
// int i;
// viz[nod] = 1;
// for (i = 0; i < a[nod].size(); i++)
// if (viz[a[nod][i]]==0) df(a[nod][i]);
// st[++k]=nod;
//}
//void dft (int nod) //df transpus
//{
// int i;
// viz[nod] = 1;ctc[nrc].push_back(nod);
// for (i = 0; i < at[nod].size(); i++)
// if (viz[at[nod][i]]==0)
// dft(at[nod][i]);
//}
//int main() {
// int i, j, x, y;
// f >> n >> m;
// for (i = 1; i <= m; i++)
// {
// f >> x >> y;
// a[x].push_back(y);
// at[y].push_back(x);
// }
//
////for(i=1;i<=n;i++){for (j=0; j<at[i].size();j++) g<<at[i][j]<<" "; g<<'\n';}
//for (i = 1; i <= n; i++)
// if (viz[i]==0) df(i);
////for(i=1;i<=n;i++)g<<st[i]<<" ";g<<endl;
// for (i = 1; i <= n; i++) viz[i]=0;
// for (i = n; i >=1; i--)
// if (viz[st[i]]==0) {
// nrc++;
// dft(st[i]);
// }
//g<<nrc<<'\n';
//for(i=1;i<=nrc;i++){
// for (j=0; j<ctc[i].size();j++)
// g<<ctc[i][j]<<" ";
// g<<'\n';
//}
// return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("arb.in");
//ofstream fo("arb.out");
//struct Nod{
//int info;
//Nod *st,*dr;
//}*r;
//int i,n,x;
//void inserare(Nod*&r,int x){
//Nod*q,*p=new Nod;
//p->info=x;
//p->st=0;
//p->dr=0;
//if(r==0){r=p;return;}
//q=r;
//while(1){
// if(q->info==x){delete p;return;}
// if(x<q->info)
// if(q->st)q=q->st;
// else {q->st=p; return;}
// else
// if(q->dr)q=q->dr;
// else {q->dr=p; return;}
// }
//}
//void afisare(Nod*r){
//if(r){
// afisare(r->st);
// fo<<r->info<< " ";
// afisare(r->dr);
//}
//}
//int cautare(Nod*r,int x){
//if(r){
// if(x==r->info)return 1;
// else if(x<r->info)cautare(r->st,x);
// else cautare(r->dr,x);
// }
// else return 0;
//}
////stergere
////echilibrare
//int main(){
// r=0;
// fi>>n;
// for(i=1;i<=n;i++)
// {fi>>x;
// inserare(r,x);
// }
// afisare(r);
// fo<<endl<<cautare(r,41);
//return 0;
//}
////alg lui Prim
//// - arbore partial de cost minim
//#include <fstream>
//using namespace std;
//ifstream fi("gr.in");
//ofstream fo("gr.out");
//struct muchie{
//int x,y,c;
//};
//muchie mu[10000];
//int n,i,j,k,t,m,c1,c2,mini,cost_arb;
//int a[10000];
//int main()
//{
// fi>>n>>m;
// for(i=1;i<=m;i++)
// fi>>mu[i].x>>mu[i].y>>mu[i].c;
// // for(i=1;i<=m;i++)
//// fo<<mu[i].x<<" "<<mu[i].y<<" "<<mu[i].c<<endl;;
// a[1]=1;//se alege primul nod in multimea finala
// k=1;
// while(k<n){
// mini=1000000; //aflam muchia de cost minim ce leaga
// for(i=1;i<=m;i++) //grupul final de exterior
// if(a[mu[i].x]!=a[mu[i].y])
// if(mu[i].c<mini){mini=mu[i].c;t=i;} //muchia t este minima
// k++;
// cost_arb+=mu[t].c;
// a[mu[t].x]=a[mu[t].y]=1; //pun in multimea finala capetele muchiei selectate
// fo<< mu[t].x<<" "<<mu[t].y<<" "<<mu[t].c<<endl;//afisez muchia selectata
// }
//fo<<endl<<cost_arb;
// return 0;
//}
////problema turnurilor lui Hanoi 2n-1 operatii pentru n discuri
////Se dau 3 tije notate cu a,b,c. Pe discul a se gasesc n discuri asezate in descrescatoare se sus in jos.
////Se cere sa se mute discurile de pe tija a pe tija c(cu intermediar b) respectand urmatoarele reguli:
//#include <fstream>
//using namespace std;
//fstream f("han.in", ios::in);
//fstream g("han.out", ios::out);
//char a,b,c;
//int n;
//void han(int n,char a,char b,char c)
//{
// if(n==1) g<<a<<"->"<<c<<'\n';
// else
// {
// han(n-1,a,c,b);
// g<<a<<"->"<<c<<'\n';
// han(n-1,b,a,c);
// }
//}
//int main()
//{
// f>>n;
// a='A'; b='B'; c='C';
// g<<2*n-1<<'\n';
// han(n,a,c,b);
//return 0;
//}
//#include<iostream>
//using namespace std;
//struct nod
//{
// int info;
// nod*urm;
//}*prim;
//void adauga(nod*&prim,int x)
//{
// nod*q,*p=new nod;
// p->info=x;
// p->urm=0;
// if(prim==0)
// {
// prim=p;
// }
// else
// {
// q=prim;
// while(q->urm)q=q->urm;
// q->urm=p;
// }
//}
//void listare(nod* prim){
//nod*p;
//p=prim;
//while(p){
// cout<<p->info<<" ";
// p=p->urm;
//}
//cout<<endl;
//}
//void ins_cresc(nod *&p, int x){
//nod*q,*t;
//t=new nod;
//t->info=x;
//t->urm=0;
//if(x<p->info){t->urm=p;p=t;return; }//adaug primul el
//q=p;
//while(q->urm->info<=x){q=q->urm;
//
//}
//}
//int n,i,x;
//int main()
//{
// cin>>n;
// for(i=1; i<=n; i++)
// {
// cin>>x;
// adauga(prim,x);
// }
// listare(prim);
// inserare(prim);
// listare(prim);
// return 0;
//}
////var I cu upper_bound
//#include<fstream>
//#include<algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("maraton.in");
//ofstream fo("maraton.out");
//long long q,d,v,t,timp,j,k,i,n,a[M],b[M];
////fara long long nu merge bine !!! (nu stiu de ce)
//int main() {
// fi>>n;
// for(i=1;i<=n;i++) {
// fi>>d>>v;
// timp=d/v;
// if(d%v!=0)timp++;//timp=2.3 => 3
// a[i]=timp;
// }
// sort(a+1,a+n+1);
// //for(i=1;i<=n;i++) fo<<a[i]<<' ';fo<<endl;
// fi>>k;
// for(i=1;i<=k;i++){
// fi>>t;
// fo<<(upper_bound(a+1,a+n+1,t)-a)-1<<'\n';
// }
// return 0;
//}
//var II manuala
//#include<fstream>
//#include<algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("maraton.in");
//ofstream fo("maraton.out");
//int q,d,v,t,timp,j,k,i,n,a[M],b[M];
////cauta binar pozitia primului element mai mare ca x
////trebuie pus un element in plus al sfarsit
//// n++;
//// a[n]=a[n-1]+3;
//int cauta_binDR(int x){
// int st,dr,mij;
// st=1;dr=n;
// while(st<dr)
// {
// mij=(st+dr)/2;
// if(x>=a[mij])st=mij+1;
// else dr=mij;
// }
//return st;
//}
//int main() {
// fi>>n;
// for(i=1;i<=n;i++) {
// fi>>d>>v;
// timp=d/v;
// if(d%v!=0)timp++;//timp=2.3 => 3
// a[i]=timp;
// }
// sort(a+1,a+n+1);
// n++;
// a[n]=a[n-1]+3;
// //for(i=1;i<=n;i++) fo<<a[i]<<' ';fo<<endl;
// fi>>k;
// for(i=1;i<=k;i++){
// fi>>t;
// fo<<cauta_binDR(t)-1<<'\n';
// }
// return 0;
//}
//// var I
////paduri de multimi disjuncte
//// cu compresia drumurilor ( cu T[rad]=0; )
//#include<iostream>
//#include <fstream>
//#define M 100003
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("gasti.in");
////ofstream fo("gasti.out");
//int nrc,k,T[M],a[5*M],b[5*M];//vectorul de tati(T[] )
//int r1,r2,i,n,m,x,y,op,RT[M],sol[5*M];
//int rad(int x) //afla radacina nodului x
//{
// int r, y;
// r=x; //merg in sus pe arbore pana gasesc radacina
// while(T[r]!=0)r=T[r];// un nod cu tata 0)
// while(T[x]!=0) //aplic compresia drumurilor
// { y = T[x]; T[x] = r; x = y; }
// return r; //returnez radacina
//
//}
//void reuneste( int x,int y)
//{
// if(RT[x]>RT[y]) T[y]=x; //unesc multimea cu rang mai mic de cea cu rang mai mare
// else T[x]=y;
// if(RT[x]==RT[y]) RT[y]++; //in caz ca rangurile erau egale atunci cresc
//} //rangul noii multimi cu 1
//int main()
//{
// fi>>n>>m;
// for(i=1;i<=m;i++) fi>>a[i]>>b[i];
// nrc=n;
// sol[++k]=nrc;
// for(i=m;i>1;i--){
// r1=rad(a[i]);
// r2=rad(b[i]);
// if(r1==r2)sol[++k]=nrc;
// else {sol[++k]=--nrc;reuneste(r1,r2);}
// }
// for(i=k;i>=1;i--)fo<<sol[i]<<'\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;
//}
//// 50p cu mat. de adiacenta(nu incape)
//// Parcurgerea Breadth First(BF) var III BFS infoarena
//#include <fstream>
//#define nmax 5600
//using namespace std;
//ifstream f("bfs.in");
//ofstream g("bfs.out");
//int n,m,a[nmax][nmax],x,y,c[nmax],u,p,viz[nmax],i,v,s;
//void bfs(int x,int numar){
// int i,p,u,v;
// p=1; u=1;
// c[1]=x; viz[x]=numar;
// while(p<=u)
// {
// v=c[p]; //se ia nodul din varful cozii
// for(i=1;i<=n;i++)
// if(a[v][i]==1 && viz[i]==0) //se cauta toti vecinii nevizitati
// { //pentru nodul v
// u++;
// c[u]=i; //se pun in coada vecinii gasiti
// viz[i]=viz[v]+1;
// }
// p++;
// }
//}
//int main()
//{
// f >> n >> m >>s;
// for(i=1;i<=m;i++)
// {
// f >> x >> y;
// if(x!=y)a[x][y]=1;
// }
// bfs(s,1);
//
// for(i=1;i<=n;i++) g<<viz[i]-1<<" ";
// f.close(); g.close();
// return 0;
//}
//
////100p var I
////reprezentare graf cu lista de adiacenta (cu pointeri)
////implementare DF
////fac vector de frecventa cu numarul de noduri din fiecare
////componenta conexa - pentru numarare avem doua cazuri
////numarare solutii
////caz I 1 2 3 4 4 7 7 7 => sol=7*7+7*7+7*7
////(fiecare 7 cu fiecare 7)=(7*7)*nr7(nr7-1)/2
////caz II cazul 2 3 5 5 5 7 =>sol=5*7+5*7+5*7
//#include<algorithm>
//#include <fstream>
//#define M 100003
//using namespace std;
//ifstream fi("gasti.in");
//ofstream fo("gasti.out");
//struct nod{
// int x;
// nod*urm;
// };
// nod *L[M];
// nod*p;
// int coada[M],viz[M],i,j,k,n,m,x,y;
// long long fr[M];
//void adauga(int i,int j){//pune in coada lui i(L[i]) nodul j
// nod*p;
// p=new nod;
// p->x=j;
// //pune in coada lui i nodul j
// p->urm=L[i];
// L[i]=p;
// }
//bool vecin(int i,int j){//verifica daca i si j sunt vecini
// nod*p;
// p=L[i];
// while(p){
// if(p->x==j)return true;
// p=p->urm;
// }
// return false;
// }
//void DF(int y,int k){
// nod*p;
// viz[y]=k;
// p=L[y];
// while(p){
// if(viz[p->x]==0)DF(p->x,k);
// p=p->urm;
// }
// }
//
//int main()
//{
// fi>>n>>m;
// for(i=1;i<=n;i++)L[i]=0;//se fac liste vide
// for(i=1;i<=m;i++){
// fi>>x>>y;
// adauga(x,y);
// adauga(y,x);
// }
// for(i=1;i<=n;i++)
// if(viz[i]==0){k++;DF(i,k);}
// for(i=1;i<=n;i++)fr[viz[i]]++;
// fo<<k<<" ";
// //b)
//// for(i=1;i<=n;i++)fo<<viz[i]<<" ";fo<<endl;
//// for(i=1;i<=k;i++)fo<<fr[i]<<" ";fo<<endl;
// sort(fr+1,fr+k+1);
// long long sol,nr;
// int z;
// if(fr[k]==fr[k-1]){ //cazul 1 2 3 4 4 7 7 7 => sol=7*7+7*7+7*7 (fiecare 7 cu fiecare 7)=(7*7)*nr7(nr7-1)/2
// z=k;
// while(z>1 and fr[z]==fr[z-1])z--;
// nr=k-z+1; //nr==nr7
// sol=(((fr[k]%666013)*(fr[k]%666013))%666013*(nr*(nr-1)/2)%666013)%666013;
// }
// else //fr[k]!=fr[k-1] cazul 2 3 5 5 5 7 =>sol=5*7+5*7+5*7
// {
// z=k;
// sol=fr[k]*fr[k-1];
// z--;
// while(z>1 and fr[z]==fr[z-1]){sol=sol%666013+(fr[k]*fr[z-1])%666013;z--;}
// }
// fo<<sol%666013<<endl;;
//
// return 0;
//}
////100p var II
////reprezentare graf cu lista de adiacenta (cu pointeri)
////implementare BF cu coada implementata dinamic manual cu pointeri
////fac vector de frecventa cu numarul de noduri din fiecare
////componenta conexa - pentru numarare avem doua cazuri
////numarare solutii
////caz I 1 2 3 4 4 7 7 7 => sol=7*7+7*7+7*7
////(fiecare 7 cu fiecare 7)=(7*7)*nr7(nr7-1)/2
////caz II cazul 2 3 5 5 5 7 =>sol=5*7+5*7+5*7
//#include<algorithm>
//#include <fstream>
//#define M 100003
//using namespace std;
//ifstream fi("gasti.in");
//ofstream fo("gasti.out");
//struct nod{
// int x;
// nod*urm;
// };
// nod *L[M];
// nod*p;
// int coada[M],viz[M],i,j,k,n,m,x,y;
// long long fr[M];
//void adauga(int i,int j){//pune in coada lui i(L[i]) nodul j
// nod*p;
// p=new nod;
// p->x=j;
// //pune in coada lui i nodul j
// p->urm=L[i];
// L[i]=p;
// }
//bool vecin(int i,int j){//verifica daca i si j sunt vecini
// nod*p;
// p=L[i];
// while(p){
// if(p->x==j)return true;
// p=p->urm;
// }
// return false;
// }
//
//void BF(int nod,int k){
// int prim,ultim;
// prim=ultim=1;
// coada[ultim]=nod;
// viz[nod]=k;
// while(prim<=ultim){
// nod=coada[prim];
// prim++;
// p=L[nod];
// while(p){
// if(viz[p->x]==0){
// coada[++ultim]=p->x;
// viz[p->x]=k;
// }
// p=p->urm;
// }
// }
// }
//int main()
//{
// fi>>n>>m;
// for(i=1;i<=n;i++)L[i]=0;//se fac liste vide
// for(i=1;i<=m;i++){
// fi>>x>>y;
// adauga(x,y);
// adauga(y,x);
// }
// for(i=1;i<=n;i++)
// if(viz[i]==0){k++;BF(i,k);}
// for(i=1;i<=n;i++)fr[viz[i]]++;
// fo<<k<<" ";
// //b)
//// for(i=1;i<=n;i++)fo<<viz[i]<<" ";fo<<endl;
//// for(i=1;i<=k;i++)fo<<fr[i]<<" ";fo<<endl;
// sort(fr+1,fr+k+1);
// long long sol,nr;
// int z;
// if(fr[k]==fr[k-1]){ //cazul 1 2 3 4 4 7 7 7 => sol=7*7+7*7+7*7 (fiecare 7 cu fiecare 7)=(7*7)*nr7(nr7-1)/2
// z=k;
// while(z>1 and fr[z]==fr[z-1])z--;
// nr=k-z+1; //nr==nr7
// sol=(((fr[k]%666013)*(fr[k]%666013))%666013*(nr*(nr-1)/2)%666013)%666013;
// }
// else //fr[k]!=fr[k-1] cazul 2 3 5 5 5 7 =>sol=5*7+5*7+5*7
// {
// z=k;
// sol=fr[k]*fr[k-1];
// z--;
// while(z>1 and fr[z]==fr[z-1]){sol=sol%666013+(fr[k]*fr[z-1])%666013;z--;}
// }
// fo<<sol%666013<<endl;;
//
// return 0;
//}
//>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.
////100p
//////// x*sx + y*sy =E-( t*st + z*sz +ss)
//////generam un sir cu elementele E-( t*st + z*sz +ss)
////si cautam binar x*sx + y*sy
//#include <fstream>
//#include<cstring>
//#include <algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("eq4.in");
//ofstream fo("eq4.out");
//char s[M],cifre[]="0123456789";
//long long k,j,sol,el,ss,ok,i,m,sx,sy,sz,st,a,b,c,w,E,semn;
//long long v[1002003];
//int cauta_bin(long long x){//cauta pozitia cel mai mic el. mai mare ca x
// int st,dr,mij; //pozitia primului mai mare ca x!!!!
// st=1;
// dr=k+1;//pt. cazul cand caut el maxim
// while(st<dr){
// mij=(st+dr)/2;
// if(x>=v[mij])st=mij+1;
// else dr=mij;
// }
// return st;
//}
//int main()
//{
// fi>>c;
// fi.get();
// fi.getline(s,M);
// fi>>a>>b>>E;
// strcat(s,"+");
// m=strlen(s);
// for(i=0;i<m;i++)
// {
// if(s[i]=='-' or s[i]=='+')
// {
// if(w!=0)ss+=semn*w;
// w=0; //calcul coeficient in w
// ok=0;//verif daca exista coef.
// if(s[i]=='-')semn=-1;
// if(s[i]=='+')semn=1;
// }
// else
// if(strchr(cifre,s[i])>0){w=w*10+s[i]-'0';ok=1;}
// else
// {
// if(ok==0)w=1;//cazul -x, +y
// if(s[i]=='x'){sx+=semn*w;w=0;}
// if(s[i]=='y'){sy+=semn*w;w=0;}
// if(s[i]=='z'){sz+=semn*w;w=0;}
// if(s[i]=='t'){st+=semn*w;w=0;}
// }
// }
// // fo<<sx<<" "<<sy<<" "<<sz<<" "<<st<<" "<<ss<<endl;;
//
// if(c==1)fo<<sx+sy+sz+st+ss;
// if(c==2)
// {
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// v[++k]=E-ss-i*sz-j*st;
// sort(v+1,v+k+1);
// v[k+1]=v[k]+1;//!!!
// //fo<<k<<" ";
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// {
// el=i*sx+j*sy;
// sol+=cauta_bin(el)-cauta_bin(el-1);
// }
// fo<<sol;
// }
// return 0;
//}
////65p O(n3) brut force cu for-uri (dat calcul corect la st===0!!!
//// t*st=E-(x*sx + y*sy + z*sz +ss)
////avem x*sx + y*sy + z*sz + t*st +ss=E
//
//#include <fstream>
//#include<iostream>
//#include<cstring>
//#include <algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("eq4.in");
//ofstream fo("eq4.out");
//char s[M],cifre[]="0123456789";
//long long k,j,sol,el,ss,ok,i,m,sx,sy,sz,st,a,b,c,w,E,semn;
//int main()
//{
// fi>>c;
// fi.get();
// fi.getline(s,M);
// fi>>a>>b>>E;
// strcat(s,"+");
// m=strlen(s);
// for(i=0;i<m;i++)
// {
// if(s[i]=='-' or s[i]=='+')
// {
// if(w!=0)ss+=semn*w;
// w=0; //calcul coeficient in w
// ok=0;//verif daca exista coef.
// if(s[i]=='-')semn=-1;
// if(s[i]=='+')semn=1;
// }
// else
// if(strchr(cifre,s[i])>0){w=w*10+s[i]-'0';ok=1;}
// else
// {
// if(ok==0)w=1;//cazul -x, +y
// if(s[i]=='x'){sx+=semn*w;w=0;}
// if(s[i]=='y'){sy+=semn*w;w=0;}
// if(s[i]=='z'){sz+=semn*w;w=0;}
// if(s[i]=='t'){st+=semn*w;w=0;}
// }
// }
// //fo<<sx<<" "<<sy<<" "<<sz<<" "<<st<<" "<<ss<<endl;;
//
// if(c==1)fo<<sx+sy+sz+st+ss;
// if(c==2)
// {
// // x*sx + y*sy + z*sz + t*st +ss=E
// // t*st=E-(x*sx + y*sy + z*sz +ss)
// long long termt;
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// for(k=a;k<=b;k++)
// { termt=E-(i*sx + j*sy + k*sz +ss);
// if(st!=0)
// {if(termt%st==0 and termt/st>=a and termt/st<=b)
// sol++;
// }
// else if(termt==0)sol+=(b-a+1);
// }
// fo<<sol;
// }
// return 0;
//}
/////40p O(n3) brut force cu for-uri (dat calcul incorect la st===0!!!
//// t*st=E-(x*sx + y*sy + z*sz +ss)
////avem x*sx + y*sy + z*sz + t*st +ss=E
//avem x*sx + y*sy + z*sz + t*st +ss=E
//
//#include <fstream>
//#include<iostream>
//#include<cstring>
//#include <algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("eq4.in");
//ofstream fo("eq4.out");
//char s[M],cifre[]="0123456789";
//long long k,j,sol,el,ss,ok,i,m,sx,sy,sz,st,a,b,c,w,E,semn;
//int main()
//{
// fi>>c;
// fi.get();
// fi.getline(s,M);
// fi>>a>>b>>E;
// strcat(s,"+");
// m=strlen(s);
// for(i=0;i<m;i++)
// {
// if(s[i]=='-' or s[i]=='+')
// {
// if(w!=0)ss+=semn*w;
// w=0; //calcul coeficient in w
// ok=0;//verif daca exista coef.
// if(s[i]=='-')semn=-1;
// if(s[i]=='+')semn=1;
// }
// else
// if(strchr(cifre,s[i])>0){w=w*10+s[i]-'0';ok=1;}
// else
// {
// if(ok==0)w=1;//cazul -x, +y
// if(s[i]=='x'){sx+=semn*w;w=0;}
// if(s[i]=='y'){sy+=semn*w;w=0;}
// if(s[i]=='z'){sz+=semn*w;w=0;}
// if(s[i]=='t'){st+=semn*w;w=0;}
// }
// }
// // fo<<sx<<" "<<sy<<" "<<sz<<" "<<st<<" "<<ss<<endl;;
//
// if(c==1)fo<<sx+sy+sz+st+ss;
// if(c==2)
// {
// long long termt;
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// for(k=a;k<=b;k++)
// { termt=E-(i*sx + j*sy + k*sz +ss);
// if(st!=0)
// {if(termt%st==0 and termt/st>=a and termt/st<=b)
// sol++;
// }
// else sol++;//pr st==0 aici e gresala!!!!! =>40p
// }
// fo<<sol;
// }
// return 0;
//}
//var II vezi pbinfo
////80p timp depasit!!!!
////Lee cu deque implementata dinamic cu pointeri
////cu matrice de ap[] sa nu pun de mai multe ori in coada
////merg si pun zonele libere in fata
////dar le pun repetat de mai multe ori si timpul!!!
////var III vezi pbinfo
////65p timp depasit
////Lee cu coada implementata cu pointeri dinamic
////var IV
////60p creapa coada
////Lee dar creapa coada
//#include <fstream>
//#include <iomanip>
//#define M 503
//using namespace std;
//ifstream fi("rover.in");
//ofstream fo("rover.out");
//int a[M][M],b[M][M],c[10*M*M];
//int i,j,n,v,G;
//void Lee(int ii,int jj,int g){
// int p,u,i,j,k;
// p=u=1;
// c[1]=ii*1000+jj;
// b[ii][jj]=0;
// while(p<=u){
// i=c[p]/1000;
// j=c[p]%1000;
// p++;
// if(i>1){ //N
// if(a[i-1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i-1][j])
// {
// b[i-1][j]=b[i][j]+k;
// c[++u]=(i-1)*1000+j;
// }
// }
// if(i<n){ //S
// if(a[i+1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i+1][j])
// {
// b[i+1][j]=b[i][j]+k;
// c[++u]=(i+1)*1000+j;
// }
// }
// if(j<n){ //E
// if(a[i][j+1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j+1])
// {
// b[i][j+1]=b[i][j]+k;
// c[++u]=(i)*1000+(j+1);
// }
// }
// if(j>1){ //V
// if(a[i][j-1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j-1])
// {
// b[i][j-1]=b[i][j]+k;
// c[++u]=(i)*1000+(j-1);
// }
// }
//}
//}
//int main()
//{
// fi>>v;
// if(v==1){
// fi>>n>>G;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //setare matrice b pe maxim
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// Lee(1,1,G);
// // for(i=1;i<=n;i++){for(j=1;j<=n;j++)fo<<setw(3)<<b[i][j];fo<<endl;}
// fo<<b[n][n];
// }
//if(v==2){
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //cauta binar rezulatul - cea mai mica valoare buna!!!
// int st,dr,mij;
// st=0;dr=5000;
// while(st<=dr){
// mij=(st+dr)/2;
// //setare matrice b pe maxim
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// Lee(1,1,mij);
// if(b[n][n]>0)dr=mij-1;
// else st=mij+1;
// }
// fo<<dr;
// }
// return 0;
//}
//
////75p timp depasit!!!!
////Lee cu deque implementata dinamic cu pointeri
////cu matrice de ap[] sa nu pun de mai multe ori in coada
////merg si pun zonele libere in fata
////
//#include <fstream>
//#include <iomanip>
//#define M 503
//using namespace std;
//ifstream fi("rover.in");
//ofstream fo("rover.out");
//struct nod{
// int i,j;
// nod*urm;
//}*p,*u;
//void push_bk(int i,int j,nod*&p,nod*&u){
// nod*q=new nod;
// q->i=i;
// q->j=j;
// q->urm=0;
// if(p==0){p=q;u=q;}
// else{
// u->urm=q;
// u=q;
// }
//}
//void push_fr(int i,int j,nod*&p,nod*&u){
// nod*q=new nod;
// q->i=i;
// q->j=j;
// q->urm=0;
// if(p==0){p=q;u=q;}
// else{
// q->urm=p;
// p=q;
// }
//}
//void pop(int &i,int &j,nod*&p,nod*&u){
// nod*q;
// i=p->i;
// j=p->j;
// q=p;
// p=p->urm;
// delete q;
//}
//int a[M][M],b[M][M],ap[M][M];
//int i,j,n,v,G;
//void Lee(int ii,int jj,int g){
// int i,j,k;
// p=0;//coada vida
// push_bk(ii,jj,p,u);
// b[ii][jj]=0;
// ap[ii][jj]=1; //pun pe 1
// while(p){
// pop(i,j,p,u);
// ap[i][j]=0; //pun pe 0
// if(i>1){ //N
// if(a[i-1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i-1][j])
// {
// b[i-1][j]=b[i][j]+k;
// if(b[i-1][j]==0) push_fr(i-1,j,p,u);
// else
// if(ap[i-1][j]==0) {push_bk(i-1,j,p,u);ap[i-1][j]=1;}
// }
// }
// if(i<n){ //S
// if(a[i+1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i+1][j])
// {
// b[i+1][j]=b[i][j]+k;
// if(b[i+1][j]==0) push_fr(i+1,j,p,u);
// else
// if(ap[i+1][j]==0) {push_bk(i+1,j,p,u);ap[i+1][j]=1;}
// }
// }
// if(j<n){ //E
// if(a[i][j+1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j+1])
// {
// b[i][j+1]=b[i][j]+k;
// if(b[i][j+1]==0) push_fr(i,j+1,p,u);
// else
// if(ap[i][j+1]==0) {push_bk(i,j+1,p,u);ap[i][j+1]=1;}
// }
// }
// if(j>1){ //V
// if(a[i][j-1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j-1])
// {
// b[i][j-1]=b[i][j]+k;
// if(b[i][j-1]==0) push_fr(i,j-1,p,u);
// else
// if(ap[i][j-1]==0) {push_bk(i,j-1,p,u);ap[i][j-1]=1;}
// }
// }
//}
//}
//int main()
//{
// fi>>v;
// if(v==1){
// fi>>n>>G;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //setare matrice b pe maxim
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// Lee(1,1,G);
// // for(i=1;i<=n;i++){for(j=1;j<=n;j++)fo<<setw(3)<<b[i][j];fo<<endl;}
// fo<<b[n][n];
// }
//if(v==2){
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //cauta binar rezulatul - cea mai mica valoare buna!!!
// int st,dr,mij;
// st=0;dr=5000;
// while(st<=dr){
// mij=(st+dr)/2;
// //setare matrice b[][] pe maxim si ap[][] pe 0
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)ap[i][j]=0;
// Lee(1,1,mij);
// if(b[n][n]>0)dr=mij-1;
// else st=mij+1;
// }
// fo<<dr;
// }
// return 0;
//}
////p timp depasit!!!!
////Lee cu deque implementata dinamic cu pointeri
////cu matrice de ap[] sa nu pun de mai multe ori in coada
////merg numai in zone sigure !!!
////la sf vad daca ating (n,n)
//#include <fstream>
//#include <iomanip>
//#define M 503
//using namespace std;
//ifstream fi("rover.in");
//ofstream fo("rover.out");
//struct nod{
// int i,j;
// nod*urm;
//}*p,*u;
//void push(int i,int j,nod*&p,nod*&u){
// nod*q=new nod;
// q->i=i;
// q->j=j;
// q->urm=0;
// if(p==0){p=q;u=q;}
// else{
// u->urm=q;
// u=q;
// }
//}
//void pop(int &i,int &j,nod*&p,nod*&u){
// nod*q;
// i=p->i;
// j=p->j;
// q=p;
// p=p->urm;
// delete q;
//}
//int a[M][M],b[M][M],ap[M][M];
//int i,j,n,v,G;
//void Lee(int ii,int jj,int g){
// int i,j,k;
// p=0;//coada vida
// push(ii,jj,p,u);
// b[ii][jj]=0;
// ap[ii][jj]=1; //pun pe 1
// while(p){
// pop(i,j,p,u);
// ap[i][j]=0; //pun pe 0
// if(i>1){ //N
// if(a[i-1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i-1][j])
// {
// b[i-1][j]=b[i][j]+k;
// if(ap[i-1][j]==0){ //se pune in coada daca nu-i pus deja
// ap[i-1][j]=1;
// push(i-1,j,p,u);
// }
// }
// }
// if(i<n){ //S
// if(a[i+1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i+1][j])
// {
// b[i+1][j]=b[i][j]+k;
// if(ap[i+1][j]==0){ //se pune in coada daca nu-i pus deja
// ap[i+1][j]=1;
// push(i+1,j,p,u);
// }
// }
// }
// if(j<n){ //E
// if(a[i][j+1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j+1])
// {
// b[i][j+1]=b[i][j]+k;
// if(ap[i][j+1]==0){ //se pune in coada daca nu-i pus deja
// ap[i][j+1]=1;
// push(i,j+1,p,u);
// }
// }
// }
// if(j>1){ //V
// if(a[i][j-1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j-1])
// {
// b[i][j-1]=b[i][j]+k;
// if(ap[i][j-1]==0){ //se pune in coada daca nu-i pus deja
// ap[i][j-1]=1;
// push(i,j-1,p,u);
// }
// }
// }
//}
//}
//int main()
//{
// fi>>v;
// if(v==1){
// fi>>n>>G;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //setare matrice b pe maxim
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// Lee(1,1,G);
// // for(i=1;i<=n;i++){for(j=1;j<=n;j++)fo<<setw(3)<<b[i][j];fo<<endl;}
// fo<<b[n][n];
// }
//if(v==2){
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //cauta binar rezulatul - cea mai mica valoare buna!!!
// int st,dr,mij;
// st=0;dr=5000;
// while(st<=dr){
// mij=(st+dr)/2;
// //setare matrice b[][] pe maxim si ap[][] pe 0
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)ap[i][j]=0;
// Lee(1,1,mij);
// if(b[n][n]>0)dr=mij-1;
// else st=mij+1;
// }
// fo<<dr;
// }
// return 0;
//}
////65p timp depasit!!!!
////Lee cu coada implementata dinamic cu pointeri
////cu matrice de ap[] sa numpun de mai multe ori in coada
////dar se scoate si re repune de mai multe ori in coada!!!!
//#include <fstream>
//#include <iomanip>
//#define M 503
//using namespace std;
//ifstream fi("rover.in");
//ofstream fo("rover.out");
//struct nod{
// int i,j;
// nod*urm;
//}*p,*u;
//void push(int i,int j,nod*&p,nod*&u){
// nod*q=new nod;
// q->i=i;
// q->j=j;
// q->urm=0;
// if(p==0){p=q;u=q;}
// else{
// u->urm=q;
// u=q;
// }
//}
//void pop(int &i,int &j,nod*&p,nod*&u){
// nod*q;
// i=p->i;
// j=p->j;
// q=p;
// p=p->urm;
// delete q;
//}
//int a[M][M],b[M][M],ap[M][M];
//int i,j,n,v,G;
//void Lee(int ii,int jj,int g){
// int i,j,k;
// p=0;//coada vida
// push(ii,jj,p,u);
// b[ii][jj]=0;
// ap[ii][jj]=1; //pun pe 1
// while(p){
// pop(i,j,p,u);
// ap[i][j]=0; //pun pe 0
// if(i>1){ //N
// if(a[i-1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i-1][j])
// {
// b[i-1][j]=b[i][j]+k;
// if(ap[i-1][j]==0){ //se pune in coada daca nu-i pus deja
// ap[i-1][j]=1;
// push(i-1,j,p,u);
// }
// }
// }
// if(i<n){ //S
// if(a[i+1][j]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i+1][j])
// {
// b[i+1][j]=b[i][j]+k;
// if(ap[i+1][j]==0){ //se pune in coada daca nu-i pus deja
// ap[i+1][j]=1;
// push(i+1,j,p,u);
// }
// }
// }
// if(j<n){ //E
// if(a[i][j+1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j+1])
// {
// b[i][j+1]=b[i][j]+k;
// if(ap[i][j+1]==0){ //se pune in coada daca nu-i pus deja
// ap[i][j+1]=1;
// push(i,j+1,p,u);
// }
// }
// }
// if(j>1){ //V
// if(a[i][j-1]>=g)k=0;
// else k=1;
// if(b[i][j]+k<b[i][j-1])
// {
// b[i][j-1]=b[i][j]+k;
// if(ap[i][j-1]==0){ //se pune in coada daca nu-i pus deja
// ap[i][j-1]=1;
// push(i,j-1,p,u);
// }
// }
// }
//}
//}
//int main()
//{
// fi>>v;
// if(v==1){
// fi>>n>>G;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //setare matrice b pe maxim
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// Lee(1,1,G);
// // for(i=1;i<=n;i++){for(j=1;j<=n;j++)fo<<setw(3)<<b[i][j];fo<<endl;}
// fo<<b[n][n];
// }
//if(v==2){
// fi>>n;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)fi>>a[i][j];
// //cauta binar rezulatul - cea mai mica valoare buna!!!
// int st,dr,mij;
// st=0;dr=5000;
// while(st<=dr){
// mij=(st+dr)/2;
// //setare matrice b[][] pe maxim si ap[][] pe 0
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)b[i][j]=500000;
// for(i=1;i<=n;i++)
// for(j=1;j<=n;j++)ap[i][j]=0;
// Lee(1,1,mij);
// if(b[n][n]>0)dr=mij-1;
// else st=mij+1;
// }
// fo<<dr;
// }
// return 0;
//}
////70p O(n^3) brute force
////din fiecare punct calculez cu while in stanga si dreapta
//#include <fstream>
//#define M 100003
//using namespace std;
//ifstream fi("turnuri.in");
//ofstream fo("turnuri.out");
//int a[M+1],b[M+1];
//int i,j,n,aux,s,p,q,frumusete;
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// for(i=1;i<=n;i++){
// aux=a[i];//salvam a[i]
// a[i]=0;
// //calculam coef. de frumusete pt. a[i]=0
// frumusete=0;
// for(j=1;j<=n;j++)
// {
// //calcul spre stanga
// p=j-1;
// while(p>=1 and a[p]<a[j]) p--;
// //calcul spre stanga
// q=j+1;
// while(q<=n and a[q]<a[j]) q++;
// frumusete+=q-p-1;
// }
// b[i]=frumusete;
// a[i]=aux;//refacem vectorul
// }
// for(i=1;i<=n;i++)fo<<b[i]<<'\n';
// return 0;
//}
//
////3 varianta 100p, 65p, 40p
////100p
////avem x*sx + y*sy + z*sz + t*st +ss=E
////c1x + c2y =E-z*sz - t*st -ss
////idee fac un vector cu elementele membrului drept, apoi sortez
//// iau elementele membrului stang si le caut binar in vector
//// de cate ori apar adun la solutii
////caut cu caut_bin ce da poz urmatorului mai mare !!!!
//// si fac sol+=cauta_bin(el)-cauta_bin(el-1); !!!!!!
//#include <fstream>
//#include<cstring>
//#include <algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("eq4.in");
//ofstream fo("eq4.out");
//char s[M],cifre[]="0123456789";
//long long k,j,sol,el,ss,ok,i,m,sx,sy,sz,st,a,b,c,w,E,semn;
//long long v[1002003];
//int cauta_bin(long long x){//cauta pozitia cel mai mic el. mai mare ca x
// int st,dr,mij; //pozitia primului mai mare ca x!!!!
// v[k+1]=v[k]+1;//pt. cazul cand caut el maxim sau unul mai mare ca maxim
// st=1;
// dr=k+1; //pt. cazul cand caut el maxim sau unul mai mare ca maxim
// while(st<dr){
// mij=(st+dr)/2;
// if(x>=v[mij])st=mij+1;
// else dr=mij;
// }
// return st;
//}
//int main()
//{
// fi>>c;
// fi.get();
// fi.getline(s,M);
// fi>>a>>b>>E;
// strcat(s,"+");
// m=strlen(s);
// for(i=0;i<m;i++)
// {
// if(s[i]=='-' or s[i]=='+')
// {
// if(w!=0)ss+=semn*w;
// w=0; //calcul coeficient in w
// ok=0;//verif daca exista coef.
// if(s[i]=='-')semn=-1;
// if(s[i]=='+')semn=1;
// }
// else
// if(strchr(cifre,s[i])>0){w=w*10+s[i]-'0';ok=1;}
// else
// {
// if(ok==0)w=1;//cazul -x, +y
// if(s[i]=='x'){sx+=semn*w;w=0;}
// if(s[i]=='y'){sy+=semn*w;w=0;}
// if(s[i]=='z'){sz+=semn*w;w=0;}
// if(s[i]=='t'){st+=semn*w;w=0;}
// }
// }
// // fo<<sx<<" "<<sy<<" "<<sz<<" "<<st<<" "<<ss<<endl;;
//
// if(c==1)fo<<sx+sy+sz+st+ss;
// if(c==2)
// {
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// v[++k]=E-ss-i*sz-j*st;
// sort(v+1,v+k+1);
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// {
// el=i*sx+j*sy;
// sol+=cauta_bin(el)-cauta_bin(el-1);
// }
// fo<<sol;
// }
// return 0;
//}
////40p cu brute force (4 for) dar cu greseala de impartire la 0
////avem x*sx + y*sy + z*sz + t*st +ss=E
//
//#include <fstream>
//#include<iostream>
//#include<cstring>
//#include <algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("eq4.in");
//ofstream fo("eq4.out");
//char s[M],cifre[]="0123456789";
//long long k,j,sol,el,ss,ok,i,m,sx,sy,sz,st,a,b,c,w,E,semn;
//int main()
//{
// fi>>c;
// fi.get();
// fi.getline(s,M);
// fi>>a>>b>>E;
// strcat(s,"+");
// m=strlen(s);
// for(i=0;i<m;i++)
// {
// if(s[i]=='-' or s[i]=='+')
// {
// if(w!=0)ss+=semn*w;
// w=0; //calcul coeficient in w
// ok=0;//verif daca exista coef.
// if(s[i]=='-')semn=-1;
// if(s[i]=='+')semn=1;
// }
// else
// if(strchr(cifre,s[i])>0){w=w*10+s[i]-'0';ok=1;}
// else
// {
// if(ok==0)w=1;//cazul -x, +y
// if(s[i]=='x'){sx+=semn*w;w=0;}
// if(s[i]=='y'){sy+=semn*w;w=0;}
// if(s[i]=='z'){sz+=semn*w;w=0;}
// if(s[i]=='t'){st+=semn*w;w=0;}
// }
// }
// // fo<<sx<<" "<<sy<<" "<<sz<<" "<<st<<" "<<ss<<endl;;
//
// if(c==1)fo<<sx+sy+sz+st+ss;
// if(c==2)
// {
// long long termt;
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// for(k=a;k<=b;k++)
// { termt=E-(i*sx + j*sy + k*sz +ss);
// if(st!=0) //impartire la 0!!!! primesti doar 40p
// {if(termt%st==0 and termt/st>=a and termt/st<=b)
// sol++;
// }
// else sol++;
// }
// fo<<sol;
// }
// return 0;
//}
////65p cu brute force (4 for)
////avem x*sx + y*sy + z*sz + t*st +ss=E
//
//#include <fstream>
//#include<iostream>
//#include<cstring>
//#include <algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("eq4.in");
//ofstream fo("eq4.out");
//char s[M],cifre[]="0123456789";
//long long k,j,sol,el,ss,ok,i,m,sx,sy,sz,st,a,b,c,w,E,semn;
//int main()
//{
// fi>>c;
// fi.get();
// fi.getline(s,M);
// fi>>a>>b>>E;
// strcat(s,"+");
// m=strlen(s);
// for(i=0;i<m;i++)
// {
// if(s[i]=='-' or s[i]=='+')
// {
// if(w!=0)ss+=semn*w;
// w=0; //calcul coeficient in w
// ok=0;//verif daca exista coef.
// if(s[i]=='-')semn=-1;
// if(s[i]=='+')semn=1;
// }
// else
// if(strchr(cifre,s[i])>0){w=w*10+s[i]-'0';ok=1;}
// else
// {
// if(ok==0)w=1;//cazul -x, +y
// if(s[i]=='x'){sx+=semn*w;w=0;}
// if(s[i]=='y'){sy+=semn*w;w=0;}
// if(s[i]=='z'){sz+=semn*w;w=0;}
// if(s[i]=='t'){st+=semn*w;w=0;}
// }
// }
// //fo<<sx<<" "<<sy<<" "<<sz<<" "<<st<<" "<<ss<<endl;;
//
// if(c==1)fo<<sx+sy+sz+st+ss;
// if(c==2)
// {
// // x*sx + y*sy + z*sz + t*st +ss=E
// // t*st=E-(x*sx + y*sy + z*sz +ss)
// long long termt;
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// for(k=a;k<=b;k++)
// { termt=E-(i*sx + j*sy + k*sz +ss);
// if(st!=0) //imp. la 0 !!!! 40p fara faza asta
// {if(termt%st==0 and termt/st>=a and termt/st<=b)
// sol++;
// }
// else if(termt==0)sol+=(b-a+1);//!!! t*0==0 => orice t este bun
// }
// fo<<sol;
// }
// return 0;
//}
////100p
////avem x*sx + y*sy + z*sz + t*st +ss=E
////c1x + c2y =E-z*sz - t*st -ss
////idee fac un vector cu elementele membrului drept, apoi sortez
//// iau elementele membrului stang si le caut binar in vector
//// de cate ori apar adun la solutii
////caut cu caut_bin ce da poz urmatorului mai mare !!!!
//// si fac sol+=cauta_bin(el)-cauta_bin(el-1); !!!!!!
//#include <fstream>
//#include<cstring>
//#include <algorithm>
//#define M 100003
//using namespace std;
//ifstream fi("eq4.in");
//ofstream fo("eq4.out");
//char s[M],cifre[]="0123456789";
//long long k,j,sol,el,ss,ok,i,m,sx,sy,sz,st,a,b,c,w,E,semn;
//long long v[1002003];
//int cauta_bin(long long x){//cauta pozitia cel mai mic el. mai mare ca x
// int st,dr,mij; //pozitia primului mai mare ca x!!!!
// v[k+1]=v[k]+1;//pt. cazul cand caut el maxim sau unul mai mare ca maxim
// st=1;
// dr=k+1; //pt. cazul cand caut el maxim sau unul mai mare ca maxim
// while(st<dr){
// mij=(st+dr)/2;
// if(x>=v[mij])st=mij+1;
// else dr=mij;
// }
// return st;
//}
//int main()
//{
// fi>>c;
// fi.get();
// fi.getline(s,M);
// fi>>a>>b>>E;
// strcat(s,"+");
// m=strlen(s);
// for(i=0;i<m;i++)
// {
// if(s[i]=='-' or s[i]=='+')
// {
// if(w!=0)ss+=semn*w;
// w=0; //calcul coeficient in w
// ok=0;//verif daca exista coef.
// if(s[i]=='-')semn=-1;
// if(s[i]=='+')semn=1;
// }
// else
// if(strchr(cifre,s[i])>0){w=w*10+s[i]-'0';ok=1;}
// else
// {
// if(ok==0)w=1;//cazul -x, +y
// if(s[i]=='x'){sx+=semn*w;w=0;}
// if(s[i]=='y'){sy+=semn*w;w=0;}
// if(s[i]=='z'){sz+=semn*w;w=0;}
// if(s[i]=='t'){st+=semn*w;w=0;}
// }
// }
// // fo<<sx<<" "<<sy<<" "<<sz<<" "<<st<<" "<<ss<<endl;;
//
// if(c==1)fo<<sx+sy+sz+st+ss;
// if(c==2)
// {
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// v[++k]=E-ss-i*sz-j*st;
// sort(v+1,v+k+1);
// for(i=a;i<=b;i++)
// for(j=a;j<=b;j++)
// {
// el=i*sx+j*sy;
// sol+=cauta_bin(el)-cauta_bin(el-1);
// }
// fo<<sol;
// }
// return 0;
//}
//#include <fstream>
//#include <iomanip>
//#define M 1000002
//using namespace std;
//ifstream fi("a.in");
//ofstream fo("a.out");
//int a[M],pr[M],b[M],c[M],i,n,k1,k0,m,maxi,k,j;
//int main()
//{
// //Ciur numerele prime au pr[]==0
// k=M-2;
// pr[0]=pr[1]=1;//neprime
// for(i=2; i<=k; i++)
// if(pr[i]==0)
// for(j=2*i; j<=k; j=j+i)pr[j]=1;
// //
// fi>>n;
// for(i=1; i<=n; i++)fi>>a[i];
// for(i=1; i<=n; i++)
// if(a[i]%9==0)a[i]=9; //9 pt. numar div cu 9
// else if(pr[a[i]]==0)a[i]=1; //1 pt. numar prim
// else a[i]=0; //0 pt. numar oarecare
// //a)
// for(i=1; i<=n; i++)
// if(a[i]==9 )k0++;
// fo<<k0<<endl;
// //b)
// for(i=2; i<n; i++)
// if(a[i]==9 and a[i-1]==1 and a[i+1]==1)k1++;
// fo<<k1<<endl;
// //c)
// //precalc. in b[i-1] cate elem consecutive din stanga sunt prime
// for(i=1; i<=n; i++) // ----->>>>>
// if(a[i]==1)b[i]=1+b[i-1];
// else b[i]=0;
// //precalc. in c[i+1] cate elem consecutive din dreapta sunt prime
// for(i=n; i>=1; i--) // <<<<<<-----
// if(a[i]==1)c[i]=1+c[i+1];
// else c[i]=0;
// for(i=1; i<=n; i++)
// if(a[i]==9)
// {
// m=min(b[i-1],c[i+1]);
// maxi=max(m,maxi);
// }
// fo<<maxi<<endl;;
// //
//// for(i=1; i<=n; i++)fo<<setw(3)<<a[i]; fo<<endl;
//// for(i=1; i<=n; i++)fo<<setw(3)<<b[i]; fo<<endl;
//// for(i=1; i<=n; i++)fo<<setw(3)<<c[i]; fo<<endl;
// return 0;
//}
//// (Lee cu o coada statica(vector) smechera!!!! i*1000+j !!!)+vector de directii
////punem initial in coada linia 1
//#include <fstream>
//#include<iomanip>
//#define M 1003
//using namespace std;
//ifstream fi("prosir.in");
//ofstream fo("prosir.out");
//int a[M][M],xx,yy,n,m,i,j,z,w,k,p,u;
//int c[M*M],x,d,ii,jj,mini;
//int diri[]= {0,-1,0,1, 0}; //N E S V
//int dirj[]= {0, 0,1,0,-1};
//int main()
//{
// fi>>m>>n;
// for(i=1;i<=m;i++)
// for(j=1;j<=n;j++) fi>>a[i][j];
// for(j=0; j<=n+1; j++) //operatia de bordare
// {a[0][j]=1; a[m+1][j]=1;}
// for(i=0; i<=m+1; i++)
// {a[i][0]=1; a[i][n+1]=1;}
// p=1;
// for(j=1;j<=n;j++) //se pun in coada el. de pe linia 1
// if(a[1][j]==0) {a[1][j]=2;c[++u]=1*10000+j;}
// while(p<=u) //cat timp sunt elemente in coada
// {
// x=c[p];//se ia element din coada x-punct curent
// p++; //se avanseaza in coada
// i=x/10000; j=x%10000; //se afla i,j pentru punctul curent
// for(d=1; d<=4; d++) //merg pe cele 4 directii
// {
// ii=i+diri[d]; //afla noul punct dupa deplasarea N E S V
// jj=j+dirj[d];
// if(a[ii][jj]==0) //daca noul punct nu este vizitat
// {
// a[ii][jj]=a[i][j]+1; //se marcheaza noul punct
// u++; c[u]=ii*10000+jj; //se pune in coada noul punct
// }
// }
// }
// mini=1000000;
// for(j=1;j<=n;j++)
// if(a[m][j]!=0 and a[m][j]!=1 and a[m][j]<mini)mini=a[m][j];
// fo<<mini-1<<endl;
//// for(i=0;i<=m+1;i++){
//// for(j=0;j<=n+1;j++)
//// fo<<setw(3)<<a[i][j];
//// fo<<'\n';
//// }
// return 0;
//}
//// (Lee Palat
//#include <fstream>
//#include<iomanip>
//#define M 1003
//using namespace std;
//ifstream fi("prosir.in");
//ofstream fo("prosir.out");
//char ch;
//int a[M][M],c[M*M],b[M][M];
//int d,p,u,ii,jj,x,i,j,n,m,iL,jL,isol,jsol,mini;
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//int main()
//{
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++){fi>>ch;
// //if(c=='_')a[i][j]=0;
// if(ch=='Z')a[i][j]=-1;
// if(ch=='I'){iL=i;jL=j;}
// if(ch=='F')b[i][j]=1; //matricae cu Fetii Frumosi
// }
// //bordarea
// for(i=0;i<=n+1;i++)a[i][0]=a[i][m+1]=-1;
// for(j=0;j<=m+1;j++)a[0][j]=a[n+1][j]=-1;
//
// //Lee facut de la Ileana
// p=1;
// a[iL][jL]=1;
// c[++u]=iL*10000+jL;
// while(p<=u){
// x=c[p];
// p++;
// i=x/10000;
// j=x%10000;
// for(d=1;d<=4;d++){
// ii=i+diri[d];
// jj=j+dirj[d];
// if(a[ii][jj]==0){
// a[ii][jj]=a[i][j]+1;
// c[++u]=ii*10000+jj;
// }
// }
// }
// mini=10000000;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==1 and a[i][j]!=0 and a[i][j]<mini)
// mini=a[i][j];
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(b[i][j]==1 and a[i][j]!=0 and a[i][j]==mini)
// {
// isol=i;jsol=j;
// }
// fo<<isol<<" "<<jsol<<endl;
//// for(i=1;i<=n;i++){
//// for(j=1;j<=m;j++)
//// fo<<setw(3)<<a[i][j];
//// fo<<endl;
//// }
// return 0;
//}
//// (Lee
//#include <fstream>
//#include<iomanip>
//#define M 1003
//using namespace std;
//ifstream fi("acces1.in");
//ofstream fo("acces1.out");
//char ch;
//int a[M][M],c[M*M];
//int d,p,u,ii,jj,x,i,j,n,m,ib,is,jb,js;
//int diri[]={0,-1,0,1, 0};//N E S V
//int dirj[]={0, 0,1,0,-1};
//int main()
//{
// fi>>n>>m;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++){fi>>ch;
// //if(c=='_')a[i][j]=0;
// if(ch=='#')a[i][j]=-1;
// if(ch=='P') //punem pompierii initial in coada
// {a[i][j]=1;
// c[++u]=i*10000+j;
// }
// }
// //bordarea
// for(i=0;i<=n+1;i++)a[i][0]=a[i][m+1]=-1;
// for(j=0;j<=m+1;j++)a[0][j]=a[n+1][j]=-1;
//
// //Lee facut de la branza la soarece
// p=1;
// while(p<=u){
// x=c[p];
// p++;
// i=x/10000;
// j=x%10000;
// for(d=1;d<=4;d++){
// ii=i+diri[d];
// jj=j+dirj[d];
// if(a[ii][jj]==0){
// a[ii][jj]=a[i][j]+1;
// c[++u]=ii*10000+jj;
// }
// }
// }
//
// for(i=1;i<=n;i++){
// for(j=1;j<=m;j++)
// if(a[i][j]==-1)fo<<"# ";
// else if(a[i][j]==0)fo<<"- ";
// else fo<<a[i][j]-1<<" ";
// fo<<endl;
// }
// return 0;
//}
////coada1 ??!!
// #include <fstream>
// #include<cstring>
// using namespace std;
// ifstream fi("prosir.in");
// ofstream fo("prosir.out");
// int n,i,k,j,m;
// int z,x,st[50003],a[50003],poz[1003];
// char s[10];
// int main()
// {
// fi>>m;
// for(i=1;i<=m;i++){
// fi>>s>>x;
// if(strcmp(s,"push")==0)
// {
// if(poz[x]>0)z=poz[x];
// st[++k]=x;poz[x]=k;
// }
// else
// if(poz[x]<=z)fo<<-1<<'\n';//!!
// else fo<<poz[x]-z<<'\n';
// }
// return 0;
// }
//#include <iostream>
//#include<cstring>
//using namespace std;
//int n,i,k,j,m;
//char st[1000003],a[1000003];
//int main()
//{
// cin>>k>>a;
// n=strlen(a);
// m=1;
// st[m]=a[0]; //pun primul element in stiva
// for(i=1;i<n;i++)
// if(k>0) //daca nu am eliminat inca k elemente
// {
// st[++m]=a[i]; //pun a[i] in stiva
// while(m>1 and st[m]<st[m-1] and k>0) //scot din stiva toate elementele
// {st[m-1]=st[m];m--;k--;} //mai mici ca a[i]
// }
// else st[++m]=a[i];//am eliminat deja k elemente
//
// for(i=1;i<=m-k;i++)cout<<st[i]; //m-k !!! 3 abcde =>ab (ultimele !!)
// return 0;
//}
//#include<iostream>
//#include<fstream>
//#include<cmath>
//#include<iomanip>
//# define M 303
//using namespace std;
//ifstream fi("prosir.in");
//ofstream fo("prosir.out");
//int i,j,n,m,P[M],k,p,x;
//int main()
//{
// fi>>m>>n>>p;
// for(j=1;j<=n;j++)P[j]=1;
// for(i=1;i<=m;i++)
// for(j=1;j<=n;j++){
// fi>>x;
// P[j]=(P[j]*x)%p;
// }
// for(j=1;j<=n;j++)
// if(P[j]%p==0)k++;
// fo<<k;
// return 0;
//}
//forma de a X b
//sol=(cmmmc/a-1) + (cmmmc/b-1)
//(numar de reflexii pe peretii exteriori)+(numar de reflexii pe peretii interiori)
//#include<fstream>
//#include<iostream>
//#include<cstring>
//using namespace std;
//int i,n,k;
//char li[200],Li[200],ch;
//char rot13(int c)
//{
// if(c>='a' and c<='z')return li[27+(c-'a')-13];
// if(c>='A' and c<='Z')return Li[27+(c-'A')-13];
// c=' ';
// return c;
//}
//int main()
//{
// k=0;
// for(char i='a'; i<='z'; i++)li[++k]=i;
// for(char i='a'; i<='z'; i++)li[++k]=i;
// k=0;
// for(char i='A'; i<='Z'; i++)Li[++k]=i;
// for(char i='A'; i<='Z'; i++)Li[++k]=i;
// while(ch=cin.get()){
// if(ch==13)break;
// cout<<rot13(ch);
// }
// return 0;
//}
//
//#include<iostream>
//#include<fstream>
//#include<cstring>
//# define M 1003
//using namespace std;
//ifstream fi("subsircomunmaximal.in");
//ofstream fo("subsircomunmaximal.out");
//int a[M][M];
//int i,j,n,m,k;
//char s[M],t[M],sol[M];
//int main()
//{
// fi.getline(s,M);
// fi.getline(t,M);
// n=strlen(s);
// m=strlen(t);
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(s[i-1]==t[j-1])a[i][j]=1+a[i-1][j-1];
// else a[i][j]=max(a[i-1][j],a[i][j-1]);
// i=n;j=m;
// while(i>=1 and j>=1)
// {
// if(s[i-1]==t[j-1]){sol[++k]=s[i-1];i--;j--;}
// else
// if(a[i][j-1]==a[i][j])j--;
// else i--;
// }
// for(i=k;i>=1;i--)fo<<sol[i];
//// fo<<endl;
//// for(i=1;i<=n;i++){
//// for(j=1;j<=m;j++)fo<<a[i][j]<<" ";
//// fo<<endl;
//// }
// return 0;
//}
//#include<iostream>
//#include<fstream>
//#include<cstring>
//# define M 1003
//using namespace std;
//ifstream fi("lungimesubsircomunmaximal.in");
//ofstream fo("lungimesubsircomunmaximal.out");
//int a[M][M];
//int i,j,n,m;
//char s[M],t[M];
//int main()
//{
// fi.getline(s,M);
// fi.getline(t,M);
// n=strlen(s);
// m=strlen(t);
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(s[i-1]==t[j-1])a[i][j]=1+a[i-1][j-1];
// else a[i][j]=max(a[i-1][j],a[i][j-1]);
// fo<<a[n][m];
// return 0;
//}
//#include<iostream>
//#include<fstream>
//#include<cstring>
//# define M 1003
//using namespace std;
//ifstream fi("prosir.in");
//ofstream fo("prosir.out");
//int a[M][M];
//int i,j,n,m,k;
//char s[M],t[M],sol[M];
//int main()
//{
// fi.getline(s,M);
// fi.getline(t,M);
// n=strlen(s);
// m=strlen(t);
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// if(s[i-1]==t[j-1])a[i][j]=1+a[i-1][j-1];
// else a[i][j]=max(a[i-1][j],a[i][j-1]);
// i=n;j=m;
// while(i>=1 and j>=1)
// {
// if(s[i-1]==t[j-1]){sol[++k]=s[i-1];i--;j--;}
// else
// if(a[i][j-1]==a[i][j])j--;
// else i--;
// }
// for(i=k;i>=1;i--)fo<<sol[i];
//// fo<<endl;
//// for(i=1;i<=n;i++){
//// for(j=1;j<=m;j++)fo<<a[i][j]<<" ";
//// fo<<endl;
//// }
// return 0;
//}
////var II 55p
////timpul: am copiat la fiecare sol posibila in t si
////apoi am comparat cu sol!!!
////idee
////solutia incepe cu litera cea mai mica
////dddddddr se incearca doar primul d (restul nu are rost)
////ddddddda nu se poate deoarece sol ar fi adddddddd!!!
////la fiecare d gasit(d de la inceput)cmpar cu sol si schimb sol daca trebuie
//#include<iostream>
//#include<cstring>
//#include<fstream>
//# define M 200005
//using namespace std;
//ifstream fi("minlex.in");
//ofstream fo("minlex.out");
//char cmin,s[M],*p,t[M],z[M],sol[M];
//int i,n,rot,j,k;
//int main()
//{
// fi.get(s,M);
// n=strlen(s);
// strcpy(t,s);
// strcat(s,t);
// cmin=126;
// for(i=0; i<n; i++)
// if(s[i]<cmin)cmin=s[i];
// //primul cuv e pus in sol !!!
// p=strchr(s,cmin);
// strncat(sol,p,n);
// rot=p-s;
// for(i=1; i<n; i++)
// if(s[i]==cmin and s[i]!=s[i-1])
// {
// t[0]=0;
// strncat(t,s+i,n);
// if(strcmp(t,sol)<0)
// {strcpy(sol,t);rot=i;}
//
// }
// fo<<rot;
// return 0;
//}
////var I 55p timpul!!
////idee rudimentara
////extrag fiecare subsir si compar cu sol
//#include<iostream>
//#include<cstring>
//#include<fstream>
//# define M 200005
//using namespace std;
//ifstream fi("minlex.in");
//ofstream fo("minlex.out");
//char s[M],*p,t[M],z[M],sol[M];
//int i,n,poz;
//int main()
//{
// fi.get(s,M);
// strcpy(sol,s);
// n=strlen(s);
// strcpy(t,s);
// strcat(s,t);
// for(i=0;i<n;i++)
// {
// z[0]='\0';
// strncat(z,s+i,n);
// // fo<<z<<endl;
// if(strcmp(sol,z)>0){strcpy(sol,z);poz=i;}
// }
// fo<<poz;
// return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("a.in");
//ofstream fo("a.out");
//int n,m,i,p,maxi,anterior,j,x,y,t;
//int a[1003],L[1003],s[1003],sfin[1003];
//bool prim(int x){
//int d;
//if(x==0 or x==1 )return false;
//for(d=2;d*d<=x;d++)
// if(x%d==0)return false;
//return true;
//}
////void afis_sol1(int i,int k){//afis toate sol pornind din p
////int j;
////s[k]=a[i];
////if(k==maxi){
//// for(t=1;t<=k;t++)fo<<s[t]<<" ";fo<<endl;
//// }
////else {
//// for(j=i+1;j<=m;j++)
//// if(a[i]<=a[j] and L[i]==L[j]+1)
//// afis_sol(j,k+1);
//// }
////}
//void afis_sol(int i,int k){
//int j;
//s[k]=a[i];
//if(k==maxi){
// t=1;
// while(t<=k and s[t]==sfin[t])t++;
// if(t!=k+1 and s[t]<sfin[t])
// for(t=1;t<=k;t++)sfin[t]=s[t];
// }
//else {
// for(j=i+1;j<=m;j++)
// if(a[i]<=a[j] and L[i]==L[j]+1)
// afis_sol(j,k+1);
// }
//}
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x;
// if(prim(x))a[++m]=x;
// }
// for(i=m;i>=1;i--)
// { maxi=0;
// for(j=i+1;j<=m;j++)
// if((a[i]<=a[j])&&(maxi<L[j]))
// maxi=L[j];
// L[i]=maxi+1;
// }
// maxi=L[1];
// for(i=1;i<=m;i++)
// if(L[i]>maxi) maxi=L[i];
////for(i=1;i<=m;i++)fo<<a[i]<<" ";fo<<endl;
////for(i=1;i<=m;i++)fo<<L[i]<<" ";fo<<endl;
//for(int t=1;t<=maxi;t++) sfin[t]=2000000000;
//for(i=1;i<=m;i++)
// if(L[i]==maxi)afis_sol(i,1);
// fo<<maxi<<endl;
// for(int t=1;t<=maxi;t++) fo<<sfin[t]<<" ";
// return 0;
//}
//#include<fstream>
//# define M 203
//#include<iomanip>
//using namespace std;
//ifstream fi("prosir.in");
//ofstream fo("prosir.out");
//int n,i,j,maxi,d,m,S;
//int a[M][M],s[M][M];
//int main()
//{
// fi>>n>>m;
// for(i=0;i<=n+1;i++)
// for(j=0;j<=m+1;j++) s[i][j]=2000000000;
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// fi>>a[i][j];
//
// //calcul matrice
// for(i=1;i<=n;i++)
// s[i][m]=a[i][m];
// for(j=m-1;j>=1;j--)
// for(i=1;i<=n;i++)
// s[i][j]=a[i][j]+min(s[i-1][j+1],min(s[i][j+1],s[i+1][j+1]));
////for(i=0;i<=n+1;i++){for(j=0;j<=m+1;j++)fo<<setw(2)<<a[i][j]<<" ";fo<<endl;}
////for(i=1;i<=n;i++){for(j=1;j<=m;j++)fo<<setw(2)<<s[i][j]<<" ";fo<<endl;}
// //calcul solutie
// int mini=2000000000;
// for(i=1;i<=n;i++)
// mini=min(mini,s[i][1]);
// fo<<mini<<'\n';
// return 0;
//}
//https://www.pbinfo.ro/?pagina=profil&user=DinuDamsa
//#include<iostream>
//using namespace std;
//int n,r,b;
//int main(){
// cin>>n>>b;
// r=n&(1<<b);
// cout<<r;
//return 0;
//}
//#include<iostream>
//#include <fstream>
//#include<cstring>
//# define M 256
////#define fi cin
////#define fo cout
//using namespace std;
//ifstream fi("prosir.in");
//ofstream fo("prosir.out");
//int i,n,maxi,k,j;
//char s[M],*p,c1[M],c2[M],c[M][M];
//int main(){
// while(fi>>s){
// strcpy(c[++k],s);
// }
// for(i=1;i<=k;i++)
// for(j=i+1;j<=k;j++)
// if(strcmp(c[i],c[j])>0)swap(c[i],c[j]);
// for(i=1;i<=k;i++)fo<<c[i]<<'\n';
//return 0;
//}
//#include<iostream>
//#include<cstring>
//#define M 300
//using namespace std;
//char s[M],Litere[M],t[M];
//int i,n,j,k,z;
//bool litera(char x){
// if((x>='a' and x<='z')or
// (x>='A' and x<='Z'))return true;
// else return false;
// }
//int main()
//{
// cin.get(s,300);
// n=strlen(s);
// for(i=0;i<n;i++)
// if(litera(s[i]))t[k++]=s[i];
// cout<<t;
// return 0;
//}
////40p timpul
//#include <iostream>
//#include<fstream>
//# define M 10000
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("arme.in");
////ofstream fo("arme.out");
//int pr[40003];
//int p,x,y,d,c,MM,kk,j;
//int A[M], B[M], C[M],i,na,nb,nc,n;
//int SOL[M], SOLF1[M], SOLF2[M],nsol,nsolf1,nsolf2;
//int S[M],ns,R[M],nr,P[M],np,R1[M],nr1,DEL[M],ndel,RR[M],nrr;
////pune pe 0 tot vectorul si na pe 0
//void seteaza0(int A[M],int na){
//int i,n;
//na=0;
//n=M-1;
//for(i=0;i<=n;i++)A[i]=0;
//}
//void afiseaza(int A[M],int na){
//int i;
//for(i=1;i<=na;i++)fo<<A[i];fo<<" ";
//fo<<endl;
//}
////copiaza vectorul A in B
//void copiaza(int A[M],int na,int B[M],int &nb){
//int i;
//seteaza0(B,nb);
//nb=na;
//for(i=1;i<=na;i++)B[i]=A[i];
//}
////inverseaza vector A
//void inverseaza(int A[M],int na){
//int i,mij=na/2;
//for(i=1;i<=mij;i++)
// swap(A[i],A[na-i+1]);
//}
//
////C=A*B cu multe cifre fiecare
//void inmulteste(int A[M],int na,int B[M],int nb,int C[M],int &nc){
//int transport,i,x,j,AA[M],BB[M],naa,nbb;
//seteaza0(AA,naa);
//seteaza0(BB,nbb);
//seteaza0(C,nc);
//copiaza(A,na,AA,naa);
//copiaza(B,nb,BB,nbb);
//inverseaza(AA,naa);
//inverseaza(BB,nbb);
//for(i=1;i<=na;i++)
// for(j=1;j<=nb;j++)
// C[i+j-1]+=AA[i]*BB[j];
//nc=naa+nbb-1;
//transport=0;
//for(i=1;i<=nc;i++){
// x=transport+C[i];
// C[i]=x%10;
// transport=x/10;
// }
//if(transport>0)C[++nc]=transport;
//inverseaza(C,nc);
//}
//
//
//int main(){
// //ciur pana la 40000
//MM=40000;
//for(i=2;i<=MM;i++)
// if(pr[i]==0)
// for(j=2*i;j<=MM;j=j+i)pr[j]=1;
////vector de numere prime pana la 40000
//for(i=2;i<=MM;i++)
// if(pr[i]==0)pr[++kk]=i;
//
//na=1; //initial
//A[1]=1; //memoram numarul 1
//fi>>n;
//for(i=1;i<=n;i++){
// fi>>x;
// y=1;
// j=1;
// while(pr[j]*pr[j]<=x){
// p=0;d=pr[j];
// while(x%d==0){p++;x=x/d;}
// if(p)y=y*d;
// j++;
// }
// if(x)y=y*x;
// nb=0;
// while(y){
// c=y%10;
// B[++nb]=c;
// y=y/10;
// }
// inverseaza(B,nb);
// inmulteste(A,na,B,nb,C,nc);
// //afiseaza(A,na);afiseaza(B,nb);afiseaza(C,nc);
// copiaza(C,nc,A,na);
// //fo<<y<<" ";
//}
//afiseaza(A,na);
//return 0;
//}
//////40p timpul
//#include <iostream>
//#include<fstream>
//# define M 10000
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("arme.in");
////ofstream fo("arme.out");
//int p,x,y,d,c;
//int A[M], B[M], C[M],i,na,nb,nc,n;
//int SOL[M], SOLF1[M], SOLF2[M],nsol,nsolf1,nsolf2;
//int S[M],ns,R[M],nr,P[M],np,R1[M],nr1,DEL[M],ndel,RR[M],nrr;
//char sir[100];
////pune pe 0 tot vectorul si na pe 0
//void seteaza0(int A[M],int na){
//int i,n;
//na=0;
//n=M-1;
//for(i=0;i<=n;i++)A[i]=0;
//}
//void afiseaza(int A[M],int na){
//int i;
//for(i=1;i<=na;i++)fo<<A[i];fo<<" ";
//fo<<endl;
//}
////copiaza vectorul A in B
//void copiaza(int A[M],int na,int B[M],int &nb){
//int i;
//seteaza0(B,nb);
//nb=na;
//for(i=1;i<=na;i++)B[i]=A[i];
//}
////inverseaza vector A
//void inverseaza(int A[M],int na){
//int i,mij=na/2;
//for(i=1;i<=mij;i++)
// swap(A[i],A[na-i+1]);
//}
//
////C=A*B cu multe cifre fiecare
//void inmulteste(int A[M],int na,int B[M],int nb,int C[M],int &nc){
//int transport,i,x,j,AA[M],BB[M],naa,nbb;
//seteaza0(AA,naa);
//seteaza0(BB,nbb);
//seteaza0(C,nc);
//copiaza(A,na,AA,naa);
//copiaza(B,nb,BB,nbb);
//inverseaza(AA,naa);
//inverseaza(BB,nbb);
//for(i=1;i<=na;i++)
// for(j=1;j<=nb;j++)
// C[i+j-1]+=AA[i]*BB[j];
//nc=naa+nbb-1;
//transport=0;
//for(i=1;i<=nc;i++){
// x=transport+C[i];
// C[i]=x%10;
// transport=x/10;
// }
//if(transport>0)C[++nc]=transport;
//inverseaza(C,nc);
//}
//
//
//int main(){
//na=1; //initial
//A[1]=1; //memoram numarul 1
//fi>>n;
//for(i=1;i<=n;i++){
// fi>>x;
// y=1;
// d=2;
// while(d*d<=x){
// p=0;
// while(x%d==0){p++;x=x/d;}
// if(p)y=y*d;
// d++;
// }
// if(x)y=y*x;
// nb=0;
// while(y){
// c=y%10;
// B[++nb]=c;
// y=y/10;
// }
// inverseaza(B,nb);
// inmulteste(A,na,B,nb,C,nc);
// //afiseaza(A,na);afiseaza(B,nb);afiseaza(C,nc);
// copiaza(C,nc,A,na);
// //fo<<y<<" ";
//}
//afiseaza(A,na);
//return 0;
//}
////40p timpul
//#include <iostream>
//#include<fstream>
//# define M 10000
//#define fi cin
//#define fo cout
//using namespace std;
////ifstream fi("arme.in");
////ofstream fo("arme.out");
//int p,x,y,d,c;
//int A[M], B[M], C[M],i,na,nb,nc,n;
//int SOL[M], SOLF1[M], SOLF2[M],nsol,nsolf1,nsolf2;
//int S[M],ns,R[M],nr,P[M],np,R1[M],nr1,DEL[M],ndel,RR[M],nrr;
//char sir[100];
////pune pe 0 tot vectorul si na pe 0
//void seteaza0(int A[M],int na){
//int i,n;
//na=0;
//n=M-1;
//for(i=0;i<=n;i++)A[i]=0;
//}
//void afiseaza(int A[M],int na){
//int i;
//for(i=1;i<=na;i++)fo<<A[i];fo<<" ";
//fo<<endl;
//}
////copiaza vectorul A in B
//void copiaza(int A[M],int na,int B[M],int &nb){
//int i;
//seteaza0(B,nb);
//nb=na;
//for(i=1;i<=na;i++)B[i]=A[i];
//}
////inverseaza vector A
//void inverseaza(int A[M],int na){
//int i,mij=na/2;
//for(i=1;i<=mij;i++)
// swap(A[i],A[na-i+1]);
//}
//
////C=A*B cu multe cifre fiecare
//void inmulteste(int A[M],int na,int B[M],int nb,int C[M],int &nc){
//int transport,i,x,j,AA[M],BB[M],naa,nbb;
//seteaza0(AA,naa);
//seteaza0(BB,nbb);
//seteaza0(C,nc);
//copiaza(A,na,AA,naa);
//copiaza(B,nb,BB,nbb);
//inverseaza(AA,naa);
//inverseaza(BB,nbb);
//for(i=1;i<=na;i++)
// for(j=1;j<=nb;j++)
// C[i+j-1]+=AA[i]*BB[j];
//nc=naa+nbb-1;
//transport=0;
//for(i=1;i<=nc;i++){
// x=transport+C[i];
// C[i]=x%10;
// transport=x/10;
// }
//if(transport>0)C[++nc]=transport;
//inverseaza(C,nc);
//}
//
//
//int main(){
//na=1; //initial
//A[1]=1; //memoram numarul 1
//fi>>n;
//for(i=1;i<=n;i++){
// fi>>x;
// y=1;
// d=2;
// while(x!=1){
// p=0;
// while(x%d==0){p++;x=x/d;}
// if(p)y=y*d;
// d++;
// }
// nb=0;
// while(y){
// c=y%10;
// B[++nb]=c;
// y=y/10;
// }
// inverseaza(B,nb);
// inmulteste(A,na,B,nb,C,nc);
// //afiseaza(A,na);afiseaza(B,nb);afiseaza(C,nc);
// copiaza(C,nc,A,na);
// //fo<<y<<" ";
//}
//afiseaza(A,na);
//return 0;
//}
////30p var I timp depasit
//#include <iostream>
//#define M 1000001
//using namespace std;
//int i,n,d,x,m,j,a,b,k,t;
//int pr[M+3],s[100003];
//int main(){
//cin>>n;
////ciur
//pr[1]=1; //1 inseamna neprim si 0 inseamna prim
//for(i=2;i<=M;i++)
// if(pr[i]==0)
// for(j=2*i;j<=M;j=j+i)pr[j]=1;
//for(i=1;i<=n;i++)
//{
// cin>>a>>b;
// k=0;
// for(x=a;x<=b;x++)
// for(j=1;j<=x;j++)
// if(x%j==0 and pr[j]==0 and pr[x/j]==0){k++;break;};
// s[++t]=k;
//}
//for(i=1;i<=t;i++)cout<<s[i]<<" ";
//return 0;
//}
//#include <iostream>
//using namespace std;
//int a,b,x,y,z,k;
//
//int main(){
//cin>>a>>b;
//for(x=1;x<=100;x++)
// for(y=x;y<=100;y++)
// for(z=y;z<=100;z++)
// if((x*y+x*z+y*z)*b==x*y*z*a)
// {cout<<x<<" "<<y<<" "<<z<<'\n';k++;}
//if(k==0)cout<<"NU ARE SOLUTII";
//return 0;
//}
//1 1 2 1 2 3
// 1 2 1 3 2 1
////70p timpul
//#include <fstream>
//using namespace std;
//ifstream fi("primxxl.in");
//ofstream fo("primxxl.out");
//int i,n,x,k,sol,d,p;
//bool ok;
////verifica la ce putere apare d in desc. lui k!
////[k/p]+[k/p^2]+... [k/p^t]
//bool verif(int d,int p){
//int pp,z=0;
//pp=d;
//while(pp<=k){
// z+=k/pp;
// pp*=d;
//}
//return (z>=p);
//}
//int main(){
//fi>>n>>k;
//for(i=1;i<=n;i++){
// fi>>x;
// ok=true;
// d=2;
// while(x!=1 and d*d<=x)
// {
// p=0;
// while(x%d==0){p++;x=x/d;}
// if(p>0)
// if(!verif(d,p))ok=false;
// d++;
// }
// if(x>1)if(!verif(x,1))ok=false;
// if(ok)sol++;
//}
//fo<<sol;
//return 0;
//}
//100p fac dif. intre smini si smaxi
//smini - suma de la inceput pana la poz. minimului
//smaxi - suma de la inceput pana la poz. maximului
//#include <fstream>
//using namespace std;
//ifstream fi("memory002.in");
//ofstream fo("memory002.out");
//long long x,mini,maxi,p1,p2,s,n,i,smini,smaxi,sol;
//int main()
//{
// mini=2e9+1;
// maxi=-2e9-1;
// fi>>n;
// s=0;
// for(i=1;i<=n;i++){
// fi>>x;
// s+=x;
// if(x<mini){mini=x;smini=s;}
// if(x>maxi){maxi=x;smaxi=s;}
// }
// if(smini<smaxi)sol=smaxi-smini+mini;
// else sol=smini-smaxi+maxi;
// fo<<sol;
// return 0;
//}
////80p cu doua citiri din fisier timp depasit
//#include <fstream>
//using namespace std;
//ifstream fi("memory002.in");
//ofstream fo("memory002.out");
//long long x,mini,maxi,p1,p2,s,n,i;
//int main()
//{
// mini=2e9+1;
// maxi=-2e9-1;
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x;
// if(x<mini){mini=x;p1=i;}
// if(x>maxi){maxi=x;p2=i;}
// }
// fi.close();
// ifstream fi("memory002.in");
// if(p2<p1)swap(p1,p2);
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x;
// if(i>=p1 and i<=p2)s+=x;
// }
// fo<<s;
// return 0;
//}
////var II 65p cu cer 3 cu long double!!!)
//#include <fstream>
//#include <iomanip>
//using namespace std;
//ifstream fin("numere24.in");
//ofstream fout("numere24.out");
//int c,n,i,x,y,z,inv,cif,k;
//long long rez;
//int main()
//{
// fin>>c;
// if(c==1){
// fin>>n;
// if(n==0){fout<<0;return 0;}
// rez=(long long)(n-1)*10; //!!!
// fout<<rez;
// return 0;
// }
// if(c==2){
// fin>>x;
// //taiat o cifra
// y=x/10;
// if(y%10==0)fout<<0;
// else
// {
// inv=0;z=y;
// while(y){
// cif=y%10;
// inv=inv*10+cif;
// y=y/10;
// }
// if(inv==z)fout<<1;
// else fout<<2;
// }
// fout<<" ";
// //taiat 2 cifre
// y=x/100;
// if(y%10==0)fout<<0;
// else
// {
// inv=0;z=y;
// while(y){
// cif=y%10;
// inv=inv*10+cif;
// y=y/10;
// }
// if(inv==z)fout<<1;
// else fout<<2;
// }
// fout<<" ";
// //taiat 3 cifre
// y=x/1000;
// if(y%10==0)fout<<0;
// else
// {
// inv=0;z=y;
// while(y){
// cif=y%10;
// inv=inv*10+cif;
// y=y/10;
// }
// if(inv==z)fout<<1;
// else fout<<2;
// }
// fout<<" ";
// return 0;
// }
// if(c==3){
//// unsigned long long pp,p,nr_tot,nr_10,nr_pal,sol;
//// fin>>k;
//// if(k==1){fout<<9;return 0;}
//// p=1;
//// for(i=1;i<=k-1;i++)p=p*10;
//// pp=1;
//// for(i=1;i<=(k-1)/2;i++)pp=pp*10;
//// nr_tot=9*p;
//// nr_10=nr_tot/10;
//// nr_pal=9*pp;
//// sol=2*(nr_tot-nr_10-nr_pal)+nr_pal;
//// fout<<sol;
// long double pp,p,nr_tot,nr_10,nr_pal,sol;
// fin>>k;
// if(k==1){fout<<9;return 0;}
// p=1;
// for(i=1;i<=k-1;i++)p=p*10;
// pp=1;
// for(i=1;i<=(k-1)/2;i++)pp=pp*10;
// nr_tot=9*p;
// nr_10=nr_tot/10;
// nr_pal=9*pp;
// sol=2*(nr_tot-nr_10-nr_pal)+nr_pal;
// fout<<fixed<<setprecision(0)<<sol;
// }
//return 0;
//}
//
//#include <fstream>
//#define M 103
//using namespace std;
//ifstream fin("fermier.in");
//ofstream fout("fermier.out");
//int d[M],q[M],dist[M];
//int i,n,c,j,d1,d2,Stot,cant,nr_ture_suplimentare;
//long long DrumTot;
//int main()
//{
// fin>>n>>c;
// for(i=0;i<=n;i++)fin>>d[i];
// for(i=1;i<=n;i++)fin>>q[i];
// for(i=0;i<=n;i++)
// Stot+=d[i];//Stot - suma pe tot circuitul
// for(i=0;i<=n;i++) //dist[i]-este distanta de la depozit la ferma i
// dist[i+1]=dist[i]+d[i]; //o precalalculam ca sa ne incadram in timp
// cant=c;//cant- este cantitatea de ingrasaminte ce o avem initialin masina
// for(i=0;i<=n;i++)
// {
// if(cant==0 ){ // a ramas zero in masina bai!! (nu are rost sa mergem la i+1 cu gol!)
// //mergem la depozit si ne intoarcem la i+1 cu plin c
// //pas 1- merg de la ferma i la depozit si incarc c
// d1=dist[i]; //direct
// d2=Stot-dist[i]; //invers
// DrumTot+=min(d1,d2);
// cant=c;
// //pas 2- merg de la depozit(incarcat) la ferma i+1
// d1=dist[i+1]; //direct
// d2=Stot-dist[i+1]; //invers
// DrumTot+=min(d1,d2);
// }
// else //cantitate diferita de 0 deci ne deplasam de la i la i+1
// {
// //ne deplasam de la i la i+1
// d1=d[i]; //direct
// d2=Stot-d[i]; //invers
// DrumTot+=min(d1,d2);
// }
// //am ajuns la ferma i+1(deci facem livrarea c)
// if(cant>=q[i+1]) //avem ingrasaminte suficiente pentru a alimenta complet ferma i+1
// {cant-=q[i+1];q[i+1]=0;}
// else { //nu ajunge cantitate c pentru a alimenta complet ferma i+1
// q[i+1]-=cant;
// cant=0;
// //realimentam masina cu ingrasamant de cate ori trebuie
// nr_ture_suplimentare=q[i+1]/c;
// if(q[i+1]%c>0)nr_ture_suplimentare++;
// DrumTot+=nr_ture_suplimentare*2*min(dist[i+1],Stot-dist[i+1]);//facen o alimentare comleta
// cant=nr_ture_suplimentare*c-q[i+1];//calc. cantitatea ramasa dupa terminarea q[i+1]
// }
// }
// fout<<DrumTot;
//return 0;
//}
//#include <fstream>
//using namespace std;
//ifstream fin("colier.in");
//ofstream fout("colier.out");
//long long ucif,a[50001],b[50001];
//int i,j,x,n,s,p,z,t,k,poz_mini,mini,maxi,poz_maxi;
//int main()
//{
// fin>>t>>n;
// for(i=1;i<=n;i++)fin>>a[i];
// //construire vector b[] cu 1 si 2 in functie de tipul elementului
// for(i=1;i<=n;i++){
// x=a[i];
// maxi=0;mini=10;k=0;
// while(x>0){
// ucif=x%10;
// k++;
// if(ucif>maxi){maxi=ucif;poz_maxi=k;}
// if(ucif<mini){mini=ucif;poz_mini=k;}
// x=x/10;
// }
// if(poz_mini>poz_maxi)b[i]=1;
// else b[i]=2;
// }
// if(t==1){
// z=0;//numar elemente de tipul 1
// for(i=1;i<=n;i++)
// if(b[i]==1)z++;
// fout<<z;
// }
//pt cazul t==2
//fie k numarul de schimbari de tip(1->2 sau 2->1)
//avem sol k-1 daca b[1]==b[n]
//avem sol k daca b[1]!=b[n]
//pt 1 1 1 2 2 1 1 1 2 1 1 1 => 1 2 1 2 1 => sol = 4
//1 2 1 2 =>sol = 4
// if(t==2){
//
// int sol=1;//numar schimbari de tip(1->2 sau de la 2->1)
// for(i=1;i<n;i++)
// if(b[i]!=b[i+1])sol++;
// if(b[1]==b[n])sol--;
// if(sol==0)fout<<1;//cazul 1 1 1 1 => sol=1;
// else fout<<sol;
// }
// return 0;
//}
//#include <fstream>
//#include <cmath>
//using namespace std;
//ifstream f("cufar.in");
//ofstream g("cufar.out");
//int d,p,n,c[1010],x,y,i,j,k,a[1010],b[1010],maxi,s;
//int main()
//{
// f>>p>>n;
// if(p==1) {
// f>>x>>y;d=sqrt(x);
// for(i=2; i<=x; i++)
// c[i]=i;
// for(i=2; i<=d+1; i++){j=2;
// while(j*i<=x)
// {if(c[j*i]!=0)c[j*i]=0;j++;}}
// for(i=2; i<=x; i++)
// if(c[i]!=0) {
// if(x%c[i]==0)k++;
// if(k==y) {
// g<<c[i];
// break;
// }
// }
// }
// if(p==2) {
// for(i=1; i<=n; i++) {
// f>>a[i]>>b[i];
// if(a[i]>maxi)maxi=a[i];
// }maxi=sqrt(maxi);
// for(i=2; i<=maxi; i++)
// c[i]=i;
// for(i=2; i<=maxi; i++)
// for(j=2; j<=maxi; j++)
// if(c[j*i]!=0)c[j*i]=0;
//
// for(j=1; j<=n; j++){k=0;
// for(i=2; i<=a[j]; i++)
// if(c[i]!=0) {
// if(a[j]%c[i]==0)k++;
// if(k==b[j])
// {s+=c[i];break;}
// }}
//
// g<<s;
// }
// /*
// f>>x>>y;d=sqrt(x);
// for(i=2; i<=x; i++)
// c[i]=i;
// for(i=2; i<=d+1; i++){j=2;
// while(j*i<=x)
// {if(c[j*i]!=0)c[j*i]=0;j++;}}
// for(i=2; i<=x; i++)
// if(c[i]!=0) {
// if(x%c[i]==0)k++;
// if(k==y) {
// g<<c[i];
// break;
// }
// }
// */
// return 0;
//}
//
//
////var I 100p
//// descompunere in factori primi cu ciur
////se merge pt. fiecare x pana la sqrt(x)
////Daca ramane ceva ce ramane este numar prim
//#include<fstream>
//#include<cmath>
//#define M 1000003
//using namespace std;
//ifstream fi("cufar.in");
//ofstream fo("cufar.out");
//bool a[M];//ciurul
//int b[M];//vectorul cu numere prime
//int i,n,k,p,v,x,r,y,nb,d,nrd,j;
//long long s;
//int main(){
////ciurul
//for(i=2;i<=M-3;i++)
// if(a[i]==0)
// for(j=2*i;j<=M-3;j=j+i)a[j]=1;
//for(i=2;i<=M-3;i++)
// if(a[i]==0)b[++nb]=i;
////for(i=1;i<=100;i++)fo<<b[i]<<" ";
// fi>>v>>n;
// //cer 1
// if(v==1){ //fara ciur cu se incadreaza in timp
// fi>>x>>k;
// d=2;y=x;
// while(d*d<=y and x!=1)
// {
// p=0;
// while(x%d==0){p++;x=x/d;}
// if(p)nrd++;
// if(nrd==k){fo<<d;return 0;}
// d++;
// }
// fo<<x;//ramane un numar prim
// return 0; //daca nu a iesit deja cu break
//
// }
// //cer 2
// if(v==2){
// for(i=1;i<=n;i++){
// fi>>x>>k;
// j=1;y=x;
// nrd=0;
// int afis=0;
// while(b[j]*b[j]<=y and x!=1)//merg pana la sqrt(x)
// {
// p=0;
// while(x%b[j]==0){p++;x=x/b[j];}
// if(p)nrd++;
// if(nrd==k){s=s+(long long)b[j];afis=1;break;}
// j++;
// }
// if(afis==0)s=s+(long long)(x);//ramane un numar prim
// }
// fo<<s;
// }
//
//return 0;
//}
////var II 62p
//// descompunere in factori primi
////pana la sqrt(x). Daca ramane ceva este numar prim.
//#include<fstream>
//using namespace std;
//ifstream fi("cufar.in");
//ofstream fo("cufar.out");
//int i,n,k,p,v,x,r,y,nb,d,nrd;
//long long s;
//int main(){
//
// fi>>v>>n;
// //cer 1
// if(v==1){
// fi>>x>>k;
// d=2;y=x;
// while(d*d<=y and x!=1)
// {
// p=0;
// while(x%d==0){p++;x=x/d;}
// if(p)nrd++;
// if(nrd==k){fo<<d;return 0;}
// d++;
// }
// fo<<x;//ramane un numar prim
// return 0; //daca nu a iesit deja cu break
//
// }
// //cer 2
// if(v==2){
// for(i=1;i<=n;i++){
// fi>>x>>k;
// d=2;y=x;
// nrd=0;
// int afis=0;
// while(d*d<=y and x!=1) //desc. pana la sqrt(x)
// {
// p=0;
// while(x%d==0){p++;x=x/d;}
// if(p)nrd++;
// if(nrd==k){s=s+(long long)d;;afis=1;break;}
// d++;
// }
// if(afis==0)s=s+(long long)(x);//ramane un numar prim
// }
// fo<<s;
// }
//
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("gogosi.in");
//ofstream fo("gogosi.out");
//int a[1000003],c[1000003];
//int i,n,k,p;
//
////k = poz. pt. cel mai mare el.<= ca a[i];
////adica unde se va aseza x in sirul de cozi
//int cbin(int x,int &k){
// int st,dr,mij;
// if(x<c[k]){k++;return k;} //daca se pune x in coada noua
// st=1;dr=k; //daca trebuie cautata pozitia in sir
// while(st<dr){
// mij=(st+dr)/2;
// if(x<c[mij])st=mij+1; //in cazul asta c[mij] nu va fi sol. pt ca este mai mare ca x
// else dr=mij; //x>=c[mij]- este posibil ca c[mij] sa fie chiar solutie
// }
// return st;
//}
//int main(){
//
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// c[1]=a[1];k=1;
// for(i=2;i<=n;i++)
// {
// p=cbin(a[i],k);//p = poz. pt. cel mai mare el.<=ca a[i];
// c[p]=a[i];
// }
// fo<<k;
//return 0;
//}
//#include<fstream>
//#include<iomanip>
//#define M 30003
//using namespace std;
//ifstream fi("concurs4.in");
//ofstream fo("concurs4.out");
//int i,j,n,k,p,q,m,t,T,nb;
//int ant[M],urm[M],a[M];
//bool ciur[12*M+3];
//int b[M];
//int main()
//{
////generare Ciur cu primele 30000 numere prime
//T=12*M;
//for(i=2;i<=T;i++)
// if(ciur[i]==0)
// for(j=2*i;j<=T;j=j+i)ciur[j]=1;
//for(i=2;i<=T;i++)
// if(ciur[i]==0)
// if(nb<30000)
// b[++nb]=i;
////for(i=1;i<=100;i++)fo<<b[i]<<" ";
////fo<<nb<<endl;
//fi>>n>>k;
//ant[1]=n; //memoram ant[] si urm[] pentru rapiditate
//for(i=2;i<=n;i++)ant[i]=i-1;
//urm[n]=1;
//for(i=1;i<n;i++)urm[i]=i+1;
//m=n;
//i=1; //pornim de la poz 1
//while(m){
// t++;
// a[i]=t; //notam elementul
// p=ant[i];//stergem elementul ce a fost ales
// q=urm[i]; //gen alocare dinamica p i q
// urm[p]=q;
// ant[q]=p;
// i=q; //facem pasii urmatori catre urmatorul element
// for(j=2;j<=k;j++)i=urm[i];
// m--;
//// fo<<m<<endl;
//// for(j=1;j<=n;j++)fo<<setw(3)<<ant[j];fo<<endl;
//// for(j=1;j<=n;j++)fo<<setw(3)<<a[j];fo<<endl;
//// for(j=1;j<=n;j++)fo<<setw(3)<<urm[j];fo<<endl;
//}
//for(i=1;i<=n;i++)fo<<b[a[i]]<< " ";
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("coada2.in");
//ofstream fo("coada2.out");
//int x,k,cif,n,j,s,cu,i,y;
//int main()
//{
//fi>>n;
//for(i=1;i<=n;i++){
// fi>>x;
// y=x;
// cu=x%10;
// x=x/10;
// k=1;
// while(x){
// cif=x%10;
// k++;
// x=x/10;
// }
// if(k==1)s=s+y;
// else
// if(cif==cu){
// k=k/2;
// for(j=1;j<=k;j++)y=y/10;
// s=s+y%10;
// }
//}
//fo<<s;
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("bloc.in");
//ofstream fo("bloc.out");
//long long n,k,p,nr_numere,cat,rest,s_tot;
//int main()
//{
//fi>>k>>p>>n;
//nr_numere=n*p+p;
//cat=nr_numere/k;
//rest=nr_numere%k;
//s_tot=cat*k*(k+1)/2+rest*(rest+1)/2;
//fo<<s_tot;
//return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("interviu.in");
//ofstream fo("interviu.out");
//int n,p,i,maxi,a[103];
//int main()
//{
//fi>>n;
//for(i=1;i<=n;i++)fi>>a[i];
//p=0;
//maxi=max(max(a[1],a[2]),a[3]);
//for(i=4;i<=n;i++)
// if(a[i]>maxi){p=i;break;}
//if(p==0)fo<<n;
//else fo<<p;
//return 0;
//}
//
////inundatii infoarena 100p
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream f("inundatie.in");
//ofstream g("inundatie.out");
//int nn,n,mm,x,i,nrq,poz,ok,minn,maxx,mid,st,dr,k,a[90030];
//unsigned long long b[90030],s;
//int cautare_bin_poz(int y){//returneaza poz elementului x daca exista in sir
// int st,dr,k; //sau poz elementului mai mare ca x daca x nu exista in sir
// st=1; dr=n; k=0;
// while(st<=dr){
// mid=(st+dr)/2;
// if(a[mid]==x)return mid;
// if (a[mid]>x) dr=mid-1;
// else st=mid+1;
// }
// return dr;
//}
//int main()
//{
// f>>nn>>mm;
// for (i=1; i<=nn*mm; i++){
// f>>x;
// if(x>0){n++;a[n]=x;}
// }
// sort(a+1,a+n+1);
// f>>nrq;
// for (i=1; i<=n; i++){
// s=s+a[i]; b[i]=s;
// }
// for(i=1; i<=nrq; i++){
// f>>x; x--;;
// k=cautare_bin_poz(x);
// if (x==-1)g<<0<<'\n';
// else g<<b[k]+x*(n-k)<<'\n';
// }
// f.close();g.close();
// return 0;
//}
////30p timpul!
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//ifstream f("inundatie.in");
//ofstream g("inundatie.out");
//long long a[90001],nr,n,i,j,k,x,q,s,m;
//int main()
//{
// f>>n>>m;
// nr=n*m;
// for(i=1;i<=nr;i++)
// {j++;
// f>>a[j];
// }
// sort(a+1,a+nr+1);
// f>>q;
// for(j=1;j<=q;j++) {
// f>>x;s=0;
// if(x>1)
// for(i=1;i<=nr;i++) if(a[i])
// if(a[i]<x) s+=a[i];
// else break;
// s+=(x-1)*(nr-i+1);
// g<<s<<'\n';}
//
// f.close ();
// g.close ();
// return 0;
//}
//#include<fstream>
//using namespace std;
//ifstream fi("elfii.in");
//ofstream fo("elfii.out");
//int x,y,z,kp,k0;
//int main(){
//fi>>x>>y>>z;
////caz 1 toate impare
//if(x%2==1 and y%2==1 and z%2==1){fo<<"Poate data viitoare!";return 0;}
//
//if(x==0)k0++; //k0 numar cifre de 0
//if(y==0)k0++;
//if(z==0)k0++;
//if(x%2==0)kp++; //kp numar cifre pare
//if(y%2==0)kp++;
//if(z%2==0)kp++;
//
//if(x<y)swap(x,y); //asezare cifre descrescator
//if(x<z)swap(x,z);
//if(y<z)swap(y,z);
//if(k0==0){ //fara cifre de 0
// if(kp==3){fo<<6<<'\n'<<x<<y<<z;return 0;} //toate pare
// if(kp==2){fo<<4<<'\n'; //doua pare
// if(z%2==0)fo<<x<<y<<z;
// else fo<<x<<z<<y;
// return 0;
// }
// if(kp==1){fo<<2<<'\n'; //una para
// if(x%2==0)fo<<y<<z<<x;
// if(y%2==0)fo<<x<<z<<y;
// if(z%2==0)fo<<x<<y<<z;
// return 0;
// }
//}
//if(k0==1){ //o cifra de 0
// if(kp==3){fo<<4<<'\n'<<x<<y<<z;return 0;} //toate pare
// if(kp==2){fo<<3<<'\n'; //doua pare
// if(z%2==0)fo<<x<<y<<z;
// else fo<<x<<z<<y;
// return 0;
// }
// if(kp==1){fo<<4<<'\n'; //una para
// fo<<x<<y<<z;
// return 0;
// }
//}
//if(k0==2){ //doua cifre de 0
//
// fo<<2<<'\n';
// fo<<x<<y<<z;
// return 0;
//
//}
//return 0;
//}
//#include <fstream>
//#include <iomanip>
//# define M 200001
//using namespace std;
//ifstream fin ("strabunica.in");
//ofstream fout ("strabunica.out");
//long long i,n,k,j,maxi,a[M],st[M],s[M],d[M];
//int main()
//{
// fin>>n;
// for(i=1;i<=n;i++)fin>>a[i];
// //construim vectorul s
// for(i=1;i<=n;i++){
// while(k>=1 && a[st[k]]>a[i])k--;
// if(k>=2 && a[st[k-1]]==a[st[k]] && a[st[k]]==a[i])k--;
// st[++k]=i;
// //for(j=0;j<=k;j++)fout<<a[st[j]]<<" ";fout<<endl;
// if(k>=2 && a[st[k-1]]==a[st[k]])
// s[i]=st[k]-st[k-2];
// else s[i]=st[k]-st[k-1];
// }
// //construim vectorul d
// k=0;
// st[k]=n+1;
// for(i=n;i>=1;i--){
// while(k>=1 && a[st[k]]>a[i])k--;
// if(k>=2 && a[st[k-1]]==a[st[k]] && a[st[k]]==a[i])k--;
// st[++k]=i;
// //for(j=0;j<=k;j++)fout<<a[st[j]]<<" ";fout<<endl;
// if(k>=2 && a[st[k-1]]==a[st[k]])
// d[i]=st[k-2]-st[k];
// else d[i]=st[k-1]-st[k];
// }
//// for(i=1;i<=n;i++)fout<<setw(3)<<s[i];fout<<endl;
//// for(i=1;i<=n;i++)fout<<setw(3)<<d[i];fout<<endl;
// for(i=1;i<=n;i++)
// if(a[i]*(s[i]+d[i]-1)>maxi)maxi=a[i]*(s[i]+d[i]-1);
// fout<<maxi;
// return 0;
//}
//#include <iosream>
//#include <fsream>
//using namespace sd;
//ifsream fin("g2.in");
//ofsream fout("g2.out");
//
//int main()
//{
// long long n,v[10000003],i,x,c;
// fin>>n;
// for(i=2;i*i<n;i++)
// {
// while(n%i==0)
// {
// v[i]=i;
// n=n/i;
// }
// }
// for(i=2;i<n;i++)
// {
// if(v[i]>9)x=0;
// else x=1;
// }
// if(x==0)fout<<'0';
// else
// {
// fout<<v[2];
// for(i=k;i<n;i++)
// {
// while(c<10)
// {
// c=v[i]*v[i+1];
// }
// fout<<c;
// }
//
// }
// fin.close();
// fout.close();
// return 0;
//}
//
////Gonda Bogdan
//// clasa a VIII-a
//
//
//#include <iosream>
//#include <fsream>
//#include <cmath>
//using namespace sd;
//
//ifsream fin("sircifre.in");
//ofsream fout("sircifre.out");
//int v[501];
// int k[501];
//int abs(int x){
// if(x<0)return -x;
// else return x;
//}
//int main()
//{
//
//int s=0;
//int cnt4=0;
//int cnt1=0;
// int n;
// int cnt=1;
//
// int l[10]={0};
// fin>>n;
// int p=n;
//
// for(int i=1;i<=n;i++)
// {fin>>v[i];
// k[i]=v[i];}
// while(cnt>0)
// {
// cnt=0;
//
// for(int i=1;i<n;i++)
// {
// if(abs(v[i]-v[i+1])==1 && v[i]!=0 && v[i+1]!=0)
// {
//
//cnt++;
//s=0;
// for(int j=i+2;j<=n;j++)
// {
//
// v[i+s]=v[j];
// s++;
// }v[i+s+1]=0;
//v[i+s+2]=0;
//n=n-2;cnt1++;
//
//
//
// }
//
// }
//
// }
//
// for(int i=1;i<=n;i++)
// {
// l[v[i]]++;
// }
//
//for(int i=1;i<=n;i++)
//{
// if(l[i]!=0)
// {
// cnt4++;
// fout<<i<<" "<<l[i]<<"\n";
// }
//
//}
//if(cnt4==0)
// fout<<-1;
//
//
//
//
//
// return 0;
//}
/////Dobricean Ioan
///// siva cu complexitatea O(n)
//#include <sack>
//#include <fsream>
//#include <cmath>
//using namespace sd;
//ifsream fin ("sircifre.in");
//ofsream fout ("sircifre.out");
//int n,val,F[11],x;
//sack <int> S;
//int abs(int x){
// if(x<0)return -x;
// else return x;
//}
//int main() {
// int i;
//fin >> n;
//for( i = 1; i <= n; i++) {
// fin >> x;
// if(S.empty()) S.push(x) , F[x]++;
// else {
// val = S.top();
// if(abs(val-x) == 1) {
// S.pop();
// F[val]--;
// }
// else {
// S.push(x);
// F[x]++;
// }
//
//}
//}
//bool ok = false;
//for(i = 0; i <= 9; i++) {
// if(F[i] > 0)
// fout << i << " " << F[i] <<"\n" ,ok = true;
// }
//if(!ok) fout << -1;
//}
///// Doamne ajuta
//#include <fsream>
//using namespace sd;
//ifsream fi("sortare.in");
//ofsream fo("sortare.out");
//int a[1001],i,j,n,aux;
//int abs(int x){
// if(x<0)return -x;
// else return x;
//}
//int main()
//{
// //citirea
// fi>>n;
// for(i=1;i<=n;i++)fi>>a[i];
// //ordonarea
// for(i=1;i<=n;i++)
// for(j=i+1;j<=n;j++)
// if(a[i]<a[j]){
// aux=a[i];
// a[i]=a[j];
// a[j]=aux;
// }
// //afisarea
// for(i=1;i<=n;i++)fo<<a[i]<<" ";
// return 0;
//}
//
//
//
////cu doua citiri din fisier
//#include <fsream>
//using namespace sd;
//ifsream fi("memory002.in");
//ofsream fo("memory002.out");
//long long x,mini,maxi,p1,p2,s,n,i;
//int main()
//{
// mini=2e9+1;
// maxi=-2e9-1;
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x;
// if(x<mini){mini=x;p1=i;}
// if(x>maxi){maxi=x;p2=i;}
// }
// fi.close();
// ifsream fi("memory002.in");
// if(p2<p1)swap(p1,p2);
// fi>>n;
// for(i=1;i<=n;i++){
// fi>>x;
// if(i>=p1 and i<=p2)s+=x;
// }
// fo<<s;
// return 0;
//}
//#include <fsream>
//using namespace sd;
//ifsream fi("memory005.in");
//ofsream fo("memory005.out");
//int i,n,x,k;
//long long M =666013;
//long long sol;
//int main()
//{
// fi>>n;
// for(i=1;i<=n;i++)
// {
// fi>>x;
// if(x%2==1)k++;
// }
// //calculam 2^(n-1)
// sol=1;
// for(i=1;i<=n-1;i++)
// sol=((long long)2*sol)%M;
// //daca avem numai elemente pare avem sol 2^n-1(altfel 2^(n-1)-1
// if(k==0)fo<<((long long)2*sol)%M-1;
// else fo<<sol-1;
// return 0;
//}
//dem cu rel de recursivitate
//dp[0][j] - cate submultimi cu suma para din primele j elemente avem
//dp[1][j]- cate submultimi cu suma impara din primele j elemente avem
//dp[0][j+1]=dp[0][j]+dp[1][j]
//dp[1][j+1]=dp[0][j]+dp[1][j]=>ele sunt egale si dp[0][j+1]=dp[1][j+1]=2^j
bodnariuc danut danutbod