//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// fout << "Hello world";
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n,m;
// fin >> n;
// m = n + 2;
// fout << m;
//}
//#include<fstream>>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
// bool operator < (Nod A) const {
// return val > A.val;
// }
//};
//struct tablou {
// int val, vizit;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//tablou mat[1502][1502];
//int n,m;
//
//Nod start;
//bool InInterior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= n)
// return true;
// return false;
//}
//int Fill() {
// priority_queue<Nod> coada;
// Nod aux, varf;
// int k, i, j;
// coada.push({ 1,1,mat[1][1].val });
// mat[1][1].vizit = 1;
// // mat[start.lin][start.col] = -1;
// while (coada.empty() == 0) {
// varf = coada.top();
// coada.pop();
// if (varf.lin == n && varf.col == n)
// return varf.val;
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
//
// if (InInterior(aux)) {
// if (mat[aux.lin][aux.col].vizit == 0) {
// mat[aux.lin][aux.col].vizit = 1;
// mat[aux.lin][aux.col].val++;
// aux.val = mat[aux.lin][aux.col].val;
// coada.push(aux);
// }
// }
// }
// }
//}
//int main() {
// int i, x, y, z, t, j;
// fin >> n >> x >> y >> z >> t;
// for (j = 1; j <= n; j++) {
// fin >> mat[1][j].val;
//
// }
// for (i = 2; i <= n; i++)
// for (j = 1; j <= n; j++) {
// mat[i][j].val = 1 + (mat[i - 1][j - 1].val * x + mat[i - 1][j].val * y + mat[i - 1][j + 1].val * z) % t;
//
// }
// /* for (i = 1; i <= n; i++,fout<<endl)
// for (j = 1; j <= n; j++)
// fout << mat[i][j] << " ";*/
//
// fout << Fill();
//
//}
//#include<fstream>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col,val;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], replica[102][102],n,m;
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a, Nod b) {
// int k;
// bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// mat[a.lin][a.col] = 1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// if (varf.lin == b.lin && varf.col == b.col) {
// h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0) {
// mat[aux.lin][aux.col] = varf.val + 1;
// aux.val = varf.val + 1;
// coada.push(aux);
// }
// }
// }
// }
// if (h == false)
// return -1;
//}
//void refac() {
// int i, j;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// mat[i][j] = replica[i][j];
//}
//int main() {
// int i, j, k,q,x1,y1,x2,y2;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> c;
// if (c == 'a')
// mat[i][j] = 0;
// else
// mat[i][j] = 1;
// replica[i][j] = mat[i][j];
// }
// }
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> x1 >> y1 >> x2 >> y2;
// if (mat[x1][y1] == 1)
// fout << -1 << endl;
// else {
// fout << Explorare({ x1,y1,1 }, { x2,y2,1 }) << '\n';
// /*for (j = 1; j <= n; j++, fout << endl)
// for (k = 1; k <= m; k++)
// fout << mat[j][k] << " ";*/
// refac();
// }
// }
//}
//#include<fstream>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//struct Teleport {
// int x1, y1, x2, y2;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], replica[102][102], n, m;
//Teleport tel[102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a) {
// int k;
// bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// int e;
// mat[a.lin][a.col] = -1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// e = 1;
// if (varf.lin == n && varf.col == m) {
// h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// while (mat[aux.lin][aux.col] > 0) {
// aux.lin = tel[mat[aux.lin][aux.col]].x2;
// aux.col = tel[mat[aux.lin][aux.col]].y2;
// e++;
// }
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0) {
// mat[aux.lin][aux.col] = -1;
// aux.val = varf.val + e;
// coada.push(aux);
// }
// }
// }
// }
// if (h == false)
// return -1;
//}
//void refac() {
// int i, j;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// mat[i][j] = replica[i][j];
//}
//int main() {
// int i, j, k, q;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> mat[i][j];
// }
// }
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> tel[i].x1 >> tel[i].y1 >> tel[i].x2 >> tel[i].y2;
// mat[tel[i].x1][tel[i].y1] = i;
// }
// fout << Explorare({ 1,1,0 });
//}
//#include<fstream>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//struct AAA {
// int val, vizit;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//AAA mat[102][102];
//int n, m;
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a,Nod b) {
// int k;
// bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// int e;
// mat[a.lin][a.col].vizit = 1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
//
// if (varf.lin == b.lin && varf.col == b.col) {
// h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
//
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col].vizit == 0) {
// mat[aux.lin][aux.col].vizit = 1;
// // mat[aux.lin][aux.col].val = varf.val + 1;
// if (mat[aux.lin][aux.col].val != mat[varf.lin][varf.col].val)
// aux.val = varf.val + mat[aux.lin][aux.col].val * mat[varf.lin][varf.col].val;
// else
// aux.val = varf.val;
// fout << aux.val << " ";
// coada.push(aux);
// }
// }
// }
// }
// if (h == false)
// return -1;
//}
//
//int main() {
// int i, j,x1,y1,x2,y2;
// char c;
// fin >> n >> m >> x1 >> y1 >> x2 >> y2;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> mat[i][j].val;
// }
// }
//
// fout << Explorare({ x1,y1,0 }, { x2,y2,0 });
// /*for (i = 1; i <= n; i++,fout<<endl) {
// for (j = 1; j <= m; j++) {
// fout << mat[i][j].val << " ";
// }
// }*/
//}
//#include<fstream>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[1002][1002], n, m, A[1002][1002];
//struct Nod {
// int lin, col, pasi;
//};
//Nod start;
//bool InInterior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//void Fill() {
// queue<Nod> coada;
// Nod aux, varf;
// int k, i, j;
// coada.push(start);
// // mat[start.lin][start.col] = -1;
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (InInterior(aux)) {
// if (A[varf.lin][varf.col] + mat[aux.lin][aux.col] < A[aux.lin][aux.col]) {
// A[aux.lin][aux.col] = A[varf.lin][varf.col] + mat[aux.lin][aux.col];
// coada.push(aux);
// }
// }
// }
// }
//}
//int main() {
// int i, j, x, y;
// fin >> n >> m;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++) {
// fin >> mat[i][j];
// A[i][j] = inf;
// }
// fin >> start.lin >> start.col >> x >> y;
// A[start.lin][start.col] = mat[start.lin][start.col];
// Fill();
//
// /* for (i = 1; i <= n; i++,fout<<endl)
// for (j = 1; j <= m; j++)
// fout << A[i][j] << " ";*/
// fout << A[x][y];
//}
//#include<fstream>
//#include<queue>
//#include<iomanip>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//struct Nod {
// int lin, col;
//};
//struct DDD {
// int val, nord, est, sud, vest;
//};
//Nod start, varf, v,auxx;
//int n, ltras, A[102][102],pas[102];
//DDD V[103][103];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= n)
// return true;
// return false;
//}
//int main() {
// int i, j, lin, col, x,aux,nrpoz,nr0=0,k;
// bool h = false;
// queue<Nod> coada;
// fin >> start.lin >> start.col >> n >> ltras;
// varf.lin = start.lin + 1;
// varf.col = start.col + 1;
// V[varf.lin][varf.col].val = 1;
//
// for (i = 1; i <= ltras; i++)
// fin >> pas[i];
//
// for (i = 1; i <= ltras, h == false; i++) {
// aux = V[varf.lin][varf.col].val;
// v = varf;
// switch (pas[i]) {
// case 1:
// varf.lin--;
// if (V[varf.lin][varf.col].val == 0) {
// V[varf.lin][varf.col].val = aux + 1;
// V[varf.lin][varf.col].sud = 1;
// V[v.lin][v.col].nord = 1;
// }
// else {
// V[varf.lin][varf.col].sud = 1;
// nrpoz = i - V[varf.lin][varf.col].val;
// h = true;
// }
// break;
//
// case 2:
// varf.col++;
// if (V[varf.lin][varf.col].val == 0) {
// V[varf.lin][varf.col].val = aux + 1;
// V[varf.lin][varf.col].vest = 1;
// V[v.lin][v.col].est = 1;
// }
// else {
// V[varf.lin][varf.col].vest = 1;
// nrpoz = i - V[varf.lin][varf.col].val;
// h = true;
// }
// break;
//
// case 3:
// varf.lin++;
// if (V[varf.lin][varf.col].val == 0) {
// V[varf.lin][varf.col].val = aux + 1;
// V[varf.lin][varf.col].nord = 1;
// V[v.lin][v.col].sud = 1;
// }
// else {
// V[varf.lin][varf.col].nord = 1;
// nrpoz = i - V[varf.lin][varf.col].val;
// h = true;
// }
// break;
//
// case 4:
// varf.col--;
// if (V[varf.lin][varf.col].val == 0) {
// V[varf.lin][varf.col].val = aux + 1;
// V[varf.lin][varf.col].est = 1;
// V[v.lin][v.col].vest = 1;
// }
// else {
// V[varf.lin][varf.col].est = 1;
// nrpoz = i - V[varf.lin][varf.col].val;
// h = true;
// }
// break;
//
// }
// }
// /*for (i = 1; i <= n + 1; i++,fout<<endl) {
// for (j = 1; j <= n + 1; j++) {
// fout << setw(9) << "[ " << V[i][j].val << "," << V[i][j].nord << V[i][j].est << V[i][j].sud << V[i][j].vest << " ] ";
// }
// }*/
// fout << nrpoz+1 << endl;
// for (j = 1; j <= n; j++) {
// if (V[1][j].est == 0) {
// coada.push({ 1,j });
// A[1][j] = 1;
// }
// if (V[n+1][j].est == 0) {
// coada.push({ n,j });
// A[n][j] = 1;
// }
// }
// for (i = 1; i <= n; i++) {
// if (V[i][1].sud == 0) {
// coada.push({ i,1 });
// A[i][1] = 1;
// }
// if (V[i][n + 1].sud == 0) {
// coada.push({ i,n });
// A[i][n] = 1;
// }
// }
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// for (k = 0; k < 4; k++) {
// auxx.lin = varf.lin + di[k];
// auxx.col = varf.col + dj[k];
// if (In_interior(auxx)) {
// if (A[auxx.lin][auxx.col] == 0) {
// switch (k) {
// case 0:
// if (V[varf.lin][varf.col].est == 0) {
// coada.push(auxx);
// A[auxx.lin][auxx.col] = 1;
// }
// break;
//
// case 1:
// if (V[varf.lin][varf.col+1].sud == 0) {
// coada.push(auxx);
// A[auxx.lin][auxx.col] = 1;
// }
// break;
//
// case 2:
// if (V[varf.lin+1][varf.col].est == 0) {
// coada.push(auxx);
// A[auxx.lin][auxx.col] = 1;
// }
// break;
//
// case 3:
// if (V[varf.lin][varf.col].sud == 0) {
// coada.push(auxx);
// A[auxx.lin][auxx.col] = 1;
// }
// break;
// }
// }
// }
// }
// }
//
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// if (A[i][j] == 0)
// nr0++;
// fout << nr0;
//}
// TEOREMA
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int dim = 100;
//int u[1002], prim[1002];
//void Ciur() {
// int i, j;
// prim[0] = 1;
// prim[1] = 1;
// for (i = 4; i <= dim; i=i+2)
// prim[i] = 1;
// for (i = 3; i * i <= dim; i=i+2) {
// for (j = i*i; j <= dim; j = j + 2 * i)
// prim[j] = 1;
// }
//
//}
//int main() {
// Ciur();
// /*for (int i = 1; i <= dim; i++)
// if (prim[i] == 0)
// fout << i << " ";*/
// int n, k, i,j,nr,varf,maxi=0,ind;
// queue<int> coada;
// fin >> n >> k;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// nr = 0;
// for (i = 1; i <= n; i++) {
// coada.push(u[i]);
// if (prim[u[i]] == 1) {
//
// nr++;
//
// }
// while (nr > k) {
// varf = coada.front();
// coada.pop();
// if (prim[varf] == 1)
// nr--;
// }
// if (coada.size() > maxi) {
// maxi = coada.size();
// ind = i - coada.size() + 1;
// }
//
// }
// fout << maxi << " " << ind;
//}
//#include<fstream>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//struct Teleport {
// int x1, y1, x2, y2;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102],matt[102][102], n, m;
//Teleport tel[102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a) {
// int k;
// bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// int e;
// mat[a.lin][a.col] = -1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// e = 1;
// if (varf.lin == n && varf.col == m) {
// //h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// e = 1;
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (mat[aux.lin][aux.col] > 0) {
// mat[aux.lin][aux.col] = -1;
// aux.lin = tel[mat[aux.lin][aux.col]].x2;
// aux.col = tel[mat[aux.lin][aux.col]].y2;
// e++;
// }
// else
// if (matt[aux.lin][aux.col] > 0) {
// matt[aux.lin][aux.col] = -1;
// aux.lin = tel[matt[aux.lin][aux.col]].x1;
// aux.col = tel[matt[aux.lin][aux.col]].y1;
// e++;
// }
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] != -1) {
// mat[aux.lin][aux.col] = -1;
// aux.val = varf.val + e;
// coada.push(aux);
// }
// }
// }
// }
//
//}
//
//int main() {
// int i, j, k, q;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// fin >> mat[i][j];
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> tel[i].x1 >> tel[i].y1 >> tel[i].x2 >> tel[i].y2;
// mat[tel[i].x1][tel[i].y1] = i;
// matt[tel[i].x2][tel[i].y2] = i;
// }
// fout << Explorare({ 1,1,0 });
//}
//#include<fstream>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//struct Teleport {
// int x1, y1, x2, y2;
//};
//struct dus_intors {
// int val;
// bool h; // h=0 => dus h=1 => intors
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int replica[102][102], n, m;
//dus_intors mat[102][102];
//Teleport tel[102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a) {
// int k;
// //bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// int e;
// mat[a.lin][a.col].val = -1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// e = 1;
// if (varf.lin == n && varf.col == m) {
// //h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// e = 1;
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// while (mat[aux.lin][aux.col].val > 0) {
//
// // if (mat[aux.lin][aux.col].h == 0) {
// aux.lin = tel[mat[aux.lin][aux.col].val].x2;
// aux.col = tel[mat[aux.lin][aux.col].val].y2;
// // }
// /*else {
// aux.lin = tel[mat[aux.lin][aux.col].val].x1;
// aux.col = tel[mat[aux.lin][aux.col].val].y1;
// }*/
// mat[aux.lin][aux.col].val = -1;
// e++;
// }
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col].val != -1) {
// mat[aux.lin][aux.col].val = -1;
// aux.val = varf.val + e;
// coada.push(aux);
// }
// }
// }
// }
//
//}
//
//int main() {
// int i, j, k, q;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> mat[i][j].val;
//
// }
// }
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> tel[i].x1 >> tel[i].y1 >> tel[i].x2 >> tel[i].y2;
// mat[tel[i].x1][tel[i].y1].val = i;
// mat[tel[i].x2][tel[i].y2].val = i;
//
// // mat[tel[i].x1][tel[i].y1].h = 0;
// // mat[tel[i].x2][tel[i].y2].h = 1;
// }
// fout << Explorare({ 1,1,0 });
//}
//#include<fstream>
//#include<queue>
//#define inf 1000000000
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//struct Teleport {
// int x1, y1, x2, y2;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], replica[102][102], n, m;
//Teleport tel[102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a) {
// int k;
// bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// int e;
// mat[a.lin][a.col] = -1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// e = 1;
// if (varf.lin == n && varf.col == m) {
// //h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// e = 1;
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// while (mat[aux.lin][aux.col] > 0) {
//
// aux.lin = tel[mat[aux.lin][aux.col]].x2;
// aux.col = tel[mat[aux.lin][aux.col]].y2;
// mat[aux.lin][aux.col] = -1;
// e++;
// }
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] != -1) {
// mat[aux.lin][aux.col] = -1;
// aux.val = varf.val + 1;
// coada.push(aux);
// }
// }
// }
// }
//
//}
//void refac() {
// int i, j;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// mat[i][j] = replica[i][j];
//}
//int main() {
// int i, j, k, q;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> mat[i][j];
// replica[i][j] = mat[i][j];
// }
// }
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> tel[i].x1 >> tel[i].y1 >> tel[i].x2 >> tel[i].y2;
// mat[tel[i].x1][tel[i].y1] = i;
// }
// fout << Explorare({ 1,1,0 });
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//int u[200002];
//int Doi(int n) {
// int nr = 0;
// while (n / 2 > 0) {
// nr++;
// n /= 2;
// }
// return nr;
//}
//int main() {
//
// int n, k, i, j, nr, varf, maxi = 0, ind;
// queue<int> coada;
// fin >> n >> k;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// nr = 0;
// for (i = 1; i <= n; i++) {
// coada.push(u[i]);
//
// nr += Doi(u[i]);
// while (nr > k) {
// varf = coada.front();
// coada.pop();
// /*if (prim[varf] == 1)
// nr--;*/
// nr -= Doi(varf);
// }
// if (coada.size() > maxi) {
// maxi = coada.size();
// ind = i - coada.size() + 1;
// }
//
// }
// fout << maxi;
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//int Doi(int n) {
// int nr = 0;
// while (n / 2 > 0) {
// nr++;
// n /= 2;
// }
// return nr;
//}
//int main() {
//
// int n, k, i, j, nr, varf, x, doi, maxi = 0, ind;
// queue<int> coada;
// fin >> n >> k;
// for (i = 1; i <= n; i++) {
// fin >> x;
// doi = Doi(x);
// nr = 0;
// fout << doi << " ";
// coada.push(doi);
//
// nr += doi;
// while (nr > k) {
// varf = coada.front();
// coada.pop();
// /*if (prim[varf] == 1)
// nr--;*/
// nr -= varf;
// }
// if (nr == k) {
//
// }
// if (coada.size() > maxi) {
// maxi = coada.size();
// ind = i - coada.size() + 1;
// }
//
// }
// fout << maxi;
//}
//#include<fstream>
//#include<queue>
//
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//struct Teleport {
// int x1, y1, x2, y2;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], replica[102][102], n, m;
//Teleport tel[102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a) {
// int k;
// bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// int e;
// mat[a.lin][a.col] = -1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// e = 1;
// if (varf.lin == n && varf.col == m) {
// h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// /* while (mat[aux.lin][aux.col] > 0) {
// aux.lin = tel[mat[aux.lin][aux.col]].x2;
// aux.col = tel[mat[aux.lin][aux.col]].y2;
// e++;
// }*/
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] != -1) {
// if (mat[aux.lin][aux.col] == 0) {
// mat[aux.lin][aux.col] = -1;
// aux.val = varf.val + 1;
// coada.push(aux);
// }
// else {
//
// aux.val = varf.val + 1;
// coada.push(aux);
// aux.val = varf.val - 1;
// aux.lin = tel[mat[aux.lin][aux.col]].x2;
// aux.col = tel[mat[aux.lin][aux.col]].y2;
// if (mat[aux.lin][aux.col] == 0) {
// mat[aux.lin][aux.col] = -1;
// aux.val = varf.val + 1;
// coada.push(aux);
// }
// mat[aux.lin][aux.col] = -1;
// }
// }
// }
// }
// }
// if (h == false)
// return -1;
//}
//void refac() {
// int i, j;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// mat[i][j] = replica[i][j];
//}
//int main() {
// int i, j, k, q;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> mat[i][j];
// }
// }
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> tel[i].x1 >> tel[i].y1 >> tel[i].x2 >> tel[i].y2;
// mat[tel[i].x1][tel[i].y1] = i;
// }
//
// fout << Explorare({ 1,1,0 });
// /* for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= m; j++)
// fout << mat[i][j] << " ";*/
//}
//#include<fstream>
//#include<queue>
//
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//struct Teleport {
// int x1, y1, x2, y2;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], replica[102][102], n, m;
//Teleport tel[102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare(Nod a) {
// int k;
// bool h = false;
// queue<Nod> coada;
// Nod aux, varf;
// int e;
// mat[a.lin][a.col] = -1;
// coada.push(a);
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// e = 1;
// if (varf.lin == n && varf.col == m) {
// h = true;
// return varf.val;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// /* while (mat[aux.lin][aux.col] > 0) {
// aux.lin = tel[mat[aux.lin][aux.col]].x2;
// aux.col = tel[mat[aux.lin][aux.col]].y2;
// e++;
// }*/
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] != -1) {
// if (mat[aux.lin][aux.col] == 0) {
// mat[aux.lin][aux.col] = -1;
// aux.val = varf.val + 1;
// coada.push(aux);
// }
// else {
// aux.val = varf.val + 1;
// coada.push(aux);
// aux.val = varf.val;
// aux.lin = tel[mat[aux.lin][aux.col]].x2;
// aux.col = tel[mat[aux.lin][aux.col]].y2;
//
// }
// }
// }
// }
// }
// if (h == false)
// return -1;
//}
//
//int main() {
// int i, j, k, q;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> mat[i][j];
// }
// }
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> tel[i].x1 >> tel[i].y1 >> tel[i].x2 >> tel[i].y2;
// mat[tel[i].x1][tel[i].y1] = i;
// }
//
// fout << Explorare({ 1,1,0 });
// /* for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= m; j++)
// fout << mat[i][j] << " ";*/
//}
//#include<fstream>
//#include<queue>
//#include<iomanip>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], n, m;
//queue<Nod> coada;
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Explorare() {
// Nod aux, varf;
// int k;
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// if (mat[varf.lin][varf.col] == -2)
// return varf.val;
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0 || mat[aux.lin][aux.col] == -2) {
// aux.val = varf.val + 1;
// mat[aux.lin][aux.col] = aux.val;
// coada.push(aux);
// }
// }
// }
// }
//}
//bool Insula(int lin, int col) {
// int a;
// a = mat[lin][col];
// for (int k = 0; k < 4; k++)
// if(In_interior({lin+di[k],col+dj[k],0}))
// if (mat[lin + di[k]][col + dj[k]] == a) {
// // fout << lin + di[k] << " " << col + dj[k] << " ";
// return true;
//
// }
// return false;
//}
//int main() {
// int i, j, aux;
// char c;
// fin >> n >> m;
// for(i=1;i<=n;i++)
// for (j = 1; j <= m; j++) {
// fin >> c;
// aux = c - '0';
// if (aux == 1) {
//
// if (Insula(i, j)) {
// fout << i << " " << j << endl;
// coada.push({ i,j ,0 });
// }
// mat[i][j] = -1;
// }
// if (aux == 2)
// mat[i][j] = -2;
// if (aux == 3)
// mat[i][j] = -3;
// }
// //for (i = 1; i <= n; i++, fout << endl)
// // for (j = 1; j <= m; j++)
// // fout << setw(5) << mat[i][j] << " ";
// fout << Explorare();
//}
// 8.2
/*
Se da un vector a[] de lungime n. Se fac deplasari in vector astfel : daca pozitia curenta este la i (i=[1,n]),
atunci se sare la pozitiile i+a[i] si i-a[i], cu conditia ca ascestea sa fie din intervalul [1,n] si sa nu fi fost
vizitate anterior. Initial se pleaca de la pozitia 1;
*/
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fr[102];
//int main() {
// queue<int>coada;
// int n, a[102], i, varf,nr=0;
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> a[i];
// fr[1] = 1;
// if (1 + a[1] <= n) {
// coada.push(1 + a[1]);
// fr[1 + a[1]] = 1;
// }
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// //fr[varf] = 1;
// if (varf + a[varf] <= n && fr[varf + a[varf]] == 0) {
// coada.push(varf + a[varf]);
// fr[varf + a[varf]] = 1;
// }
// if (varf - a[varf] > 0 && fr[varf - a[varf]] == 0) {
// coada.push(varf - a[varf]);
// fr[varf - a[varf]] = 1;
// }
// }
// for (i = 1; i <= n; i++)
// if (fr[i] == 0) {
// nr++;
// fout << i << " ";
// }
// fout << nr;
//}
/*
8.3
Se da un vector a[] de lungime n si un numar natural k. Sa se determine numarul secventelor din sir care au cel
mult k elemente diferite.
*/
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fr[1002];
//int main() {
// int n, a[102], i,x, varf,k,rez=0,nr=0;
// queue<int> coada;
// fin >> n >> k;
// for (i = 1; i <= n; i++)
// fin >> a[i];
// for (i = 1; i <= n; i++) {
// coada.push(a[i]);
// fr[a[i]]++;
// if (fr[a[i]] == 1)
// nr++;
// while (nr > k) {
// varf = coada.front();
// coada.pop();
// fr[varf]--;
// if (fr[varf] == 0)
// nr--;
// }
// if (nr <= k && coada.size() > 0) {
// x = coada.size();
// rez = rez + x;
// }
// }
// fout << rez;
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int val, pasi;
//};
//int main() {
// int n, x, i, k;
// queue<Nod> coada;
// Nod varf, aux;
// fin >> n >> x;
// coada.push({ n,0 });
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// fout << varf.val << " "<<varf.pasi<<endl;
// if (varf.val == 1) {
// fout << varf.pasi;
// break;
// }
// for (k = 1; k <= 3; k++) {
// switch (k) {
// case 1:
// coada.push({ varf.val + x,varf.pasi + 1 });
// break;
// case 2:
// if (n % 2 == 0)
// coada.push({ varf.val / 2,varf.pasi + 1 });
// break;
// case 3:
// coada.push({ varf.val - 1,varf.pasi + 1 });
// break;
// }
// }
// }
//}
// 8.4
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int val, pasi;
//};
//int main() {
// int n, x, i, k;
// queue<Nod> coada;
// Nod varf, aux;
// fin >> n >> x;
// coada.push({ n,0 });
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// // fout << varf.val << " " << varf.pasi << endl;
// if (varf.val == 1) {
// fout << varf.pasi;
// break;
// }
// coada.push({ varf.val + x,varf.pasi + 1 });
// if (varf.val % 2 == 0)
// coada.push({ varf.val / 2,varf.pasi + 1 });
// coada.push({ varf.val - 1,varf.pasi + 1 });
// }
//}
//bool Div(queue<int> coada, int n) {
// int i, nr = 0;
// while (coada.empty() == false) {
// nr = nr * 10 + coada.front();
// coada.pop();
// }
// if (n % nr == 0)
// return true;
// return false;
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int c1, c2, c3, n, i, varf;
// queue<int> coada;
// fin >> n >> c1 >> c2 >> c3;
// if (c1 % n == 0 || c2 % n == 0 || c3 % n == 0 || c1 == 0 || c2 == 0 || c3 == 0)
// fout << 1;
// else {
//
// }
//}
//#include<fstream>
//#include<queue>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Vas {
// char nume;
// int vol;
//};
//struct Stare {
// Vas aa, bb;
// vector<char> cale;
//};
//int mat[102][102], a, b, c;
//Stare UmpleA(Stare prez);
//Stare UmpleB(Stare prez);
//Stare GolireA(Stare prez);
//Stare GolireB(Stare prez);
//Stare TornA_B(Stare prez);
//Stare TornB_A(Stare prez);
//void Afisare(Stare prez);
//int main() {
// Stare elem, varf, aux;
// queue<Stare> coada;
// fin >> a >> b >> c;
// elem.aa = { 'A',a };
// elem.bb = { 'B',0 };
// elem.cale.push_back('R');
// elem.cale.push_back('A');
// coada.push(elem);
//
// elem.cale.clear();
// elem.aa = { 'A',0 };
// elem.bb = { 'B',b };
// elem.cale.push_back('R');
// elem.cale.push_back('B');
// coada.push(elem);
//
// mat[0][0] = 1;
// mat[a][0] = 1;
// mat[0][b] = 1;
//
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// if (varf.aa.vol == c || varf.bb.vol == c) {
// Afisare(varf);
// break;
// }
// if (varf.aa.vol < a) {
// aux = UmpleA(varf);
// if (mat[aux.aa.vol][aux.bb.vol] == 0) {
// mat[aux.aa.vol][aux.bb.vol] = 1;
// coada.push(aux);
// }
// }
// if (varf.bb.vol < b) {
// aux = UmpleB(varf);
// if (mat[aux.aa.vol][aux.bb.vol] == 0) {
// mat[aux.aa.vol][aux.bb.vol] = 1;
// coada.push(aux);
// }
// }
// if (varf.aa.vol > 0) {
// aux =GolireA(varf);
// if (mat[aux.aa.vol][aux.bb.vol] == 0) {
// mat[aux.aa.vol][aux.bb.vol] = 1;
// coada.push(aux);
// }
// }
// if (varf.bb.vol > 0) {
// aux = GolireB(varf);
// if (mat[aux.aa.vol][aux.bb.vol] == 0) {
// mat[aux.aa.vol][aux.bb.vol] = 1;
// coada.push(aux);
// }
// }
// if (varf.aa.vol > 0 && varf.bb.vol < b) {
// aux = TornA_B(varf);
// if (mat[aux.aa.vol][aux.bb.vol] == 0) {
// mat[aux.aa.vol][aux.bb.vol] = 1;
// coada.push(aux);
// }
// }
// if (varf.bb.vol > 0 && varf.aa.vol < a) {
// aux = TornB_A(varf);
// if (mat[aux.aa.vol][aux.bb.vol] == 0) {
// mat[aux.aa.vol][aux.bb.vol] = 1;
// coada.push(aux);
// }
// }
// }
//}
//void Afisare(Stare prez) {
// int i;
// fout << prez.cale.size()/2 << endl;
// for (i = 0; i < prez.cale.size(); i+=2)
// fout << prez.cale[i] << " " << prez.cale[i + 1] << endl;
//}
//Stare UmpleA(Stare prez) {
// Stare urm;
// urm.aa.nume = 'A';
// urm.aa.vol = a;
// urm.bb.nume = 'B';
// urm.bb.vol = prez.bb.vol;
// urm.cale = prez.cale;
// urm.cale.push_back('R');
// urm.cale.push_back('A');
// return urm;
//}
//Stare UmpleB(Stare prez) {
// Stare urm;
// urm.aa.nume = 'A';
// urm.aa.vol = prez.aa.vol;
// urm.bb.nume = 'B';
// urm.bb.vol = b;
// urm.cale = prez.cale;
// urm.cale.push_back('R');
// urm.cale.push_back('b');
// return urm;
//}
//Stare GolireA(Stare prez) {
// Stare urm;
// urm.aa.nume = 'A';
// urm.aa.vol = 0;
// urm.bb.nume = 'B';
// urm.bb.vol = prez.bb.vol;
// urm.cale = prez.cale;
// urm.cale.push_back('A');
// urm.cale.push_back('C');
// return urm;
//}
//Stare GolireB(Stare prez) {
// Stare urm;
// urm.aa.nume = 'A';
// urm.aa.vol = prez.aa.vol;
// urm.bb.nume = 'B';
// urm.bb.vol = 0;
// urm.cale = prez.cale;
// urm.cale.push_back('B');
// urm.cale.push_back('C');
// return urm;
//}
//Stare TornA_B(Stare prez) {
// Stare urm;
// if (prez.aa.vol + prez.bb.vol <= b) {
// urm.aa.nume = 'A';
// urm.bb.nume = 'B';
// urm.aa.vol = 0;
// urm.bb.vol = prez.aa.vol + prez.bb.vol;
// }
// else {
// urm.bb.nume = 'B';
// urm.aa.nume = 'A';
// urm.bb.vol = b;
// urm.aa.vol = prez.aa.vol - b + prez.bb.vol;
// }
// urm.cale = prez.cale;
// urm.cale.push_back('A');
// urm.cale.push_back('B');
// return urm;
//}
//Stare TornB_A(Stare prez) {
// Stare urm;
// if (prez.aa.vol + prez.bb.vol <= a) {
// urm.aa.nume = 'A';
// urm.bb.nume = 'B';
// urm.aa.vol = prez.aa.vol + prez.bb.vol;
// urm.bb.vol = 0;
// }
// else {
// urm.bb.nume = 'B';
// urm.aa.nume = 'A';
// urm.bb.vol = prez.bb.vol - a + prez.aa.vol;
// urm.aa.vol = a;
// }
// urm.cale = prez.cale;
// urm.cale.push_back('B');
// urm.cale.push_back('A');
// return urm;
//}
//#include<fstream>
//#include<queue>
//#include<bitset>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//int a[1002], fr[1002], n,k;
//bitset<1001> b;
//int main() {
// int i, varf,x;
// queue<int> coada;
// fin >> n >> k;
// for (i = 1; i <= n; i++)
// fin >> a[i];
// for (i = 1; i <= k; i++) {
// fin >> x;
// b.set(x);
// }
// for (i = 1; i <= n; i++) {
// coada.push(a[i]);
// fr[a[i]]++;
//
// }
//}
// !!!!!!!!
//#include<fstream>
//#include<queue>
//#include<cmath>
//#include<bitset>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//int a[1002], fr[1002], n, k;
//bitset<1001> b;
//struct DDD {
// int val, index;
//};
//DDD firma[1501];
//int main() {
// int i, varf, x,contor=0,mini=INT_MAX,kk=0;
// queue<DDD> coada;
// fin >> n >> k;
// for (i = 1; i <= n; i++)
// fin >> a[i];
// for (i = 1; i <= k; i++) {
// fin >> x;
// b.set(x);
// }
// for (i = 1; i <= n; i++) {
// if (b[a[i]]) {
// coada.push({ a[i],i });
//
// if (fr[a[i]] == 0) {
// kk++;
//
// }
// fr[a[i]]++;
// }
// if (kk == k) {
// while (fr[coada.front().val] > 1) {
// fr[coada.front().val]--;
// coada.pop();
// }
// //mini = min(mini, coada.size() - 1);
// if (mini > i-coada.front().index)
// mini = i - coada.front().index;
// fr[coada.front().val]=0;
// coada.pop();
// kk--;
//
// }
//
// }
// fout << mini << " ";
//}
//#include<fstream>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n;
//vector<int> u;
//void Asezare(int val, int& poz) {
// int st, dr, mij;
//
// st = 0;
// dr = u.size()-1;
// while (st <= dr) {
// mij = (st + dr) / 2;
// if (u[mij] == val) {
// /* while (mij>0&&u[mij - 1] == u[mij]) {
// mij--;
// }
// u.insert(u.begin()+mij,val);*/
// poz = mij;
// break;
// }
// else {
// if (u[mij] > val)
// dr = mij - 1;
// else
// st = mij + 1;
//
// }
// }
//}
//int main() {
// int m, i, x,poz=0;
// fin >> n;
//
// for (i = 1; i <= n; i++) {
// fin >> x;
// u.push_back(x);
//
// }
// fin >> m;
// for (i = 1; i <= m; i++) {
// fin >> x;
// Asezare(x, poz);
// fout << poz << " ";
// }
//}
//#include<fstream>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n;
//vector<int> u;
///* while (mij>0&&u[mij - 1] == u[mij]) {
// mij--;
// }
// u.insert(u.begin()+mij,val);*/
//bool incadrare(int poz, int val) {
//
// if (poz == u.size() - 1) {
// if (val >= u[poz])
// return true;
// return false;
// }
// else {
// if (poz == 0) {
// if ( val<=u[0])
// return true;
// return false;
// }
// else {
// if (val >= u[poz] && val <= u[poz + 1])
// return true;
// return false;
// }
// }
//}
//
//void Asezare(int val, int& poz) {
// int st, dr, mij;
//
// st = 0;
// dr = u.size() - 1;
// while (st <= dr) {
// mij = (st + dr) / 2;
// if (u[mij] == val) {
// poz = mij;
// break;
// }
// else {
// if (incadrare(mij, val)) {
// poz = mij;
// //fout << u.size() << endl;
// break;
// }
// else {
// if (val > u[mij])
// st = mij + 1;
// else
// dr = mij - 1;
// }
// }
// }
//}
//int main() {
// int m, i, x, poz = 0;
// fin >> n;
//
// for (i = 1; i <= n; i++) {
// fin >> x;
// u.push_back(x);
//
// }
// fin >> m;
// for (i = 1; i <= m; i++) {
// fin >> x;
// Asezare(x, poz);
//
// while (poz>0&&u[poz - 1] == u[poz])
// poz--;
// fout << poz << " ";
// // fout << poz << " ";
// }
//}
//#include<fstream>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n;
//vector<int> u;
//
//bool incadrare(int poz, int val) {
//
// if (poz == u.size() - 1) {
// if (val > u[poz])
// return true;
// //return false;
// }
// else {
// if (poz == 0) {
// if (val < u[0])
// return true;
// // return false;
// }
// else {
// if (val > u[poz] && val < u[poz + 1])
// return true;
// //return false;
// }
// }
// return false;
//}
//
//void Asezare(int val, int& poz) {
// int st, dr, mij;
//
// st = 0;
// dr = u.size() - 1;
// while (st <= dr) {
// mij = (st + dr) / 2;
// if (u[mij] == val) {
// poz = mij;
// break;
// }
// else {
// if (incadrare(mij, val)) {
// // fout << 0;
// if(mij>0)
// poz = mij+1;
// else {
// if (mij == 0)
// poz = 0;
// else
// poz = u.size();
// }
// //fout << u.size() << endl;
// break;
// }
// else {
// if (val > u[mij])
// st = mij + 1;
// else
// dr = mij - 1;
// }
// }
// }
//}
//
//
////int main() {
//// fout << incadrare(7, 11);
////}
//
//
//int main() {
// int m, i, x, poz = 0,j;
// fin >> n;
//
// for (i = 1; i <= n; i++) {
// fin >> x;
// u.push_back(x);
//
// }
// fin >> m;
// for (i = 1; i <= m; i++) {
// fin >> x;
// Asezare(x, poz);
//
// while (poz > 0 && u[poz - 1] == u[poz]) {
// fout << poz;
// poz--;
//
// }
//
// //if (poz == u.size()) {
// // //u.insert(u.begin() + u.size()-1, x);
// // poz++;
// //}
// //else {
// u.insert(u.begin() + poz, x);
// //fout << 0;
// //}
//
// fout <<poz+1 << endl;
//
// }
// /*fout << endl << u.size() << endl;
// for (i = 0; i < u.size(); i++)
// fout << u[i] << " ";*/
//}
//#include<fstream>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n;
//vector<int> u;
//
//bool incadrare(int poz, int val) {
//
// if (poz == u.size() - 1) {
// if (val > u[poz])
// return true;
// //return false;
// }
// else {
// if (poz == 0) {
// if (val < u[0])
// return true;
// // return false;
// }
// else {
// if (val > u[poz] && val < u[poz + 1])
// return true;
// //return false;
// }
// }
// return false;
//}
//
//void Asezare(int val, int& poz) {
// int st, dr, mij;
//
// st = 0;
// dr = u.size() - 1;
// while (st <= dr) {
// mij = (st + dr) / 2;
// if (u[mij] == val) {
// poz = mij;
// break;
// }
// else {
// if (incadrare(mij, val)) {
// // fout << 0;
// if (mij > 0)
// poz = mij + 1;
// else {
// if (mij == 0)
// poz = 0;
// else
// poz = u.size();
// }
// //fout << u.size() << endl;
// break;
// }
// else {
// if (val > u[mij])
// st = mij + 1;
// else
// dr = mij - 1;
// }
// }
// }
//}
//
//
////int main() {
//// fout << incadrare(7, 11);
////}
//
//
//int main() {
// int m, i, x, poz = 0, j;
// fin >> n;
//
// for (i = 1; i <= n; i++) {
// fin >> x;
// u.push_back(x);
//
// }
// fin >> m;
// for (i = 1; i <= m; i++) {
// fin >> x;
// Asezare(x, poz);
// if (poz < u.size()) {
// while (poz > 0 && u[poz - 1] == u[poz]) {
// // fout << poz;
// poz--;
//
// }
// u.insert(u.begin() + poz, x);
// }
// else {
// u.insert(u.begin() + u.size(), x);
// }
// fout << poz + 1 << " ";
// /*fout << endl << u.size() << endl;
// for (i = 0; i < u.size(); i++)
// fout << u[i] << " ";*/
// }
// /*fout << endl << u.size() << endl;
// for (i = 0; i < u.size(); i++)
// fout << u[i] << " ";*/
//}
//#include<fstream>
//#include<queue>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n, m,b[10],fr[10], a[1002],aa[1002];
//bool gaseste(int val) {
// for (int i = 1; i <= m; i++)
// if (b[i] == val) {
// if (fr[i] == 0) {
// fr[i] = 1;
// return true;
// }
// else
// return false;
// }
// return false;
//}
//int main() {
// int i, j, x, nrdif = 0,st,dr,nraux,rez=0;
// queue<int> coada;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// fin >> a[i];
// aa[i] = a[i];
// }
// sort(aa + 1, aa + n + 1);
// i = 2;
// nrdif++;
// b[1] = aa[1];
// j = 0;
// /*for (i = 1; i <= n; i++)
// fout << aa[i] << " ";
// fout << endl;*/
// while (nrdif < m && i <= n) {
//
// if (aa[i] != aa[i - 1]) {
// nrdif++;
// b[nrdif] = aa[i];
// }
// i++;
// }
// /*fout << nrdif << endl;
// for (i = 1; i <= nrdif; i++)
// fout << b[i] << " ";*/
// for (i = 1; i < n; i++) {
// nraux = 0;
//
// for (j = 1; j <= 5; j++)
// fr[j] = 0;
// for (j = i; j <= n; j++) {
// //coada.push(a[j]);
// if (gaseste(a[j])) {
// nraux++;
// }
// if (nraux == m) {
// rez += n - j + 1;
// break;
// }
// }
// }
// fout << rez;
//}
//
//#include<iostream>
//using namespace std;
//int sc[102];
//int SumCif(int n) {
// int s = 0;
// while (n > 0) {
// s += n % 10;
// n /= 10;
// }
// return s;
//}
//int DouaNumere(int a[], int n) {
// int i,j,s,maxi=-1;
//
// for (i = 1; i <= n; i++)
// sc[i] = SumCif(a[i]);
// for (i = n; i > 1; i--) {
// j = i - 1;
// while (j>0&&sc[i] != sc[j])
// j--;
// if (sc[i] == sc[j]) {
// s = a[i] + a[j];
// if (s > maxi)
// maxi = s;
// }
// }
// return maxi;
//}
//int main() {
// int n, i, a[102];
// cin >> n;
// for (i = 1; i <= n; i++)
// cin >> a[i];
// cout << DouaNumere(a, n);
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, m;
// char c;
// fin >> n >> m;
// for (int i = 1; i <= n; i++,fout<<endl) {
// for (int j = 1; j <= m; j++) {
// fin >> c;
// switch (c) {
// case '0':fout << "-";
// break;
// case '1':fout << "R";
// break;
// case '2':fout << "G";
// break;
// case '3':fout << "B";
// break;
// }
// fout << " ";
// }
// }
//}
//
//#include<fstream>
//#include<iomanip>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col,pasi;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int n, m, mat[102][102], matt[102][102];
//queue<Nod> coada;
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//void Umple(Nod a,int val) {
// int k;
// Nod varf, aux;
// queue<Nod> coada;
// coada.push(a);
// matt[a.lin][a.col] = 0;
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (matt[aux.lin][aux.col] == val) {
// matt[aux.lin][aux.col] = 0;
// coada.push(aux);
// }
// }
// }
// }
//}
//int Explorare() {
// int k;
// Nod varf, aux;
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// /*fout << varf.lin << varf.col << " "<<mat[varf.lin][varf.col]<<endl;
// if (mat[varf.lin][varf.col] == -2) {
//
// if (varf.pasi > 1) {
//
// return varf.pasi;
//
// }
//
// }*/
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0||mat[aux.lin][aux.col]==-2) {
//
// aux.pasi = varf.pasi + 1;
// if (mat[aux.lin][aux.col] == -2&&aux.pasi>2)
// return aux.pasi;
// mat[aux.lin][aux.col] = -3;
// coada.push(aux);
// }
// }
// }
// }
//}
//int main() {
// int i, j,nr1=0,nr2=0,nr3=0;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> c;
// switch (c) {
// case '0':
// mat[i][j] = 0;
// break;
// case '1':
// mat[i][j] = -1;
// break;
// case '2':
// mat[i][j] = -2;
// break;
// case '3':
// mat[i][j] = -3;
// break;
// }
// matt[i][j] = mat[i][j];
// }
// }
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// if (matt[i][j] == -1) {
// Umple({ i,j,0 }, - 1);
// nr1++;
// }
// if (matt[i][j] == -2) {
// Umple({ i,j,0 }, - 2);
// nr2++;
// }
// if (matt[i][j] == -3) {
// Umple({ i,j,0 }, - 3);
// nr3++;
// }
// }
// }
// fout << nr1 << " " << nr2 << " " << nr3 << " ";
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++) {
// if (mat[i][j] == -1)
// coada.push({ i,j,0 });
// //fout <<setw(4)<< mat[i][j] << " ";
// }
// //fout << endl;
// fout<<Explorare()-1;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fra[10002], frb[10002], n, m;
//int main() {
// int i, x,minia=10000,minib=10000,mini,maxia=0,maxib=0,maxi,nra=0,nrb=0,st,dr;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// fin >> x;
// fra[x]++;
// if (x > maxia)
// maxia = x;
// if (x < minia)
// minia = x;
// }
// for (i = 1; i <= m; i++) {
// fin >> x;
// frb[x]++;
// if (x > maxib)
// maxib = x;
// if (x < minib)
// minib = x;
// }
// maxi = max(maxia, maxib);
// mini = min(minia, minib);
// for (i = mini; i <= maxi; i++) {
// if (fra[i] > 0 && frb[i] > 0) {
// st = i;
// break;
// }
// }
// for (i = maxi; i >= mini; i--) {
// if (fra[i] > 0 && frb[i] > 0) {
// dr = i;
// break;
// }
// }
// for (i = mini; i < st; i++) {
// if (fra[i] > 0)
// nra++;
// if (frb[i] > 0)
// nrb++;
// }
// for (i = dr + 1; i <= maxi; i++) {
// if (fra[i] > 0)
// nra++;
// if (frb[i] > 0)
// nrb++;
// }
// fout << st<< " "<<dr << " ";
// if (nra > nrb)
// fout << 1;
// else {
// if (nrb > nra)
// fout << 2;
// else
// fout << 0;
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int cmmmc(int a, int b) {
// int r, prod;
// prod = a * b;
// if (b > a)
// swap(a, b);
// while (b > 0) {
// r = a % b;
// a = b;
// b = r;
// }
// return prod/a;
//}
//
//int main() {
// int a, b;
// fin >> a >> b;
// fout << cmmmc(a, b);
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int cmmmc(int a, int b) {
// int r, prod;
// prod = a * b;
// if (b > a)
// swap(a, b);
// while (b > 0) {
// r = a % b;
// a = b;
// b = r;
// }
// return prod / a;
//}
//int CMMMC(int v[], int n) {
// int i, d;
// d = v[1];
// for (i = 2; i <= n; i++) {
// d = cmmmc(d, v[i]);
// }
// return d;
//}
//int main() {
// int v[20], n;
// fin >> n;
// for (int i = 1; i <= n; i++)
// fin >> v[i];
// fout << CMMMC(v, n);
//
//}
// TEOREMA
//
// URMA!!!!!!!!!!!!!!!!!!!!!!!!!!!
//#include<fstream>
//#include<queue>
//#include<iomanip>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//
//};
//vector<Nod> vec;
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], n, m, urma[102][102];
// bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//void Explorare(int &rez,int &coloana) {
// int k, i, j;
// Nod varf, aux;
// queue<Nod> coada;
// for (j = 1; j <= m; j++)
// if (mat[1][j] == 0) {
// coada.push({ 1,j,1 });
// mat[1][j] = -1;
// }
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// if (varf.lin == n) {
// rez = varf.val;
// coloana = varf.col;
// break;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0) {
// aux.val = varf.val + 1;
// mat[aux.lin][aux.col] = aux.val;
// urma[aux.lin][aux.col] = k;
// coada.push(aux);
// }
// }
// }
// }
//}
//int main() {
// int i, j, rez, coloana, val;
// char c;
// Nod varf, aux;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> c;
// if (c == 'O')
// mat[i][j] = 0;
// else
// mat[i][j] = -1;
// }
// }
// Explorare(rez,coloana);
// vec.push_back({ n,coloana });
// while (vec.back().lin != 1) {
// varf = vec.back();
// val = urma[varf.lin][varf.col];
// aux.lin = varf.lin - di[val];
// aux.col = varf.col - dj[val];
// vec.push_back(aux);
// }
// fout << rez << endl;
// for (i = vec.size() - 1; i >= 0; i--)
// fout << vec[i].lin << " " << vec[i].col << endl;
// fout << endl;
//
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= m; j++)
// fout << setw(3)<<mat[i][j] << " ";
//
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, raza,nume;
//};
//struct AAA {
// int lin, col;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = {0,1,0,-1 };
//int n, mat[102][102];
//Nod u[102];
//int dist(AAA a, AAA b) {
// return abs(a.lin - b.lin) + abs(a.col - b.col);
//}
//bool In_interior(AAA a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= n)
// return true;
// return false;
//}
//void Umple(Nod a) {
// int k;
// AAA aux, varf,b;
// queue<AAA> coada;
// aux.lin = a.lin;
// aux.col = a.col;
// coada.push(aux);
// mat[aux.lin][aux.col] = a.nume;
// while (coada.empty() == false) {
// varf = coada.front();
// coada.pop();
// for (k = 0; k < 4; k++) {
// b.lin = varf.lin + di[k];
// b.col = varf.col + dj[k];
// if (In_interior(b)&&dist(b,aux)<a.raza&&mat[b.lin][b.col]!=a.nume) {
// mat[b.lin][b.col] = a.nume;
// coada.push(b);
// }
// }
// }
//}
//int main() {
// int p, i, lin, col, raza;
// fin >> n >> p;
// for (i = 1; i <= p; i++) {
// fin >> u[i].lin >> u[i].col >> u[i].raza;
// u[i].nume = i;
// }
// for (i = 1; i <= p; i++) {
// Umple(u[i]);
// }
// for (i = 1; i <= n; i++,fout<<endl)
// for (int j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//}
// !!!!!!
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, raza, nume;
//};
//struct AAA {
// int lin, col;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int n, mat[102][102];
//Nod u[102];
//int dist(AAA a, AAA b) {
// return abs(a.lin - b.lin) + abs(a.col - b.col);
//}
//bool In_interior(AAA a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= n)
// return true;
// return false;
//}
//void Umple(Nod a) {
// int dim, i, j;
// dim = a.raza - 1;
// for (i = 0; i <= dim; i++)
// for (j = i; j <= dim; j++) {
// if (a.lin - i >= 1 && a.col + j - i <= n)
// mat[a.lin - i][a.col + j - i] = a.nume;
//
// if (a.lin + i <= n && a.col + j - 1 <= n)
// mat[a.lin + i][a.col + j - i] = a.nume;
//
// if (a.lin - i >= 1 && a.col - j + i >= 1)
// mat[a.lin - i][a.col - j + i] = a.nume;
//
// if (a.lin + i <= n && a.col - j + i >= 1)
// mat[a.lin + i][a.col - j + i] = a.nume;
// }
//}
//int main() {
// int p, i, lin, col, raza;
// fin >> n >> p;
// for (i = 1; i <= p; i++) {
// fin >> u[i].lin >> u[i].col >> u[i].raza;
// u[i].nume = i;
// }
// for (i = 1; i <= p; i++) {
// Umple(u[i]);
// }
// for (i = 1; i <= n; i++, fout << endl)
// for (int j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, raza, nume;
//};
//struct AAA {
// int lin, col;
//};
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int n, mat[102][102];
//Nod u[102];
//int dist(AAA a, AAA b) {
// return abs(a.lin - b.lin) + abs(a.col - b.col);
//}
//bool In_interior(AAA a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= n)
// return true;
// return false;
//}
//void Umple(Nod centru,Nod curent) {
// int k;
// Nod aux;
// mat[curent.lin][curent.col] = centru.nume;
// for (k = 0; k< 4; k++) {
// aux.lin = curent.lin + di[k];
// aux.col = curent.col + dj[k];
// if (In_interior({ aux.lin,aux.col }) && mat[aux.lin][aux.col] != centru.nume && dist({ centru.lin,centru.col }, { aux.lin,aux.col })<centru.raza){
// Umple(centru, aux);
// }
// }
//
//
//}
//int main() {
// int p, i, lin, col, raza;
// fin >> n >> p;
// for (i = 1; i <= p; i++) {
// fin >> u[i].lin >> u[i].col >> u[i].raza;
// u[i].nume = i;
// }
// for (i = 1; i <= p; i++) {
// Umple(u[i],u[i]);
// }
// for (i = 1; i <= n; i++, fout << endl)
// for (int j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col;
//};
//int n, mat[102][102];
//int Ataca(int lin, int col) {
// int i, j, nr = 0;
// for (i = col + 1; i <= n; i++)
// if (mat[lin][i] == 1) {
// nr++;
// break;
// }
// for (i = col - 1; i >= 1; i--)
// if (mat[lin][i] == 1) {
// nr++;
// break;
// }
// for (i = lin + 1; i <= n; i++)
// if (mat[i][col] == 1) {
// nr++;
// break;
// }
// for (i = lin - 1; i >= 1; i--)
// if (mat[i][col] == 1) {
// nr++;
// break;
// }
// for (i = lin + 1, j = col + 1; i <= n, j <= n; i++, j++)
// if (mat[i][j] == 1) {
// nr++;
// break;
// }
// for (i = lin + 1, j = col - 1; i <= n, j >= 1 ; i++, j--)
// if (mat[i][j] == 1) {
// nr++;
// break;
// }
// for (i = lin - 1, j = col + 1; i >= 1, j <=n; i--, j++)
// if (mat[i][j] == 1) {
// nr++;
// break;
// }
// for (i = lin - 1, j = col - 1; i >= 1, j >= 1; i--, j--)
// if (mat[i][j] == 1) {
// nr++;
// break;
// }
// return nr;
//}
//int main() {
// int i, j, lin,m, col,maxi=0,nr=0,x;
// Nod reg[102];
// fin >> n >> m;
// for (i = 1; i <= m; i++) {
// fin >> reg[i].lin >> reg[i].col;
// mat[reg[i].lin][reg[i].col] = 1;
// }
// for (i = 1; i <= m; i++) {
// x = Ataca(reg[i].lin,reg[i].col);
// if (x == maxi) {
// nr++;
// // fout << reg[i].lin << " " << reg[i].col << endl;
// }
// if (x > maxi) {
// nr = 1;
// maxi = x;
// }
// }
// fout << maxi << " " << nr;
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("data.in");
//ofstream fout("date.out");
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[1002][1002], n, m;
//struct Nod {
// int lin, col, pasi;
//};
//bool In_interior(Nod a) {
// if (a.lin <= n && a.lin >= 1 && a.col <= m && a.col >= 1)
// return true;
// return false;
//}
//int Explorare() {
// int i, j, k;
// queue <Nod> coada;
// Nod aux, varf;
//
// for (j = 1; j <= m; j++) {
// if (mat[1][j] == 0) {
// aux.lin = 1;
// aux.col = j;
// aux.pasi = 1;
// coada.push(aux);
// mat[1][j] = 1;
// }
// }
//
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// if (varf.lin == n) {
// return varf.pasi;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0) {
// aux.pasi = varf.pasi + 1;
// mat[aux.lin][aux.col] = 1;
// coada.push(aux);
// }
// }
// }
// }
//}
//int main() {
// int i, j;
// char c;
// fin >> n >> m;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++) {
// fin >> c;
// if (c == 'O')
// mat[i][j] == 0;
// else
// mat[i][j] = 1;
// }
// for(i=1;i<=n;i++)
// fout << Explorare();
//
//}
//#include<fstream>
//#include<queue>
//#include<iomanip>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//
//};
//vector<Nod> vec;
//const int di[4] = { -1,0,1,0 }, dj[4] = { 0,1,0,-1 };
//int mat[102][102], n, m, urma[102][102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//void Explorare(int& rez, int& coloana) {
// int k, i, j;
// Nod varf, aux;
// queue<Nod> coada;
// for (j = 1; j <= m; j++)
// if (mat[1][j] == 0) {
// coada.push({ 1,j,1 });
// mat[1][j] = -1;
// }
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// if (varf.lin == n) {
// rez = varf.val;
// coloana = varf.col;
// break;
// }
// for (k = 0; k < 4; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0) {
// aux.val = varf.val + 1;
// mat[aux.lin][aux.col] = aux.val;
// urma[aux.lin][aux.col] = k;
// coada.push(aux);
// }
// }
// }
// }
//}
//int main() {
// int i, j, rez, coloana, val;
// char c;
// Nod varf, aux;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> c;
// if (c == 'O')
// mat[i][j] = 0;
// else
// mat[i][j] = -1;
// }
// }
// Explorare(rez, coloana);
// vec.push_back({ n,coloana });
// while (vec.back().lin != 1) {
// varf = vec.back();
// val = urma[varf.lin][varf.col];
// aux.lin = varf.lin - di[val];
// aux.col = varf.col - dj[val];
// vec.push_back(aux);
// }
// fout << rez << endl;
// for (i = vec.size() - 1; i >= 0; i--)
// fout << vec[i].lin << " " << vec[i].col << endl;
// fout << endl;
//
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= m; j++)
// fout << setw(3) << mat[i][j] << " ";
//
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n, u[102], vmax, rez, dom_max;
//int main() {
// int i, cat,rest,dif,j;
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// fin >> vmax;
// i = 1;
// //fout << vmax;
// while (i<=n&&u[i] < vmax)
// i++;
// n = i - 1;
// //fout << n;
// rez = u[2] - 1;
// dom_max = rez;
// u[n + 1] = vmax + 1;
// for (i = 2; i <= n; i++) {
// if (dom_max <= u[i + 1] - 1) {
// dif = u[i + 1] - 1 - dom_max;
// cat = dif / u[i];
// rest = dif % u[i];
// if (rest != 0)
// cat++;
// rez += cat;
// dom_max = dom_max + cat * u[i];
// }
// }
// fout << rez;
// //fout << 1;
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct DDD {
// int lin, col, raza, stare, nume;
//};
//struct Nod {
// int lin, col, stare;
//};
//Nod nava, planeta;
//DDD pulsar[102];
//int n, p, a[102][102][62], vec[102],nr_etaje;
//int cmmmc(int x, int y) {
// int prod = x * y;
// if (x < y)
// swap(x, y);
// int r;
// while (y > 0) {
// r = x % y;
// x = y;
// y = r;
// }
//
// return prod/x;
//}
//int CMMMC() {
// int i, rez;
// rez = vec[1];
// for (i = 2; i <= p; i++)
// rez = cmmmc(rez, vec[i]);
// return rez;
//}
//void Umple(DDD A,int dim,int etaj) {
// int i, j;
//
// for (i = 0; i <= dim; i++)
// for (j = i; j <= dim; j++) {
// if (A.lin - i >= 1 && A.col + j - i <= n)
// a[A.lin - i][A.col + j - i][etaj] = A.nume;
//
// if (A.lin + i <= n && A.col + j - i <= n)
// a[A.lin + i][A.col + j - i][etaj] = A.nume;
//
// if (A.lin - i >= 1 && A.col - j + i >= 1)
// a[A.lin - i][A.col - j + i][etaj] = A.nume;
//
// if (A.lin + i <= n && A.col - j + i >= 1)
// a[A.lin + i][A.col - j + i][etaj] = A.nume;
// }
//}
//int main() {
// int cerinta, n, i, j,dim;
// fin >> cerinta >> n >> p;
// for (i = 1; i <= p; i++) {
// fin >> pulsar[i].lin >> pulsar[i].col >> pulsar[i].raza >> pulsar[i].stare;
// pulsar[i].nume = i;
// }
// fin >> nava.lin >> nava.col >> planeta.lin >> planeta.col;
// nava.stare = 0;
// planeta.stare = 0;
// for (i = 1; i <= p; i++)
// vec[i] = pulsar[i].raza;
// nr_etaje = CMMMC();
// //fout << nr_etaje;
// for (int ii = 0; ii < nr_etaje; ii++) {
// for (int k = 1; k <= p; k++) {
// dim = (pulsar[k].stare + ii) % nr_etaje % pulsar[k].raza;
// Umple(pulsar[k], dim, ii);
// }
// }
// /*for (int ii = 0; ii <= 2; ii++, fout << endl)
// for (i = 1; i <= n; i++,fout<<endl)
// for (j = 1; j <= n; j++)
// fout << a[i][j][ii] << " ";*/
// if (cerinta == 1) {
// int nr_act, maxi_nr = 0;
// for (int k = 0; k < nr_etaje; k++) {
// nr_act = 0;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// if (a[i][j][k] == 1)
// nr_act++;
// if (nr_act > maxi_nr)
// maxi_nr = nr_act;
// }
// fout << maxi_nr;
// }
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct DDD {
// int lin, col, raza, stare, nume;
//};
//struct Nod {
// int lin, col, stare;
//};
//const int di[7] = { -1,0,1,0 ,0 }, dj[7] = { 0,1,0,-1 ,0 };
//Nod nava, planeta;
//DDD pulsar[102];
//int n, p, a[102][102][62], vec[102], nr_etaje,vizit[102][102][62],dist[102][102][62];
//int cmmmc(int x, int y) {
// int prod = x * y;
// if (x < y)
// swap(x, y);
// int r;
// while (y > 0) {
// r = x % y;
// x = y;
// y = r;
// }
//
// return prod / x;
//}
//int CMMMC() {
// int i, rez;
// rez = vec[1];
// for (i = 2; i <= p; i++)
// rez = cmmmc(rez, vec[i]);
// return rez;
//}
//void Umple(DDD A, int dim, int etaj) {
// int i, j;
//
//
//}
//bool In_interior(int lin, int col) {
// if (lin >= 1 && lin <= n && col >= 1 && col <= n)
// return true;
// return false;
//}
//int main() {
// int cerinta, i, j, dim;
// fin >> cerinta >> n >> p;
// for (i = 1; i <= p; i++) {
// fin >> pulsar[i].lin >> pulsar[i].col >> pulsar[i].raza >> pulsar[i].stare;
// pulsar[i].nume = i;
// }
// fin >> nava.lin >> nava.col >> planeta.lin >> planeta.col;
// nava.stare = 0;
// planeta.stare = 0;
// for (i = 1; i <= p; i++)
// vec[i] = pulsar[i].raza;
// nr_etaje = CMMMC();
// //fout << nr_etaje;
// for (int ii = 0; ii < nr_etaje; ii++) {
// for (int k = 1; k <= p; k++) {
// dim = ((pulsar[k].stare + ii) % nr_etaje) % pulsar[k].raza;
// for (i = 0; i <= dim; i++)
// for (j = i; j <= dim; j++) {
//
//
// if (pulsar[k].lin + i <= n && pulsar[k].col + j - i <= n)
// a[pulsar[k].lin + i][pulsar[k].col + j - i][ii] = pulsar[k].nume;
//
// if (pulsar[k].lin + i <= n && pulsar[k].col - j + i >= 1)
// a[pulsar[k].lin + i][pulsar[k].col - j + i][ii] = pulsar[k].nume;
//
// if (pulsar[k].lin - i >= 1 && pulsar[k].col + j - i <= n)
// a[pulsar[k].lin - i][pulsar[k].col + j - i][ii] = pulsar[k].nume;
//
// if (pulsar[k].lin - i >= 1 && pulsar[k].col - j + i >= 1)
// a[pulsar[k].lin - i][pulsar[k].col - j + i][ii] = pulsar[k].nume;
//
//
// }
// //Umple(pulsar[k], dim, ii);
// }
// }
// //for (int ii = 0; ii <= 2; ii++, fout << endl)
// // for (i = 1; i <= n; i++,fout<<endl)
// // for (j = 1; j <= n; j++)
// // fout << a[i][j][ii] << " ";
// if (cerinta == 1) {
// int nr_act, maxi_nr = 0;
// for (int k = 0; k < nr_etaje; k++) {
// nr_act = 0;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// if (a[i][j][k] != 0)
// nr_act++;
// if (nr_act > maxi_nr)
// maxi_nr = nr_act;
// }
// fout << maxi_nr;
// }
// else {
// int k, ii;
// int mini = INT_MAX;
// for ( k = 0; k < nr_etaje; k++)
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// dist[i][j][k] = INT_MAX;
//
// queue<Nod> coada;
// Nod varf, aux;
// coada.push(nava);
// vizit[nava.lin][nava.col][nava.stare] = 1;
// dist[nava.lin][nava.col][nava.stare] = 1;
//
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// for ( k = 0; k < 5; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// aux.stare = (varf.stare + 1)%nr_etaje;
//
// if (In_interior(aux.lin, aux.col) && a[aux.lin][aux.col][aux.stare]==0 && vizit[aux.lin][aux.col][aux.stare]==0) {
// vizit[aux.lin][aux.col][aux.stare] = 1;
// coada.push(aux);
// dist[aux.lin][aux.col][aux.stare] = dist[varf.lin][varf.col][varf.stare] + 1;
// }
// }
// }
// /*for (ii = 0; ii <= 2; ii++, fout << endl)
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= n; j++)
// fout << dist[i][j][ii] << " ";*/
// for (int ii = 0; ii < nr_etaje; ii++) {
// if (dist[planeta.lin][planeta.col][ii] < mini)
// //fout << dist[planeta.lin][planeta.col][ii] << " ";
// mini = dist[planeta.lin][planeta.col][ii];
// }
// fout << mini-1;
// }
//}
//#include<fstream>
//#include<queue>
//#include<string.h>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int x, y;
// char c, d;
// fin >> x >> c >> y >> d;
// fout << x << " " << c<<endl<<y<<" "<<d;
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//int n, m, mat[102][102], urma[102][102];
//void Explorare() {
//
//}
//int main() {
// int i, j,x[6];
// char y,c[6];
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> y;
// if (y == 'X')
// mat[i][j] = 1;
// else
// mat[i][j] = 0;
// }
// }
//
//
//
//}
//#include<fstream>
//#include<queue>
//#include<string.h>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col, val;
//};
//
//int n, m, mat[102][102], urma[102][102], di[6] = { -1,0,1,0 }, dj[6] = { 0,1,0,-1 };
//bool In_interior(Nod x) {
// if (x.lin >= 1 && x.lin <= n && x.col >= 1 && x.col <= m)
// return true;
// return false;
//}
//int Explorare(int &coloana) {
// Nod varf, aux;
// queue<Nod> coada;
// int k, j;
// for (j = 1; j <= m; j++)
// if (mat[1][j] == 0) {
// coada.push({ 1,j,1 });
// mat[1][j] = 1;
// }
// while (coada.empty() == 0) {
// varf = coada.front();
// coada.pop();
// if (varf.lin == n) {
// coloana = varf.col;
// return varf.val;
// }
// for (k = 0; k < 6; k++) {
// aux.lin = varf.lin + di[k];
// aux.col = varf.col + dj[k];
// if (In_interior(aux)) {
// if (mat[aux.lin][aux.col] == 0) {
// mat[aux.lin][aux.col] = 1;
// urma[aux.lin][aux.col] = k;
// aux.val = varf.val + 1;
// coada.push(aux);
// }
// }
// }
// }
//
//}
//int main() {
// int i, j, x[6],linie,coloana,val;
// char y, c[6];
// vector<Nod> vec;
// Nod aux;
// fin >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> y;
// if (y == 'X')
// mat[i][j] = 1;
// else
// mat[i][j] = 0;
// }
// }
// fin >> x[1] >> c[1] >> x[2] >> c[2] >> x[3] >> c[3] >> x[4] >> c[4];
// for (i = 1; i <= 4; i++) {
// linie = 0;
// coloana = 0;
// if (c[i] == 'N')
// linie -= x[i];
// if(c[i]=='S')
// linie+=x[i];
// if (c[i] == 'E')
// coloana += x[i];
// if (c[i] == 'V')
// coloana -= x[i];
// switch (i) {
// case 1:
// di[4] = linie;
// break;
// case 2:
// dj[4] = coloana;
// break;
// case 3:
// di[5] = linie;
// break;
// case 4:
// dj[5] = coloana;
// break;
// }
// }
// /*for (i = 0; i < 6; i++)
// fout << di[i] << " " << dj[i] << endl;*/
// fout << Explorare(coloana) << endl;
// vec.push_back({ n,coloana,0 });
// while (vec.back().lin != 1) {
// val = urma[vec.back().lin][vec.back().col];
// aux.lin = vec.back().lin - di[val];
// aux.col = vec.back().col - dj[val];
// vec.push_back(aux);
// }
// for(i=vec.size()-1;i>=0;i--)
// fout << vec[i].lin << " " << vec[i].col << '\n';
//}
////////////////////////////////////////////////////////////////////////////////////////////////////////////
// STIVA
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int u[1002], n, i, j;
// bool h;
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// fout << 0 << " ";
// for (i = 2; i <= n; i++) {
// j = i - 1;
// h = false;
// while (j >= 1) {
// if (u[j] < u[i]) {
// fout << u[j] << " ";
// h = true;
// break;
// }
//
// j--;
// }
// if (h == false)
// fout << 0 << " ";
// }
//}
//
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int u[102], n, vf;
//int main() {
// int i, x;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// while (vf > 0 && u[vf] > x)
// vf--;
// if (vf == 0)
// fout << 0 << " ";
// else
// fout << u[vf] << " ";
// u[++vf] = x;
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int u[102], n, vf, k;
//int main() {
// int i, x;
// fin >> n >> k;
// for (i = 1; i <= n; i++) {
// fin >> x;
// while (vf > 0 && u[vf] < x && k>0) {
// vf--;
// k--;
// }
// u[++vf] = x;
// }
// while (vf > 0 && k > 0) {
// vf--;
// k--;
// }
// for (i = 1; i <= vf; i++)
// fout << u[i] << " ";
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int u[102], n, vf, k;
//int main() {
// int i, x;
// fin >> n >> k;
// for (i = 1; i <= n; i++) {
// fin >> x;
// while (vf > 0 && u[vf] < x && k>0) {
// vf--;
// k--;
// }
// u[++vf] = x;
// }
// while (vf > 0 && k > 0) {
// vf--;
// k--;
// }
// for (i = 1; i <= vf; i++)
// fout << u[i] << " ";
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int i, n, x, varf;
// stack<int> a, b, c;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// a.push(x);
// }
// while (a.empty() == false) {
// b.push(a.top());
// a.pop();
// }
// while (b.empty() == false) {
// varf = b.top();
// b.pop();
// if (varf % 2 == 0)
// a.push(varf);
// else
// c.push(varf);
// }
// while (a.empty() == false) {
// b.push(a.top());
// a.pop();
// }
// while (b.empty() == false) {
// fout << b.top()<<" ";
// b.pop();
// }
// fout << endl;
// while (c.empty() == false) {
// b.push(c.top());
// c.pop();
// }
// while (b.empty() == false) {
// fout << b.top() << " ";
// b.pop();
// }
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//int main() {
// int n, x, i, vf = 0;
// stack<int> stiva;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// while (stiva.empty() == false && stiva.top() > x)
// stiva.pop();
// if (stiva.empty() == true)
// fout << 0 << " ";
// else
// fout << stiva.top() << " ";
// stiva.push(x);
// }
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//int main() {
// int n, x, i, vf = 0, k, vec;
// stack<int> stiva, q;
// fin >> n >> k;
// for (i = 1; i <= n; i++) {
// fin >> x;
// while (stiva.empty() == false && stiva.top() < x && k > 0) {
// stiva.pop();
// k--;
// }
//
// stiva.push(x);
// }
// while (stiva.empty() == 0 && k > 0) {
// stiva.pop();
// k--;
// }
// while (stiva.empty() == false) {
// q.push(stiva.top());
// stiva.pop();
// }
// while (q.empty() == 0) {
// fout << q.top() << " ";
// q.pop();
// }
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//int main() {
// int n, x, i, vf = 0, k, vec;
// stack<int> stiva, q;
// fin >> n;
// while (n > 0) {
// stiva.push(n % 2);
// n /= 2;
// }
// while (stiva.empty() == 0) {
// fout << stiva.top();
// stiva.pop();
// }
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool Verific(int a, int b, int c) {
// if ((a % b == 0 || b % a == 0) && (c % b == 0 || b % c == 0))
// return true;
// return false;
//}
//int main() {
// int n, i, x, stiva[102], vf = 0;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// stiva[++vf] = x;
// if (vf >= 3 && Verific(stiva[vf - 2], stiva[vf - 1], stiva[vf]))
// vf -= 3;
// //fout << vf << endl;
// }
// if (vf > 0) {
// for (i = 1; i <= vf; i++)
// fout << stiva[i] << " ";
// }
// else
// fout << "Merry Christmas";
//}
//#include<fstream>
//#include<stack>
//#include<string.h>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// stack<int>stiva;
// int x, i, n;
// char s[10], cuv1[6] = "push", cuv2[6] = "pop";
// fin >> n;
// for (i = 1; i <= n; i++) {
//
// fin >> s;
// /* fout << s << endl;*/
// if (strcmp(s,cuv1)==0) {
// fin >> x;
// stiva.push(x);
// }
// else {
// if (strcmp(s,cuv2)==0) {
// if (stiva.empty() == false)
// stiva.pop();
//
// }
// else
// if (stiva.empty() == false)
// fout << stiva.top()<<endl;
// }
// //fout << stiva.top() << endl;
// }
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct AAA {
// int ind, val;
//};
//AAA u[102];
//int main() {
// stack<AAA>stiva;
// AAA varf, aux;
// int i, n, x;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// u[i].ind = i;
// u[i].val = x;
// }
// stiva.push(u[1]);
// for (i = 2; i <= n; i++) {
// while (stiva.empty() == false && stiva.top().val < u[i].val) {
// varf = stiva.top();
// stiva.pop();
// u[varf.ind].val = u[i].val;
// }
// stiva.push(u[i]);
// }
// while (stiva.empty() == false) {
// varf = stiva.top();
// u[varf.ind].val = -1;
// stiva.pop();
// }
// for (i = 1; i <= n; i++)
// fout << u[i].val << " ";
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct AAA {
// int ind, val;
//};
//AAA u[102];
//int main() {
// stack<AAA>stiva;
// AAA varf, aux;
// int i, n, x;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// u[i].ind = i;
// u[i].val = x;
// }
// stiva.push(u[1]);
// for (i = 2; i <= n; i++) {
// if (stiva.empty() == true || stiva.top().val >= u[i].val) {
// stiva.push(u[i]);
// }
// else {
// while (stiva.empty() == false && stiva.top().val < u[i].val) {
// varf = stiva.top();
// stiva.pop();
// u[varf.ind].val = u[i].val;
// }
// stiva.push(u[i]);
// }
// }
// while (stiva.empty() == false) {
// varf = stiva.top();
// u[varf.ind].val = -1;
// stiva.pop();
// }
// for (i = 1; i <= n; i++)
// fout << u[i].val << " ";
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct AAA {
// int ind, val;
//};
//AAA u[102];
//int main() {
//
// AAA varf, aux;
// int i, n, x,vf=0;
// AAA stiva[102];
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// u[i].ind = i;
// u[i].val = x;
// }
// stiva[++vf] = u[1];
// for (i = 2; i <= n; i++) {
// if (vf==0 || stiva[vf].val >= u[i].val) {
// stiva[++vf] = u[i];
// }
// else {
// while (vf>0 && stiva[vf].val < u[i].val) {
// varf = stiva[vf];
// vf--;
// u[varf.ind].val = u[i].val;
// }
// stiva[++vf] = u[i];
// }
// }
// while (vf>0) {
// varf = stiva[vf];
// u[varf.ind].val = -1;
// vf--;
// }
// for (i = 1; i <= n; i++)
// fout << u[i].val << " ";
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool Intersectie(pair<int, int> A, pair<int, int> B) {
// if (A.second<B.first || A.first>B.second)
// return false;
// return true;
//}
//pair<int, int> Reuniune(pair<int, int> A, pair<int, int> B) {
// return { min(A.first,B.first),max(A.second,B.second) };
//}
//pair<int, int> u[102];
//int main() {
// int n, i;
// stack<pair<int, int>> stiva;
// pair<int, int> varf;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i].first >> u[i].second;
// }
// for (i = 1; i <= n; i++) {
// while (stiva.empty() == false&& Intersectie(stiva.top(),u[i])) {
// u[i] = Reuniune(u[i], stiva.top());
// stiva.pop();
// }
// stiva.push(u[i]);
// }
// fout << stiva.size();
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, j, m;
// char s[102];
// stack <char> stiva;
// fin >> n;
// fin.get();
// for (i = 1; i <= n; i++) {
// fin.getline(s, 100);
//
// for (j = 0; j< strlen(s); j++) {
// if (s[j] == '(')
// stiva.push(s[j]);
// else
// if(stiva.empty()==false)
// stiva.pop();
// }
// if (stiva.empty() == true)
// fout << 1 << endl;
// else
// fout << 0 << endl;
//
// while (stiva.empty() == false)
// stiva.pop();
// }
//}
//#include<fstream>
//#include<stack>
//#include<string.h>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, j, m;
// char s[302];
// bool h;
// stack <char> stiva;
// fin >> n;
// fin.get();
// for (i = 1; i <= n; i++) {
// fin.getline(s, 260);
// h = false;
// for (j = 0; j < strlen(s); j++) {
// if (s[j] == '('||s[j]=='[')
// stiva.push(s[j]);
// else {
// if (stiva.empty() == false)
// stiva.pop();
// else {
// fout << 0 << endl;
// h = true;
// break;
// }
// }
// }
// if (h == false) {
// if (stiva.empty() == true)
// fout << 1 << endl;
// else
// fout << 0 << endl;
// }
//
// while (stiva.empty() == false)
// stiva.pop();
// }
//}
//#include<fstream>
//#include<stack>
//#include<string.h>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool Corect(char s[]) {
// stack<char> stiva;
// int i, j, m;
// m = strlen(s);
// for (i = 0; i < m; i++) {
// if (s[i] == ')') {
// if (stiva.empty() == true)
// return false;
// else {
// if (stiva.top() == '(')
// stiva.pop();
// else
// return false;
// }
// }
// else {
// if (s[i] == ']') {
// if (stiva.empty() == true)
// return false;
// else {
// if (stiva.top() == '[')
// stiva.pop();
// else
// return false;
// }
// }
// else {
// stiva.push(s[i]);
// }
// }
// }
// if (stiva.empty() == true)
// return true;
// return false;
//}
//int main() {
// int n, i, j, m;
// char s[302];
// bool h;
// stack <char> stiva;
// fin >> n;
// fin.get();
// for (i = 1; i <= n; i++) {
// fin.getline(s, 260);
// h = false;
// if (Corect(s))
// fout << 1;
// else
// fout << 0;
// fout << '\n';
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// char stiva[102];
// char s[102];
// int n, i, varf = 0, maxi = 0;
// fin.getline(s, 100);
// n = strlen(s);
// for (i = 0; i < n; i++) {
// //fout << s[i] << " ";
// if (s[i] == '(') {
// stiva[++varf] = s[i];
//
// }
// else {
//
// if (maxi < varf)
// maxi = varf;
// varf--;
//
// }
// }
// fout << maxi;
//}
//#include<fstream>
//#include<stack>
//#include<string.h>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// char s[302], stiva[301];
// int n, i, varf = 0;
// fin.getline(s, 290);
// n = strlen(s);
// for (i = 0; i < n; i++) {
// if (s[i] == '(')
// stiva[++varf] = s[i];
// else {
// fout << varf << " ";
// varf--;
// }
// }
//
//}
//#include<fstream>
//#include<stack>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fra[102], frb[102];
//int main() {
// int varf = 0, n, u[102], i, j;
// stack<int> A, B, C;
// vector<char> rez;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i];
// fra[u[i]] = 1;
// A.push(u[i]);
// }
// for (i = 1; i <= n; i++) {
// if (fra[i] == 1) {
// while (A.top() != i) {
// B.push(A.top());
// frb[A.top()] = 1;
// fra[A.top()] = 0;
// A.pop();
// rez.push_back('A');
// rez.push_back('B');
// //rez.push_back('C');
// }
// C.push(A.top());
// A.pop();
// rez.push_back('A');
// rez.push_back('C');
// }
// if (frb[i] == 1) {
// while (B.top() != i) {
// A.push(B.top());
// fra[B.top()] = 1;
// frb[B.top()] = 0;
// B.pop();
// rez.push_back('B');
// rez.push_back('A');
// }
// C.push(B.top());
// B.pop();
// rez.push_back('B');
// rez.push_back('C');
//
// }
// }
// fout << rez.size() / 2 << endl;
// for (i = 0; i < rez.size()-1; i+=2) {
// fout << rez[i] << " " << rez[i + 1] << '\n';
// }
//}
//#include<fstream>
//#include<stack>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int stiva[102], n, varf = 0, i, j,nr=0;
// char s[102];
// fin.getline(s, 100);
// n = strlen(s);
// for (i = 0; i < n; i++) {
// if (s[i] == '(') {
// nr++;
// stiva[++varf] = nr;
// }
// else {
// fout << stiva[varf] << " ";
// varf--;
// }
// }
//}
//#include<fstream>
//#include<stack>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int i, n, k, vf = 0;
// char s[302], stiva[102];
// fin >> k;
// fin >> s;
// for (i = 0; i < strlen(s); i++) {
// while (vf > 0 && stiva[vf] > s[i] && k>0) {
// vf--;
// k--;
// }
// stiva[++vf] = s[i];
// }
// while (vf > 0 && k > 0) {
// vf--;
// k--;
// }
// for (i = 1; i <= vf; i++)
// fout << stiva[i];
//}
//#include<fstream>
//#include<stack>
//#include<string>
//#include<sstream> // pentru spargere, utilizarea istringstream
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// string s;
// int n, i, j, nr = 0;
// stack<string> stiva;
// fin >> n;
// fin.get();
// for (i = 1; i <= n; i++) {
// getline(fin, s);
// nr = 0;
// istringstream Sparge(s);
// for (string w; Sparge >> w;) {
// if (stiva.empty() == true) {
// if (w == "else") {
// nr++;
// stiva.push("if");
// }
// else
// stiva.push(w);
// }
// else {
// if (w == "else")
// stiva.pop();
// else
// stiva.push(w);
// }
//
// }
// if (stiva.empty()==true)
// fout << 0 << endl;
// else {
// if (stiva.size() % 2 == 1)
// fout << -1 << endl;
// else {
// nr = nr + stiva.size() / 2;
//
// fout << nr<< endl;
// }
// }
// while (stiva.empty() == false)
// stiva.pop();
// }
//}
//!
//#include<fstream>
//#include<stack>
//#include<cstring>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// char s[102], cuv1[5] = "if", cuv2[7] = "else";
// char* p;
// int n, i, j, nr = 0;
// stack<char*> stiva;
// fin >> n;
// fin.get();
// //fout << 0;
// for (i = 1; i <= n; i++) {
// fin.getline(s, 100);
// p = strtok(s, " ");
// nr = 0;
// //fout << s << endl;
// while(p) {
// if (stiva.empty() == true) {
// if (strcmp(p,"else") == 0) {
// nr++;
// stiva.push(cuv1);
// }
// else
// stiva.push(cuv1);
// }
// else {
// if (strcmp(p, "else") == 0)
// stiva.pop();
// else
// stiva.push(cuv1);
// }
// //fout << p << endl;
// p = strtok(NULL," ");
// }
// if (stiva.empty() == true)
// fout << 0 << endl;
// else {
// if (stiva.size() % 2 == 1)
// fout << -1 << endl;
// else {
// nr = nr + stiva.size() / 2;
//
// fout << nr << endl;
// }
// }
// while (stiva.empty() == false)
// stiva.pop();
// }
//}
//
//#include<fstream>
//#include<stack>
//#include<string>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int Ord(char op) {
// if (op == '*' || op == '/')
// return 2;
// if (op == '+' || op == '-')
// return 1;
// return 0;
//}
//int Evaluare(int op1, int op2, char op) {
// switch (op) {
// case '+':
// return op1 + op2;
// break;
// case '-':
// return op1 - op2;
// break;
// case '*':
// return op1 * op2;
// break;
// case '/':
// return op1 / op2;
// break;
// }
//}
//int main() {
// string expresie;
// int n, i, j, aux, op1,op2;
// stack<int> valori;
// stack<char> operatori;
// char op;
// getline(fin, expresie);
// n = expresie.size();
// for (i = 0; i < n; i++) {
// if (isdigit(expresie[i])) {
// aux = 0;
// while (isdigit(expresie[i])) {
// aux = aux * 10 + expresie[i]-'0';
// i++;
// }
// valori.push(aux);
// i--;
// continue;
// }
// if (expresie[i] == '(') {
// operatori.push(expresie[i]);
// continue;
// }
// if (expresie[i] == ')') {
// while (operatori.top() != '(') {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
// op = operatori.top();
// operatori.pop();
// valori.push(Evaluare(op1, op2, op));
// }
// operatori.pop();
// continue;
// }
// while (operatori.empty()==false&&Ord(expresie[i] <= operatori.top())) {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
// op = operatori.top();
// operatori.pop();
// valori.push(Evaluare(op1, op2, op));
// }
// operatori.push(expresie[i]);
// }
// while (operatori.empty() == false) {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
// op = operatori.top();
// operatori.pop();
// valori.push(Evaluare(op1, op2, op));
// }
// fout << valori.top();
//}
//#include<fstream>
//#include<stack>
//#include<cstring>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// char s[100002], cuv1[5] = "if", cuv2[7] = "else";
// char* p;
// int n, i, j, nr = 0;
// stack<char*> stiva;
// fin >> n;
// fin.get();
// //fout << 0;
// for (i = 1; i <= n; i++) {
// fin.getline(s, 100000);
// p = strtok(s, " ");
// nr = 0;
// //fout << s << endl;
// while (p) {
// if (stiva.empty() == true) {
// if (strcmp(p, "else") == 0) {
// nr++;
// stiva.push(cuv1);
// }
// else
// stiva.push(cuv1);
// }
// else {
// if (strcmp(p, "else") == 0)
// stiva.pop();
// else
// stiva.push(cuv1);
// }
// //fout << p << endl;
// p = strtok(NULL, " ");
// }
// if (stiva.empty() == true)
// fout << nr << endl;
// else {
// if (stiva.size() % 2 == 1)
// fout << -1 << endl;
// else {
// nr = nr + stiva.size() / 2;
//
// fout << nr << endl;
// }
// }
// while (stiva.empty() == false)
// stiva.pop();
// }
//}
//#include<fstream>
//#include<stack>
//#include<string.h>
//#include<string>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int cerinta, n, i, j, nr_par,vec[102],s=0;
// fin >> cerinta >> n;
// for (i = 1; i <= n; i++)
// fin >> vec[i];
// if (cerinta == 1) {
// nr_par = 0;
// s = vec[1] - vec[2];
// for (i = 3; i <= n; i++) {
// s += abs(vec[i]);
// }
// fout << s << '\n';
// fout << "x1-";
// for (i = 3; i <= n; i++) {
// if (vec[i] > 0) {
// if (nr_par % 2 == 0) {
// fout << "(x" << i - 1 << "-";
// nr_par++;
// }
// else
// fout << "x" << i-1 << "-";
// }
// else {
// if (nr_par % 2 == 1) {
// fout << "(x" << i - 1<<"-";
// nr_par++;
// }
// else
// fout << "x" << i - 1 << "-";
// }
// }
// fout << "x" << n;
// while (nr_par > 0) {
// fout << ")";
// nr_par--;
// }
// }
// else {
// string expresie;
// int aux, op1, op2, val,m;
// stack<int> valori;
// stack<char> operatori;
// char op;
// fin.get();
// getline(fin, expresie);
// m = expresie.size();
// for (i = 0; i < m; i++) {
// if (expresie[i] == 'x') {
// i++;
// val = 0;
// while (isdigit(expresie[i])) {
// val = val * 10 + expresie[i] - '0';
// i++;
// }
// i--;
// valori.push(vec[val]);
// continue;
// }
//
//
// if (expresie[i] == '(') {
// operatori.push(expresie[i]);
// continue;
// }
// if (expresie[i] == ')') {
// if(operatori.top()=='-') {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
// operatori.pop();
// valori.push(op1-op2);
// }
// if(operatori.empty()==false)
// operatori.pop();
// continue;
// }
// if(operatori.empty() == false&&operatori.top() == '-') {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
//
// operatori.pop();
// valori.push(op1-op2);
// }
// operatori.push(expresie[i]);
// }
// if(operatori.empty() == false) {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
//
// operatori.pop();
// valori.push(op1-op2);
// }
// fout << valori.top();
// /*fout << valori.size() << endl;
// while (valori.empty() == false) {
// fout << valori.top() << " ";
// valori.pop();
// }*/
// }
//}
//#include<fstream>
//#include<stack>
//#include<string.h>
//#include<string>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool Corect(string expr) {
// int i;
// if (expr[0] == ']')
// return false;
// if (isdigit(expr[0]))
// return false;
// for (i = 0; i < expr.size() - 1; i++) {
// if (expr[i] == '[' && expr[i + 1] == ']')
// return false;
// if (isdigit(expr[i]) && expr[i + 1] == '[')
// return false;
//
// }
// return true;
//}
//int Rezolva(string expr) {
// int i, aux, sum;
// stack<int>stiva;
// for (i = 0; i<expr.size(); i++) {
// if (isdigit(expr[i])) {
// aux = 0;
// while (isdigit(expr[i])) {
// aux = aux * 10 + expr[i] - '0';
// i++;
// }
// i--;
// stiva.push(aux);
// continue;
// }
// if (expr[i] == '[') {
// stiva.push(-1);
// continue;
// }
// if (expr[i] == ']') {
// sum = 0;
// while (stiva.empty() == false && stiva.top() != -1) {
// sum += stiva.top();
// stiva.pop();
// }
// stiva.pop();
// sum = sum / 2;
// stiva.push(sum);
// }
// }
// sum = 0;
// while(stiva.empty() == false) {
// sum += stiva.top();
// stiva.pop();
// }
// return sum;
//}
//int main() {
// stack<int>stiva;
// int n, i;
// string expr;
// getline(fin, expr);
// if (Corect(expr) == false)
// fout << "expresie gresita";
// else {
// fout << Rezolva(expr);
// }
//}
//#include<fstream>
//#include<stack>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//bool Formeaza_interval(vector<int> vec1, vector<int> vec2) {
// int min = INT_MAX, max = -1, i, fr[15002] = { 0 };
// for (i = 0; i < vec1.size(); i++) {
// if (min > vec1[i])
// min = vec1[i];
// if (max < vec1[i])
// max = vec1[i];
// fr[vec1[i]]++;
// }
// for (i = 0; i < vec2.size(); i++) {
// if (min > vec2[i])
// min = vec2[i];
// if (max < vec2[i])
// max = vec2[i];
// fr[vec2[i]]++;
// }
// for (i = min; i <= max; i++) {
// if (fr[i] == 0)
// return false;
// }
// return true;
//}
//void Afiseaza(vector<int> vec) {
// int i;
// for (i = 0; i < vec.size(); i++)
// fout << vec[i] << " ";
//}
//int main() {
// stack<vector<int>>stiva;
// vector<int>aux, x1, x2;
// int n, m, i, j, x;
// bool h;
// fin >> n >> m;
// for (i = 1; i <= m; i++) {
// for (j = 1; j <= n; j++) {
// fin >> x;
// aux.push_back(x);
// stiva.push(aux);
// aux.clear();
// }
// /*while (stiva.empty() == false) {
// aux = stiva.top();
// stiva.pop();
// for (int k = 0; k < aux.size(); k++)
// fout << aux[k] << " ";
// aux.clear();
// }*/
// fout << endl;
// while (stiva.size() > 1) {
// x1 = stiva.top();
// stiva.pop();
// h = false;
// while (stiva.empty() == false) {
// x2 = stiva.top();
// stiva.pop();
// /*if (Formeaza_interval(x1, x2)) {
// h = true;
// while (x1.size() > 0) {
// x2.push_back(x1[x1.size() - 1]);
// x1.pop_back();
// }
// stiva.pop();
// stiva.push(x2);
// }*/
//
// Afiseaza(x1);
// Afiseaza(x2);
// fout << endl;
// x2.clear();
// }
// if (h == false) {
// fout << 0 << '\n';
// break;
// }
// }
// if (stiva.size() == 1)
// fout << 1 << '\n';
//
// while (stiva.size() > 0)
// stiva.pop();
// }
//
//}
//#include<fstream>
//#include<stack>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//
//bool Formeaza_interval(vector<int> vec1, vector<int> vec2) {
// int min = INT_MAX, max = -1, i, fr[15002] = { 0 };
// for (i = 0; i < vec1.size(); i++) {
// if (min > vec1[i])
// min = vec1[i];
// if (max < vec1[i])
// max = vec1[i];
// fr[vec1[i]]++;
// }
// for (i = 0; i < vec2.size(); i++) {
// if (min > vec2[i])
// min = vec2[i];
// if (max < vec2[i])
// max = vec2[i];
// fr[vec2[i]]++;
// }
// for (i = min; i <= max; i++) {
// if (fr[i] == 0)
// return false;
// }
// return true;
//}
//void Afiseaza(vector<int> vec) {
// int i;
// for (i = 0; i < vec.size(); i++)
// fout << vec[i] << " ";
//}
//int main() {
// stack<vector<int>>stiva;
// vector<int>aux, x1, x2;
// int n, m, i, j, x;
// bool h;
// fin >> n >> m;
// for (i = 1; i <= m; i++) {
// for (j = 1; j <= n; j++) {
// fin >> x;
// aux.push_back(x);
// stiva.push(aux);
// aux.clear();
// }
// /*while (stiva.empty() == false) {
// aux = stiva.top();
// stiva.pop();
// for (int k = 0; k < aux.size(); k++)
// fout << aux[k] << " ";
// aux.clear();
// }*/
// fout << endl;
// while (stiva.size() > 1) {
//
// h = false;
// while (stiva.empty() == false) {
// x1 = stiva.top();
// stiva.pop();
// x2 = stiva.top();
// stiva.pop();
// if (Formeaza_interval(x1, x2)) {
// h = true;
// while (x1.size() > 0) {
// x2.push_back(x1[x1.size() - 1]);
// x1.pop_back();
// }
// //if(stiva.empty()==false)
// //stiva.pop();
// stiva.push(x2);
// }
//
// Afiseaza(x1);
// Afiseaza(x2);
// fout << endl;
// x2.clear();
// }
// if (h == false) {
// fout << 0 << '\n';
// break;
// }
// }
// if (stiva.size() == 1)
// fout << 1 << '\n';
//
// while (stiva.size() > 0)
// stiva.pop();
// }
//
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n, fr[100002][122], liste;
//bool Intersectat(int x, int y) {
//
//}
//void Unificare(int x,int y) {
//
//}
//int main() {
// int i, j, x, y, vec[102],st;
// stack<int>stiva;
// bool h;
// fin >> liste;
// for (i = 1; i <= liste; i++) {
// vec[i] = i;
// fin >> n;
// for (j = 1; j <= n; j++) {
// fin >> x;
// fr[i][x]++;
// }
// }
// h = true;
// n = liste;
// st = 1;
// while (h) {
// h = false;
// for (i = st; i < n; i++) {
// x = vec[i];
// y = vec[i + 1];
// if (Intersectat(x, y)) {
// Unificare(y, x);
// st++;
// h = true;
// }
// vec[i + 1] = y;
// }
// }
// /*while (stiva.size() > 1) {
// h = false;
// x = stiva.top();
// stiva.pop();
// y = stiva.top();
// if (Intersectat(x, y)) {
// Unificare(y, x);
// h = true;
// }
//
// if (h == false)
// break;
// }*/
//}
//#include<fstream>
//#include<stack>
//#include<vector>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n, fr[100002][122], liste;
//bool Intersectat(int x, int y) {
// int i;
// for (i = 0; i <= 120; i++)
// if (fr[x][i] == 1 && fr[y][i] == 1)
// return true;
// return false;
//}
//void Unificare(int x, int y) {
// int i;
// for (i = 0; i <= 120; i++) {
// if (fr[x][i] == 0 && fr[y][i] == 1)
// fr[x][i] = 1;
// }
//}
//int main() {
// int i, j, x, y, st;
// vector<int> vec;
// stack<int>stiva;
// bool h;
// fin >> liste;
// for (i = 1; i <= liste; i++) {
// vec.push_back(i);
// fin >> n;
// for (j = 1; j <= n; j++) {
// fin >> x;
// fr[i][x]=1;
// }
// }
//
// for (i = 1; i <= 4; i++,fout<<endl)
// for (j = 0; j <= 4; j++)
// fout << fr[i][j] << " ";
//
// h = true;
// while (h) {
// h = false;
// for (i = 0; i < vec.size() - 1; i++) {
// if (Intersectat(vec[i], vec[i] + 1)) {
// Unificare(vec[i], vec[i + 1]);
// h = true;
// vec.erase(vec.begin() + i + 1);
// i--;
// }
// }
// }
// fout << vec.size();
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fr[19];
//void Div5(int x, int& rez) {
// rez = x % 5;
// rez = 5 - rez;
//}
//
//int main() {
// int n, w, x, y, z, i, j, vec[102], aux, rez1, rez2,nrper=0;
// fin >> n >> w >> x >> y >> z;
// vec[1] = w;
// fr[vec[1]]++;
// fout << vec[1] << " ";
// for (i = 2; i <= n; i++) {
// aux = (x * vec[i - 1] + y) % z;
// vec[i] = aux % 10;
// fr[vec[i]]++;
// fout << vec[i] << " ";
// }
// fout << endl;
// for (i = 1; i < n-1; i++) {
// fr[vec[i]]--;
// for (j = i + 1; j < n; j++) {
//
// fr[vec[j]]--;
// Div5(vec[i] + vec[j], rez1);
// if (rez1 == 5)
// rez2 = 0;
// else
// rez2 = 5 + rez1;
// fout << vec[i]<<" "<<vec[j]<<" "<<rez1 << " " << rez2 << " " << fr[rez1] << " " << fr[rez2] << endl;
// nrper += fr[rez1] + fr[rez2];
//
// }
// for (j = i + 1; j < n; j++)
// fr[vec[j]]++;
// }
// fout << nrper;
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int a[102], b[102], n, i, j;
// bool h = true;
// double k;
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> a[i];
// for (i = 1; i <= n; i++)
// fin >> b[i];
// sort(a + 1, a + n + 1);
// sort(b + 1, b + n + 1);
// k = a[1]*1.0 / b[1];
// for (i = 2; i <= n; i++) {
// if (a[i]*1.0 / b[i] != k) {
// h = false;
// break;
// }
// }
// if (h)
// fout << "DA";
// else
// fout << "NU";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, u[102], i, minpar = 10000, minimpar = 10000,k;
// bool h = true, hh;
// fin >> n;
// for (i = 1; i <= 2 * n; i++) {
// fin >> u[i];
// if (i > n) {
// if (u[i] % 2 == 0) {
// if (u[i] < minpar)
// minpar = u[i];
// }
// else {
// if (u[i] < minimpar)
// minimpar = u[i];
// }
// if (i > n + 1) {
// if (u[i] % 2 != u[i - 1] % 2)
// h = false;
// k = u[i] % 2;
// }
// }
// }
// for (i = 1; i <= n; i++) {
// hh = false;
// if (h) {
// if (u[i] % 2 == k)
// hh = true;
// }
// if (u[i] % 2 == 0) {
// if (u[i] < minimpar)
// hh = true;
// }
// else {
// if (u[i] < minpar)
// hh = true;
// }
// if (hh == false) {
// fout << "NU";
// break;
// }
// }
// if (hh)
// fout << "DA";
//}
/*
Sa se rezolve doar cu 4 variabile
Nu mai retin prima jumatate din vector, ci retin maxpar si maximpar in prima jumatate
*/
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, u[102], i, minpar = 10000, minimpar = 10000, k=-1, x;
// bool h = true, hh;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i];
//
// }
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (x % 2 == 0) {
// if (x < minpar)
// minpar = x;
// }
// else {
// if (x < minimpar)
// minimpar = x;
// }
// }
// if (minpar == 10000) {
// k = 1;
// h = true;
// }
// if (minimpar == 10000) {
// k = 0;
// h = true;
// }
// for (i = 1; i <= n; i++) {
// hh = false;
// if (h) {
// if (u[i] % 2 == k)
// hh = true;
// }
// if (u[i] % 2 == 0) {
// if (u[i] < minimpar)
// hh = true;
// }
// else {
// if (u[i] < minpar)
// hh = true;
// }
// if (hh == false) {
// fout << "NU";
// break;
// }
// }
// if (hh)
// fout << "DA";
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fr[19];
//void Div5(int x, int& rez) {
// rez = x % 5;
// rez = 5 - rez;
//}
//
//int main() {
// int n, w, x, y, z, i, j, vec[102], aux, rez1, rez2, nrper = 0;
// fin >> n >> w >> x >> y >> z;
// vec[1] = w;
// fr[vec[1]]++;
// fout << vec[1] << " ";
// for (i = 2; i <= n; i++) {
// aux = (x * vec[i - 1] + y) % z;
// vec[i] = aux % 10;
// fr[vec[i]]++;
// fout << vec[i] << " ";
// }
// fout << endl;
// for (i = 1; i < n - 1; i++) {
// fr[vec[i]]--;
// for (j = i + 1; j < n; j++) {
//
// fr[vec[j]]--;
// Div5(vec[i] + vec[j], rez1);
// if (rez1 == 5)
// rez2 = 0;
// else
// rez2 = 5 + rez1;
// fout << vec[i] << " " << vec[j] << " " << rez1 << " " << rez2 << " " << fr[rez1] << " " << fr[rez2] << endl;
// nrper += fr[rez2];
//
// }
// for (j = i + 1; j < n; j++)
// fr[vec[j]]++;
// }
// fout << nrper;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int zero = 0, unu = 0, doi = 0, trei = 0, patru = 0, n, w, x, y, z, u[102], i, j, r,rez=0;
// fin >> n >> w >> x >> y >> z;
// u[1] = w;
// r = u[1] % 5;
// switch (r) {
// case 0:
// zero++;
// break;
// case 1:
// unu++;
// break;
// case 2:
// doi++;
// break;
// case 3:
// trei++;
// break;
// case 4:
// patru++;
// break;
// }
// for (i = 2; i <= n; i++) {
// u[i] = (x * u[i - 1] + y) % z;
// r = u[i] % 5;
// switch (r) {
// case 0:
// zero++;
// break;
// case 1:
// unu++;
// break;
// case 2:
// doi++;
// break;
// case 3:
// trei++;
// break;
// case 4:
// patru++;
// break;
// }
// }
// rez = rez + zero * unu * patru;
// rez = rez + zero * doi * trei;
// rez = rez + unu * (unu - 1) / 2 * trei;
// rez = rez + unu * doi * (doi - 1) / 2;
// rez = rez + doi * patru * (patru - 1) / 2;
// rez = rez + trei * (trei - 1) / 2 * patru;
// if (zero >= 3) {
// rez = rez + (zero - 2) * (zero - 1) * zero / 6;
// }
// fout << rez;
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Interval {
// int st, dr;
//};
//bool Intersectat(Interval a, Interval b) {
// if (a.dr + 1 == b.st || b.dr + 1 == a.st)
// return true;
// return false;
//}
//Interval Reuniune(Interval a, Interval b) {
// return { min(a.st,b.st),max(a.dr,b.dr) };
//}
//int main() {
// int n, nrsubst, i, j, t;
// stack<Interval>stiva;
// Interval aux, e,vec[102];
// fin >> n >> nrsubst;
// for (t = 1; t <= nrsubst; t++) {
// for (i = 1; i <= n; i++) {
// fin >> aux.st;
// aux.dr = aux.st;
// vec[i] = aux;
// }
// stiva.push(vec[1]);
// for (i = 2; i <= n; i++) {
// e = vec[i];
// if (Intersectat(stiva.top(), e)) {
// while (stiva.empty() == false && (Intersectat(stiva.top(), e))) {
// e = Reuniune(stiva.top(), e);
// stiva.pop();
// }
// stiva.push(e);
// }
// else
// stiva.push(e);
// }
// if (stiva.size() == 1)
// fout << 1 << '\n';
// else
// fout << 0 << '\n';
// while (stiva.empty() == false)
// stiva.pop();
// }
//
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, d, exp, maxi = 0, rez;
// fin >> n;
// d = 2;
// while (n > 1) {
// exp = 0;
// while (n % d == 0) {
// exp++;
// n = n / d;
// }
// if (maxi <= exp) {
// maxi = exp;
// rez = d;
// }
// d++;
// }
// fout << rez;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool prim(int n) {
// int i;
// for (i = 2; i * i <= n; i++) {
// if (n % i == 0)
// return false;
// if (i * i > n)
// break;
// }
// return true;
//}
//int main() {
// int n, k, x, i, dif = 10000, rez;
// fin >> n >> k;
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (prim(x)) {
// if (abs(k - x) == dif) {
// if (x < rez)
// rez = x;
// }
// if (abs(k - x) < dif) {
// dif = abs(k - x);
// rez = x;
// }
// }
// }
// fout << rez;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int NrDiv(int n) {
// int d, nr=1, exp;
// d = 2;
// while (n > 1) {
// exp = 0;
// while (n % d == 0) {
// n = n / d;
// exp++;
// }
// //merge si fara
// nr = nr * (exp + 1);
// d++;
// if (d * d > n)
// d = n;
// }
// return nr;
//}
//int main() {
// int n, p, i, x, s = 0;
// fin >> n >> p;
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (NrDiv(x) >= p)
// s += x;
// }
// fout << s;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int cmmdc(int a, int b) {
// int r;
// while (b > 0) {
// r = a % b;
// a = b;
// b = r;
// }
// return a;
//}
//int main() {
// int a, b, d;
// fin >> a >> b;
// d = cmmdc(a, b);
// fout << a / d + b / d - 2;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool prim(int n) {
// int i;
// for (i = 2; i * i <= n; i++) {
// if (n % i == 0)
// return false;
// if (i * i > n)
// break;
// }
// return true;
//}
//bool pp(int n) {
// int d;
// if (sqrt(n) == int(sqrt(n))) {
// d = sqrt(n);
// if (prim(d))
// return true;
// }
// return false;
//}
//int main() {
// int n, i, x, nr = 0;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (pp(x))
// //fout << x << " ";
// nr++;
// }
// fout << nr;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int NrFact(int n) {
// int d, nr = 0, exp;
// d = 2;
// while (n > 1) {
// exp = 0;
// while (n % d == 0) {
// n = n / d;
// exp++;
// }
// if (exp > 0)
// nr++;
// d++;
// if (d * d > n)
// d = n;
// }
// return nr;
//}
//int main() {
// int n, i,k, x, s = 0;
// fin >> k >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (NrFact(x) >= k)
// s += x;
// }
// fout << s;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int NrExp(int n) {
// int d, nr = 0, exp;
// d = 2;
// while (n > 1) {
// exp = 0;
// while (n % d == 0) {
// n = n / d;
// exp++;
// }
// if (exp > 0)
// nr+=exp;
// d++;
// if (d * d > n)
// d = n;
// }
// return nr;
//}
//int main() {
// int n, i, k, x, s = 0;
// fin >> k >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (NrExp(x) >= k)
// s += x;
// }
// fout << s;
//}
//
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool Munte(int u[], int n, int maxi, int pozvf) {
// int i, nr = 0;
// for (i = 1; i <= n; i++) {
// if (u[i] == maxi)
// nr++;
// if (nr > 1)
// return false;
// }
// if (pozvf == n)
// return false;
// for (i = 2; i <= pozvf; i++) {
// if (u[i] < u[i - 1])
// return false;
// }
// for (i = pozvf + 1; i <= n; i++)
// if (u[i] > u[i - 1])
// return false;
// return true;
//}
//int main() {
// int n, i, u[102], maxi = 0, pozvf;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i];
// if (u[i] > maxi) {
// maxi = u[i];
// pozvf = i;
// }
// }
// if (Munte(u, n, maxi, pozvf))
// fout << "DA";
// else
// fout << "NU";
//}
/*
Smenul lui Batog
*/
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int t[340], u[100002];
//int main() {
// int n, k, i, j, L = 300, x, y,s=0;
// char c;
// fin >> n >> k;
// for (i = 1; i <= k; i++) {
// fin >> c >> x >> y;
// if (c == 1) {
// u[x] = u[x] + y;
// t[x / L] += y;
// }
// else {
// for (i = x; i < (x / L + 1) * L; i++)
// s += u[i];
// for (i = x / L + 1; i < y / L; i++)
// s += t[i];
// for (i = y / L * L; i <= y; i++)
// s += u[i];
// fout << s << endl;
// }
// }
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int b[100002], t[340];
//int main() {
// int n, i, j, u[100002],L=300,q,s=0;
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// for (i = 1; i <= n; i++) {
// q = u[i] / L;
// s = 0;
// for (j = 0; j < q; j++) {
// s += t[i];
// }
// for (j = q * L; j < u[i]; j++)
// s += b[j];
// fout << s << " ";
//
// b[u[i]]++;
// t[u[i] / L]++;
//
// }
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool Munte(int u[], int n, int poz) {
// int i;
// for (i = 2; i <= poz; i++)
// if (u[i - 1] < u[i])
// return false;
// for (i = poz + 1; i <= n; i++)
// if (u[i - 1] > u[i])
// return false;
// return true;
//}
//int main() {
// int u[1002], n, i, mini = 100000,poz;
// bool h;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i];
// if (u[i] == mini)
// h = false;
// if (u[i] < mini) {
// mini = u[i];
// poz = i;
// h = true;
// }
// }
// if (h == false||poz==1||poz==n)
// fout << "NU";
// else {
// if (Munte(u, n, poz))
// fout << "DA";
// else
// fout << "NU";
// }
//}
//#include<iostream>
//#include<stack>
//#include<string>
//using namespace std;
//int Ord(char op) {
// if (op == '*' || op == '/')
// return 2;
// if (op == '+' || op == '-')
// return 1;
// return 0;
//}
//long long int Evaluare(long long int op1, long long int op2, char op) {
// switch (op) {
// case '+':
// return op1 + op2;
// break;
// case '-':
// return op1 - op2;
// break;
// case '*':
// return op1 * op2;
// break;
// case '/':
// return op1 / op2;
// break;
// }
//}
//int main() {
// string expresie;
// long long int n, i, j, aux, op1, op2;
// stack<long long int> valori;
// stack<char> operatori;
// char op;
// getline(cin, expresie);
// n = expresie.size();
// for (i = 0; i < n; i++) {
// if (isdigit(expresie[i])) {
// aux = 0;
// while (isdigit(expresie[i]) && i < n) {
// aux = aux * 10 + expresie[i] - '0';
// i++;
// }
// valori.push(aux);
// i--;
// continue;
// }
// if (expresie[i] == '(') {
// operatori.push(expresie[i]);
// continue;
// }
// if (expresie[i] == ')') {
// while (operatori.top() != '(') {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
// op = operatori.top();
// operatori.pop();
// valori.push(Evaluare(op1, op2, op));
// }
// operatori.pop();
// continue;
// }
// while (operatori.empty() == false && Ord(expresie[i]) <= Ord(operatori.top())) {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
// op = operatori.top();
// operatori.pop();
// valori.push(Evaluare(op1, op2, op));
// }
// operatori.push(expresie[i]);
// }
// while (operatori.empty() == false) {
// op2 = valori.top();
// valori.pop();
// op1 = valori.top();
// valori.pop();
// op = operatori.top();
// operatori.pop();
// valori.push(Evaluare(op1, op2, op));
// }
// cout << valori.top();
//}
//
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct AAA {
// int ind, val;
//};
//int main() {
// int n, i, poz, m, j;
// stack<AAA>stiva;
// AAA u[1002], varf;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i].val;
// u[i].ind = i;
// }
// stiva.push(u[1]);
// for (i = 2; i <= n; i++) {
// if (stiva.empty() == true || stiva.top().val >= u[i].val) {
// stiva.push(u[i]);
// }
// else {
// while (stiva.empty() == false && stiva.top().val < u[i].val) {
// varf = stiva.top();
// stiva.pop();
// u[varf.ind].val = u[i].val;
// }
// stiva.push(u[i]);
// }
// }
// while (stiva.empty() == false) {
// varf = stiva.top();
// u[varf.ind].val = -1;
// stiva.pop();
// }
// for (i = 1; i <= n; i++)
// fout << u[i].val << " ";
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct AAA {
// int ind, val;
//};
//int main() {
// int n, i, poz, m,x, j, v[1002],rez[1002];
// stack<AAA>stiva;
// stack<int> stivaa;
// AAA u[1002], varf;
// char c;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i].val;
// u[i].ind = i;
// v[i] = u[i].val;
// }
// stiva.push(u[1]);
// for (i = 2; i <= n; i++) {
// if (stiva.empty() == true || stiva.top().val <= u[i].val) {
// stiva.push(u[i]);
// }
// else {
// while (stiva.empty() == false && stiva.top().val > u[i].val) {
// varf = stiva.top();
// stiva.pop();
// u[varf.ind].val = u[i].val;
// }
// stiva.push(u[i]);
// }
// }
// while (stiva.empty() == false) {
// varf = stiva.top();
// u[varf.ind].val = 0;
// stiva.pop();
// }
// /*for (i = 1; i <= n; i++)
// fout << u[i].val << " ";*/
// for (i = 1; i <= n; i++) {
// while (stivaa.empty() == false && stivaa.top() > v[i])
// stivaa.pop();
// if (stivaa.empty() == true)
// rez[i] = 0;
// else
// rez[i] = stivaa.top();
// stivaa.push(v[i]);
// }
// /*for (i = 1; i <= n; i++)
// fout << rez[i] << " ";*/
//
// fin >> m;
// for (i = 1; i <= m; i++) {
// fin >> c >> x;
// if (c == 'S')
// fout << rez[x] << '\n';
// else
// fout << u[x].ind << '\n';
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int u[102], n, vf;
//int main() {
// int i, x;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// while (vf > 0 && u[vf] > x)
// vf--;
// if (vf == 0)
// fout << 0 << " ";
// else
// fout << u[vf] << " ";
// u[++vf] = x;
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, u[1002], i, cerinta, nr = 0;
// fin >> cerinta >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// if (cerinta == 1) {
// for (i = 2; i < n; i++) {
// if (u[i] >= u[i - 1] && u[i] > u[i + 1])
// nr++;
//
// }
// }
// fout << nr;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n=0, u[1002],m, i,x, cerinta, nr = 0;
// fin >> cerinta >> m;
// u[0] = -1;
// for (i = 1; i <= m; i++) {
// fin >> x;
// if (x != u[n])
// u[++n] = x;
// }
// if (cerinta == 1) {
// for (i = 2; i < n; i++) {
// if (u[i] > u[i - 1] && u[i] > u[i + 1])
// nr++;
// }
// }
// fout << nr;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool fr1[1002],fr2[1002],fr3[1002];
//int main() {
// int n, m, i, j, k, t, lin, col,rand=0;
// fin >> n >> m >> k;
// for (i = 1; i <= n; i++) {
// fin >> lin >> col;
// if (lin == 1)
// fr1[col] = 1;
// if (lin == 2)
// fr2[col] = 1;
// if (lin > 2) {
// if (rand == lin)
// fr3[col]++;
// }
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int cmapp(int n) {
// int i;
// i = 1;
// while (i * i <= n)
// i++;
// return (i - 1)*(i-1);
//}
//int main() {
// int p, cerinta;
// fin >> cerinta >> p;
// if (cerinta == 1) {
// fout << cmapp(p);
// }
// if (cerinta == 2) {
// int k, nret, nrp, i, j,q;
// k = cmapp(p);
// i = 1;
// while (13 * i <= p+4)
// i++;
// i--;
// nret = i;
// // q = sqrt(k) + 1;
// if (nret == 1)
// fout << k;
// else
// fout << nret*13;
// }
//}
//#include<fstream>
//#include<cmath>
//#define DIM 200000
//using namespace std;
//ifstream fin("arma1.in");
//ofstream fout("arma1.out");
//int prim[DIM + 2], ss = 0;
//void ciur() {
// int i, j, a[DIM + 2] = { 0 };
// a[0] = 1;
// a[1] = 1;
// for (i = 4; i <= DIM; i = i + 2)
// a[i] = 1;
// for (i = 3; i * i <= DIM; i = i + 2) {
// if (a[i] == 0)
// for (j = i * i; j <= DIM; j = j + 2 * i)
// a[j] = 1;
// }
// prim[++ss] = 2;
// for (i = 1; i <= DIM; i = i + 2)
// if (a[i] == 0)
// prim[++ss] = i;
//
//}
////int cmmdc(int n,int vec[]) {
//// int i, aux, r=vec[1];
//// for (i = 1; i < n; i++) {
//// while (vec[i] % vec[i+1] > 0) {
//// r = vec[i] % vec[i + 1];
//// vec[i] = vec[i + 1];
//// vec[i + 1] = r;
//// }
////
//// }
//// return r;
////
////}
//int cmmdc(int n, int vec[]) {
// int x = vec[1], a, b, r, i;
// for (i = 1; i <= n; i++) {
// a = vec[i];
// b = x;
// while (b > 0) {
// r = a % b;
// a = b;
// b = r;
// }
// x = a;
// }
// return x;
//}
//int main() {
// ciur();
// int i, n, c, j, x, d, exxp[DIM + 2], baza[100], k, exp, q = 0, p = 1, dc;
// long long int s = 0;
// fin >> c >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// k = 0;
// q = 0;
// d = prim[++k];
// while (x > 1) {
// exp = 0;
// while (x % d == 0) {
// exp++;
// x = x / d;
// }
// if (exp > 0) {
// exxp[++q] = exp;
// baza[q] = d;
// }
// d = prim[++k];
// if (d * d > x && x > 1)
// d = x;
// }
// dc = cmmdc(q, exxp);
// if (c == 2)
// fout << dc << endl;
// for (j = 1; j <= q; j++)
// exxp[j] = exxp[j] / dc;
// p = 1;
// for (j = 1; j <= q; j++)
// p = p * pow(baza[j], exxp[j]);
// //fout << p << endl;
// s = s + p;
//
//
// }
// //fin >> n;
// //for (i = 1; i <= n; i++)
// // fin >> u[i];
// //fout << cmmdc(n, u);
// /*for (i = 1; i <= ss; i++)
// fout << prim[i] << " ";*/
//
// if (c == 1)
// fout << s;
//
//
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int DDD = 200000;
//int prim[DDD / 3], u[DDD + 1],nrprim;
//void Ciur() {
// int i, j;
// u[0] = 1;
// u[1] = 1;
// for (i = 4; i <= DDD; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= DDD; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= DDD; j = j + 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= DDD; i += 2) {
// if (u[i] == 0)
// prim[++nrprim] = i;
// }
//}
//int cmmdc(int v[], int n) {
// int x, i, a,r;
// x = v[1];
// for (i = 2; i <= n; i++) {
// a = u[i];
// while (a > 0) {
// r = x % a;
// x = a;
// a = r;
// }
// }
// return x;
//}
//int main() {
// int cerinta, n, i,t, p,q,s=0, k, d,divcom, x, exp, vecexp[1002], baza[1002];
// fin >> cerinta >> n;
// Ciur();
// for (t = 1; t <= n; t++) {
// fin >> x;
// k = 0;
// q = 0;
// d = prim[++k];
// while (x > 1) {
// exp = 0;
// while (x % d == 0) {
// x = x / d;
// exp++;
// }
// if (exp > 0) {
// vecexp[++q] = exp;
// baza[q] = d;
// }
// d = prim[++k];
// if (d * d > x && x > 1)
// d = x;
// }
// divcom = cmmdc(vecexp, q);
// for (i = 1; i <= q; i++) {
// vecexp[i] = vecexp[i] / divcom;
// }
// p = 1;
// for (i = 1; i <= q; i++)
// p = p * pow(baza[i], vecexp[i]);
// s += p;
// if (cerinta == 2)
// fout << divcom << '\n';
//
// }
// if (cerinta == 1)
// fout << s;
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int b[100002], t[340];
//int main() {
// int n, i, j, u[100002], L = 300, q, s = 0;
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// for (i = 1; i <= n; i++) {
// q = u[i] / L;
// s = 0;
// for (j = 0; j < q; j++) {
// s += t[i];
// }
// for (j = q * L; j < u[i]; j++)
// s += b[j];
// fout << s << " ";
//
// b[u[i]]++;
// t[u[i] / L]++;
//
// }
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int proeminenta(int u[], int n, int poz) {
// int i, rez = 1000000, mini = 100000;
// for (i = poz - 1; i >= 1; i--) {
//
// if (u[i] > u[poz]) {
// if (u[i] - u[poz] < rez)
// rez = u[i] - u[poz];
// }
//
// }
// for (i = poz + 1; i <= n; i++) {
// if (u[i] < mini)
// mini = u[i];
// if (u[i] > u[poz]) {
// if (u[i] - u[poz] < rez)
// rez = u[i] - u[poz];
// }
// }
// return rez;
//}
//int main() {
// int n, i, u[102], k, l, q, poz,cerinta;
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// fout << proeminenta(u, n, 10);
//}
//#include<fstream>
//#include<iomanip>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col;
//};
//const int di[9] = {3,0,-1,0,1 }, dj[9] = {3, 1,0,-1,0 }; // 3 pt a nu lucra cu ei indexati de la 0
//int mat[102][102], n, m, fr[102][102];
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Exploreaza(Nod poz) {
// int i, punctaj = 0;
// Nod aux;
// while (fr[poz.lin][poz.col] == 0 && In_interior(poz)) {
// fr[poz.lin][poz.col] = 1;
// punctaj++;
// aux = poz;
//
// poz.lin += di[mat[aux.lin][aux.col]];
// poz.col += dj[mat[aux.lin][aux.col]];
//
// }
// if (In_interior(poz) && fr[poz.lin][poz.col] == 1) {
// punctaj = punctaj * 1000;
// }
// return punctaj;
//}
//void Exploreaza2(Nod poz) {
// int i, fr2[502][502] = { 0 };
// Nod aux, ult;
// while (fr2[poz.lin][poz.col] == 0 && In_interior(poz)) {
// fr2[poz.lin][poz.col] = 1;
// aux = poz;
// ult = poz;
// poz.lin += di[mat[aux.lin][aux.col]];
// poz.col += dj[mat[aux.lin][aux.col]];
//
// }
// if (In_interior(poz) && (fr2[poz.lin][poz.col] == 1|| fr2[poz.lin][poz.col] == -1)) {
// fout << ult.lin << " " << ult.col << endl;
// fr2[poz.lin][poz.col] = -1;
// aux = poz;
// poz.lin -= di[mat[ult.lin][ult.col]];
// poz.col -= dj[mat[ult.lin][ult.col]];
// ult = aux;
// while (fr2[poz.lin][poz.col] == 1) {
// fr2[poz.lin][poz.col] = -1;
// aux = poz;
// poz.lin -= di[mat[ult.lin][ult.col]];
// poz.col -= dj[mat[ult.lin][ult.col]];
// ult = aux;
// }
// }
//}
//
//
//void Exploreaza3(Nod poz, int &maxi) {
// int i, punctaj = 0;
// Nod varf, aux;
// while (fr[poz.lin][poz.col] != 1 && In_interior(poz)) {
// fr[poz.lin][poz.col] = 1;
// punctaj++;
// aux = poz;
//
// poz.lin += di[mat[aux.lin][aux.col]];
// poz.col += dj[mat[aux.lin][aux.col]];
//
//
// }
// if (In_interior(poz) && fr[poz.lin][poz.col] == 1) {
// punctaj = punctaj * 1000;
// }
// if (maxi < punctaj)
// maxi = punctaj;
//}
//int main() {
// int i, j, cerinta, nr = 0,maxi=0;
// Nod start;
// fin >> cerinta>>n >> m;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// fin >> mat[i][j];
// fin >> start.lin >> start.col;
// if (cerinta == 1) {
// fout << Exploreaza(start);
// //for (i = 1; i <= n; i++,fout<<endl)
// // for (j = 1; j <= m; j++)
// // fout << fr[i][j] << " ";
// }
// if (cerinta == 2) {
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// if (fr[i][j] != -1)
// Exploreaza2({ i,j });
// for (i = 1; i <= n; i++,fout<<endl)
// for (j = 1; j <= m; j++) {
// fout << setw(4) << fr[i][j];
// if (fr[i][j] == -1)
// nr++;
// }
// fout << nr;
// }
// if (cerinta == 3) {
// int x;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// x = Exploreaza({ i,j });
// if (x > maxi)
// maxi = x;
// }
// }
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++)
// fout << fr[i][j] << " ";
// fout << endl;
// }
// fout << maxi;
// }
//}
//#include<fstream>
//#include<iomanip>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col;
//};
//const int di[9] = { 3,0,-1,0,1 }, dj[9] = { 3, 1,0,-1,0 }; // 3 pt a nu lucra cu ei indexati de la 0
//int mat[102][102], n, m;
//bool In_interior(Nod a) {
// if (a.lin >= 1 && a.lin <= n && a.col >= 1 && a.col <= m)
// return true;
// return false;
//}
//int Exploreaza(Nod poz) {
// int i, punctaj = 0, fr[102][102] = { 0 };
// Nod aux;
// while (fr[poz.lin][poz.col] == 0 && In_interior(poz)) {
// fr[poz.lin][poz.col] = 1;
// punctaj++;
// aux = poz;
//
// poz.lin += di[mat[aux.lin][aux.col]];
// poz.col += dj[mat[aux.lin][aux.col]];
//
// }
// if (In_interior(poz) && fr[poz.lin][poz.col] == 1) {
// punctaj = punctaj * 1000;
// }
// return punctaj;
//}
//
//int main() {
// int i, j, cerinta, x,nr = 0, maxi = 0;
// Nod start;
// fin >> cerinta >> n >> m;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// fin >> mat[i][j];
// fin >> start.lin >> start.col;
// if (cerinta == 1) {
// fout << Exploreaza(start);
// }
// if (cerinta == 2) {
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++)
// mat[i][j] = Exploreaza({ i,j });
//
// }
// if (cerinta == 3) {
// for (i = 1; i <= n; i++)
// for (j = 1; j <= m; j++) {
// x= Exploreaza({ i,j });
// if (x > maxi)
// maxi = x;
// }
// fout << maxi;
// }
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool prim(int n) {
// int d;
// if (n == 1)
// return false;
// for (d = 2; d * d <= n; d++)
// if (n % d == 0)
// return false;
// return true;
//}
//int main() {
// int n, i, u[1002], nr = 0, x;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (prim(x))
// u[++nr] = x;
// }
// sort(u + 1, u + nr + 1);
// for (i = 1; i <= nr; i++)
// fout << u[i] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, u[1002], nr = 0, x;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// if (x%10==0)
// u[++nr] = x;
// }
// sort(u + 1, u + nr + 1);
// for (i = nr;i>=1;i--)
// fout << u[i] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct AAA {
// int ind, val;
//};
//void sortare(AAA u[], int n) {
// int i, j;
// AAA aux;
// for (i = 1; i < n; i++) {
// for (j = i + 1; j <= n; j++) {
// if (u[i].val > u[j].val) {
// swap(u[i], u[j]);
// }
// }
// }
//}
//int main() {
// int n, i, nr = 0, x;
// AAA u[1002];
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i].val;
// u[i].ind = i;
// }
// sortare(u, n);
// for (i = 1; i <= n; i++)
// fout << u[i].ind << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct AAA {
// int div, val;
//};
//void sortare(AAA u[], int n) {
// int i, j;
// AAA aux;
// for (i = 1; i < n; i++) {
// for (j = i + 1; j <= n; j++) {
// if (u[i].div == u[j].div) {
// if (u[i].val < u[j].val)
// swap(u[i], u[j]);
// }
// if (u[i].div > u[j].div) {
// swap(u[i], u[j]);
// }
// }
// }
//}
//int nrdiv(int n) {
// int d, exp, nr = 1;
// d = 2;
// while (n > 1) {
// exp = 0;
// while (n % d == 0) {
// n = n / d;
// exp++;
// }
// if (exp > 0)
// nr = nr * (exp + 1);
// d++;
// if (d * d > n)
// d = n;
// }
// return nr;
//}
//int main() {
// int n, i, nr = 0, x;
// AAA u[1002];
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i].val;
// u[i].div = nrdiv(u[i].val);
// }
// sortare(u, n);
// for (i = n; i >=1;i--)
// fout << u[i].val << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//void sortare(int u[], int n) {
// int i, j;
//
// for (i = 1; i < n; i++) {
// for (j = i + 1; j <= n; j++) {
// if (u[i] < u[j])
// swap(u[i], u[j]);
// }
// }
//}
//
//int main() {
// int n, i, nr = 0, x, u[1002];
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// sortare(u, n);
// for (i = 1; i <= n; i++)
// fout << u[i] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fr[100002];
//int main() {
// int n, i, x, u[20000],m=0;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// fr[x]++;
// }
// for(i=100001;i>=1;i--)
// while (fr[i] > 0) {
// fr[i]--;
// u[++m] = i;
// }
// for (i = 1; i <= n; i++)
// fout << u[i] << " ";
// fout << '\n';
// u[n + 1] = 0;
// u[0] = 0;
// for (i = 1; i <= n; i++) {
// if (u[i] == (u[i - 1] + u[i + 1]) / 2)
// fout << 1 << " ";
// else
// fout << 0 << " ";
// }
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool pie(int a, int b) {
// int r;
// while (b > 0) {
// r = a % b;
// a = b;
// b = r;
// }
// if (a == 1)
// return true;
// return false;
//}
//int main() {
// int n, i, nr = 0, x, u[1002],v[1002];
// fin >> n;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// for (i = 1; i < n; i++) {
// if (pie(u[i], u[n]))
// v[++nr] = u[i];
// }
// sort(v + 1, v + nr + 1);
// for (i = nr; i>=1;i--)
// fout << v[i] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, u[1002], k;
// fin >> n >> k;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// sort(u + 1, u + k+1);
// sort(u + k + 1, u + n + 1,greater<int>());
// for (i = 1; i <= n; i++)
// fout << u[i] << " ";
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//int main() {
// int n, i, u[1002], k, maxi = -1, pozmaxi,mini=1000000,pozmini;
// cin >> n;
// for (i = 1; i <= n; i++) {
// cin >> u[i];
// if (u[i] > maxi) {
// maxi = u[i];
// pozmaxi = i;
// }
// if (u[i] < mini) {
// mini = u[i];
// pozmini = i;
// }
// }
// if (pozmini < pozmaxi)
// sort(u + pozmini, u + pozmaxi + 1);
// else
// sort(u + pozmaxi, u + pozmini + 1);
// for (i = 1; i <= n; i++)
// cout << u[i] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//bool pp(int x) {
// int i;
// for (i = 1; i * i <= x; i++)
// if (i * i == x)
// return true;
// return false;
//}
//int main() {
// int u[1002], v[1002],m=0,poz[1002], n, i;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i];
// if (pp(u[i])) {
// v[++m] = u[i];
// poz[m] = i;
// }
// }
// sort(v + 1, v + m + 1);
// for (i = 1; i <= m; i++)
// u[poz[i]] = v[i];
// for (i = 1; i <= n; i++)
// fout << u[i] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int mat[8][8];
//int main() {
// int n, i, j,u,z,s,m,zm;
// fin >> n;
// u = n % 10;
// n /= 10;
//
// z = n % 10;
// n /= 10;
//
// s = n % 10;
// n /= 10;
//
// m = n % 10;
// n /= 10;
//
// zm = n % 10;
// n /= 10;
//
// for (i = 2; i <= 6; i++) {
// mat[1][i] = u;
// mat[i][1] = u;
// }
// for (i = 3; i <= 6; i++) {
// mat[2][i] = z;
// mat[i][2] = z;
// }
// for (i = 4; i <= 6; i++) {
// mat[3][i] = s;
// mat[i][3] = s;
// }
// for (i = 5; i <= 6; i++) {
// mat[4][i] = m;
// mat[i][4] = m;
// }
// for (i = 6; i <= 6; i++) {
// mat[5][i] = zm;
// mat[i][5] = zm;
// }
// for (i = 1; i <= 6; i++, fout << endl)
// for (j = 1; j <= 6; j++)
// fout << mat[i][j] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int mat[30][30];
//int main() {
// int n, i, j, jum;
// fin >> n;
// if (n % 2 == 0)
// jum = n / 2 - 1;
// else
// jum = n / 2;
// for (i = 1; i <= jum; i++) {
//
// }
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int dim = 100000;
//int u[dim + 1], prim[dim / 3],nrprim=0;
//void Ciur() {
// int i, j;
// for (i = 4; i <= dim; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= dim; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= dim; j =j+ 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= dim; i++)
// if (u[i] == 0)
// prim[++nrprim] = i;
//}
//int NrDiv(int n) {
// int d, exp, nr = 1, i = 0;
// d = prim[++i];
// while (n > 1) {
// exp = 0;
// while (n % d == 0) {
// n = n / d;
// exp++;
// }
// if (exp > 0)
// nr = nr * (exp + 1);
// d = prim[++i];
// if (d * d > n && n > 1)
// d = n;
// }
// return nr;
//}
//int main() {
// int n, x, i;
// Ciur();
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// fout << NrDiv(x) << '\n';
// }
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//long long const int dim = 1000;
//bool u[dim * 2];
//long long int prim[dim / 2], nrprim = 0;
//void Ciur() {
// long long int i, j;
// for (i = 4; i <= dim; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= dim; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= dim; j = j + 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= dim; i++)
// if (u[i] == 0)
// prim[++nrprim] = i;
//}
//int SumDiv(long long int n) {
// long long int d, exp, nr = 1, i = 0;
// d = prim[++i];
// while (n > 1) {
//
// exp = d;
// while (n % d == 0) {
// n = n / d;
// exp = exp * d;
// exp++;
// }
// if (exp > 0)
// nr = nr * (exp - 1) / (d - 1);
// d = prim[++i];
// if (d * d > n && n > 1)
// d = n;
// }
// return nr;
//}
//int main() {
// long long int n, x, i, nr1 = 0, nr2 = 0, nr3 = 0;
// int y;
// Ciur();
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// y = SumDiv(x);
// if (y < x)
// nr1++;
// if (y == x)
// nr2++;
// if (y > x)
// nr3++;
// fout << y << " ";
// }
// // fout << nr1 << " " << nr2 << " " << nr3;
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//long long const int dim = 1000;
//bool u[dim * 2];
//long long int prim[dim / 2], nrprim = 0;
//void Ciur() {
// long long int i, j;
// for (i = 4; i <= dim; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= dim; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= dim; j = j + 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= dim; i++)
// if (u[i] == 0)
// prim[++nrprim] = i;
//}
//int SumDiv(long long int n) {
// int i, s = 1;
// for (i = 2; i*i <= n; i++) {
// if (n % i == 0) {
// s += i;
// s = s + n / i;
// }
//
// }
// return s;
//}
//int main() {
// long long int n, x, i, nr1 = 0, nr2 = 0, nr3 = 0;
// int y;
// Ciur();
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// y = SumDiv(x);
// if (y < x)
// nr1++;
// if (y == x)
// nr2++;
// if (y > x)
// nr3++;
// fout << y << " ";
// }
// fout << nr1 << " " << nr2 << " " << nr3;
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//long long const int dim = 1000;
//bool u[dim * 2];
//long long int prim[dim / 2], nrprim = 0;
//void Ciur() {
// long long int i, j;
// for (i = 4; i <= dim; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= dim; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= dim; j = j + 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= dim; i++)
// if (u[i] == 0)
// prim[++nrprim] = i;
//}
//int SumDiv(long long int n) {
// long long int d, exp, s=1, i = 0,nn;
// d = prim[++i];
// nn = n;
// while (n > 1) {
//
// exp = 0;
// while (n % d == 0) {
// n = n / d;
// exp++;
// }
// if (exp > 0) {
// while (exp > 0) {
// s += pow(d, exp);
// s += nn / pow(d, exp);
//
// fout << pow(d, exp) << " " << nn / pow(d, exp) << endl;
// exp--;
// }
// }
// d = prim[++i];
// if (d * d > n && n > 1)
// d = n;
// }
// return s;
//}
//int main() {
// Ciur();
// long long int n;
// fin >> n;
// fout << SumDiv(n);
//}
////int main() {
//// long long int n, x, i, nr1 = 0, nr2 = 0, nr3 = 0;
//// int y;
//// Ciur();
//// fin >> n;
//// for (i = 1; i <= n; i++) {
//// fin >> x;
//// y = SumDiv(x);
//// if (y < x)
//// nr1++;
//// if (y == x)
//// nr2++;
//// if (y > x)
//// nr3++;
//// fout << y << " ";
//// }
//// fout << nr1 << " " << nr2 << " " << nr3;
////}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int mat[102][102];
//int main() {
// int i, j, n, k;
// fin >> n >> k;
// for (i = 1; i <= n; i++) {
// mat[i][i] = 1;
// mat[n - i + 1][i] = 1;
// }
// for (j = 1; j <= k; j++) {
// for (i = 1; i <= n; i++) {
// if(i+j<=n)
// mat[i + j][i] = 1;
// if(i-j>=1)
// mat[i-j][i] = 1;
// if (j + 1 <= i)
// mat[n - i + j + 1][i] = 1;
// if (n - i + 1 - j >= 1)
// mat[n - i + 1 - j][i] = 1;
// }
// }
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= n; j++) {
// if (mat[i][j] == 1)
// fout << mat[i][j] << " ";
// else
// fout << 2 << " ";
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Poz {
// int lin, col;
//};
//int mat[102][102];
//void Patrat(Poz css, Poz cdj) {
// int i;
// for (i = css.col; i <= cdj.col; i++) {
// mat[css.lin][i] = 1;
// mat[cdj.lin][i] = 1;
// }
// for (i = css.lin; i <= cdj.lin; i++) {
// mat[i][css.col] = 1;
// mat[i][cdj.col] = 1;
// }
//}
//int main() {
// int n,i,j;
// Poz css, cdj;
// fin >> n;
// css = { 1,1 };
//
// cdj = { n,n };
//
// while (css.lin <= cdj.lin) {
// Patrat(css,cdj);
// css.lin+=2;
// css.col+=2;
//
// cdj.lin-=2;
// cdj.col-=2;
//
// }
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, nrpag = 0,nn;
// fin >> n;
// nn = n;
// i = 1;
// while (i * 9 * pow(10, i - 1) <= n) {
// n -= i * 9 * pow(10, i - 1);
// nrpag = nrpag + 9 * pow(10, i - 1);
// i++;
//
// //fout << 9 * pow(10, i - 1) << " ";
// }
//
// if (n > 0)
// nrpag =nrpag+ n / i;
// fout << nrpag;
//}
//#include<iostream>
//#include<cmath>
//#include<iomanip>
//using namespace std;
//int main() {
// int n;
// cin >> n;
// while (n > 0) {
// cout << 0;
// n--;
// }
//
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//long long const int dim = 3500000;
//bool u[dim * 2];
//long long int prim[dim / 10], nrprim = 0;
//void Ciur() {
// long long int i, j;
// for (i = 4; i <= dim; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= dim; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= dim; j = j + 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= dim; i++)
// if (u[i] == 0)
// prim[++nrprim] = i;
//}
//int NrDiv(long long int n) {
// long long int d, exp,p= 1, i = 0;
// d = prim[++i];
// while (n > 1) {
// exp = 0;
// while (n % d == 0) {
// n = n / d;
// exp++;
// }
// if (exp > 0) {
// p = p * ((pow(d,exp+1)-1)/(d-1));
// // fout << d << " " << exp << endl;
// }
// d = prim[++i];
// if (d * d > n && n > 1)
// d = n;
// }
// return p;
//}
//int main() {
// long long int n, x, i;
// int y, nr1 = 0, nr2 = 0, nr3 = 0;
// Ciur();
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x;
// y = NrDiv(x)-x;
// if (y < x)
// nr1++;
// if (y == x)
// nr2++;
// if (y > x)
// nr3++;
// fout << y << " ";
// }
// fout << nr1 << " " << nr2 << " " << nr3;
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int x, a, b, c, r;
// while (fin >> x) {
// fout << x << " ";
// if (x % 3 == 0) {
// a = x / 3;
// b = x / 3;
// c = x / 3;
// }
// if (x % 3 == 1) {
// a = x / 3 ;
// b = x / 3;
// c = x / 3+1;
// }
// if (x % 3 == 2) {
// a = x / 3 ;
// b = x / 3 + 1;
// c = x / 3 + 1;
// }
// fout << a << " " << b << " " << c << '\n';
// }
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int di[9] = { -1,-1,0,1,1,1,0,-1 }, dj[9] = { 0,1,1,1,0,-1,-1,-1 };
//int mat[102][102], n, matt[102][102];
//int NrVecini(int lin, int col) {
// int k, nr = 0;
// for (k = 0; k < 8; k++) {
// if (mat[lin + di[k]][col + dj[k]] == 1)
// nr++;
// }
// return nr;
//}
//int main() {
// int nrgen, k, i, j,x;
// fin >> n >> nrgen;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// fin >> mat[i][j];
// while (nrgen >= 0) {
// //for (i = 1; i <= n; i++)
// // for (j = 1; j <= n; j++)
// // matt[i][j] = mat[i][j];
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= n; j++) {
// x = NrVecini(i, j);
// if (mat[i][j] == 1) {
// if (x < 2 || x>3)
// matt[i][j] = 0;
// else
// matt[i][j] = 1;
// }
// else {
// if (x == 3)
// matt[i][j] = 1;
// }
// }
// }
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// mat[i][j] = matt[i][j];
// nrgen--;
// }
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col;
//};
//int n, mat[102][102];
//void Chenar(Nod st, Nod dr,int ind) {
// int i, j;
// for (i = st.col; i <= dr.col; i++) {
// mat[st.lin][i] = ind;
// mat[dr.lin][i] = ind;
// }
// for (i = st.lin; i <= dr.lin; i++) {
// mat[i][st.col] = ind;
// mat[i][dr.col] = ind;
// }
//}
//int main() {
// int i, j, ind = 1;
// Nod st, dr;
// fin >> n;
// st = { 1,1 };
// dr = { n,n };
// while (st.lin <= dr.lin) {
// Chenar(st, dr,ind);
// st.lin++;
// st.col++;
// dr.lin--;
// dr.col--;
// ind++;
// }
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//typedef int Nrmare[1002];
//void Atribmic(Nrmare a, long long int n) {
// int uc;
// a[0] = 0;
// if (n == 0)
// a[++a[0]] = 0;
// else {
// while (n > 0) {
// uc = n % 10;
// a[++a[0]] = uc;
// n /= 10;
// }
// }
//}
//void Adunare(Nrmare a, Nrmare b) {
// int i, r = 0;
// while (a[0] < b[0]) {
// a[++a[0]] = 0;
// }
// while(b[0]<a[0]){
// b[++b[0]] = 0;
// }
// for (i = 1; i <= b[0]; i++) {
// r = r + a[i] + b[i];
// a[i] = r % 10;
// r = r / 10;
// }
// if (r > 0) {
// a[++a[0]] = 1;
// }
//}
//void Impart(Nrmare a, long long int b,long long int &rest) {
// int r = 0, i;
// for (i = a[0]; i >= 1; i--) {
// r = r * 10 + a[i];
// a[i] = r / b;
// r = r % b;
// }
// rest = r;
// while (a[a[0]] == 0&&a[0]>1)
// a[0]--;
//
//}
//void Afisare(Nrmare a) {
// int i;
// for (i = a[0]; i >= 1; i--)
// fout << a[i];
//}
//int Nrcif(long long int n) {
// int nr = 0;
// while (n > 0) {
// nr++;
// n /= 10;
// }
// return nr;
//}
//int main() {
// Nrmare A,C,R;
// long long int b, r, rr,n;
// int i;
// fin >> n >> b >> r;
// if (Nrcif(b) > n)
// fout << -1;
// else {
// A[0] = n;
//
// for (i = 1; i <= n - 1; i++) {
// A[i] = 0;
// }
// A[n] = 1;
// for (i = 0; i <= n; i++)
// C[i] = A[i];
// Impart(C, b, rr);
// if (r >= rr) {
// r -= rr;
// Atribmic(R, r);
// Adunare(A, R);
// }
// else {
// r = r - rr + b;
// Atribmic(R, r);
// Adunare(A, R);
// }
// Afisare(A);
// }
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int lin, col;
//};
//int n, mat[102][102];
//void Chenar(Nod st, Nod dr, int ind) {
// int i, j;
// for (i = st.col; i <= dr.col; i++) {
// mat[st.lin][i] = ind;
// mat[dr.lin][i] = ind;
// }
// for (i = st.lin; i <= dr.lin; i++) {
// mat[i][st.col] = ind;
// mat[i][dr.col] = ind;
// }
//}
//int main() {
// int i, j, ind = 1,s=0;
// Nod st, dr;
// fin >> n;
// st = { 1,1 };
// dr = { n,n };
// while (st.lin <= dr.lin) {
// Chenar(st, dr, ind);
// //s = s + ind * (n - st.lin) * (n - st.lin);
// // fout << (n - st.lin) * (n - st.lin) << " ";
// st.lin++;
// st.col++;
// dr.lin--;
// dr.col--;
// ind++;
//
// }
// fout << ind - 1 << endl;
// for (i = 1; i <= n; i++, fout << endl)
// for (j = 1; j <= n; j++) {
// fout << mat[i][j];
// s = s + mat[i][j] * (mat[i][j] + 1) / 2;
// }
// fout << s;
//}
//
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int dim = 10000;
//int u[dim + 1], prim[dim / 3], fr[10002],nrprim=0;
//void Ciur() {
// int i, j;
// u[0] = 1;
// u[1] = 1;
// for (i = 4; i <= dim; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= dim; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= dim; j += 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= dim; i++)
// if (u[i] == 0)
// prim[++nrprim] = i;
//}
//int Val_Max(int n) {
// int d, i = 0, maxi = 0;
// d = prim[++i];
// while (d <= n) {
// if (n % d == 0)
// maxi = d;
// d = prim[++i];
// }
// return maxi;
//}
//int main() {
// int n, i, j,v[10002], lmax = 0, cerinta, x,maxi=0;
// Ciur();
// fin >> n>>cerinta;
// for (i = 1; i <= n; i++) {
// fin >> x;
// v[i] = Val_Max(x);
// fr[v[i]]++;
// //fout << v[i] << " ";
// if (maxi < v[i])
// maxi = v[i];
// }
// if (cerinta == 1) {
// for (i = 1; i <= n; i++) {
// if (fr[v[i]] > 1) {
// for (j = n; j >= i; j--)
// if (v[j] == v[i]) {
// lmax = j - i + 1;
// break;
// }
// fr[v[i]] = 0;
// }
// }
// fout << lmax;
// }
// else {
// int nr = 0;
// //n(n-1)/2
// for (i = 1; i <= maxi; i++) {
// if (fr[i] > 1)
// nr += fr[i] * (fr[i] - 1) / 2;
//
// }
// fout << nr;
// }
//}
//#include<fstream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int n, pp, lg;
//vector<int>v;
//int Cb(int val) {
// int st, dr, mij;
// st = 0;
// dr = v.size() - 1;
// while (st <= dr) {
// mij = (st + dr) / 2;
// if (v[mij] == val)
// return mij;
// else {
// if (v[mij] > val)
// dr = mij - 1;
// else
// st = mij + 1;
// }
// }
//}
//
//int Cb2(int val) {
// int st, dr, mij,x;
// st = 0;
// dr = v.size() - 1;
// if (val < v[0])
// return -1;
// if (val > v[v.size() - 1])
// return -2;
// while (st <= dr) {
// mij = (st + dr) / 2;
// if (v[mij] < val) {
// x = mij;
// st = mij + 1;
// }
// else
// dr = mij - 1;
// }
// return x;
//}
//int main() {
// int i, j, u[1002], q,qq[102],rez[102],poz;
// fin >> n >> pp >> lg;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// fin >> q;
// for (i = 1; i <= q; i++) {
// fin >> qq[i];
// }
// for (i = 1; i <= lg; i++) {
// v.push_back(u[i]);
//
// }
// sort(v.begin(), v.end());
// /*for (i = 0; i < v.size(); i++)
// fout << v[i] << " ";
// fout << endl;*/
// rez[1] = v[pp - 1];
// for (i = lg + 1; i <=n; i++) {
// poz = Cb(u[i - lg]);
// v.erase(v.begin() + poz);
// poz = Cb2(u[i]);
// if (poz == -1)
// v.insert(v.begin(), u[i]);
// else if (poz == -2)
// v.push_back(u[i]);
// else
// v.insert(v.begin() + poz+1, u[i]);
//
// rez[i - lg + 1] = v[pp - 1];
// /* for (auto e : v)
// fout << e << " ";
// fout << endl;*/
// }
// for (i = 1; i <= q; i++)
// fout << rez[qq[i]] << '\n';
//}
//#include<fstream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int dim = 317;
//int n, pp, lg, fr[100002], fr_grupa[dim + 1];
//int main() {
// int i, j, u[1002], q, qq[102],x, rez[102],s,aux,auxx,t,maxi=0,st,dr;
// fin >> n >> pp >> lg;
// for (i = 1; i <= n; i++) {
// fin >> x;
// x += 50001;
// u[i] = x;
// if (u[i] > maxi)
// maxi = u[i];
// }
// fin >> q;
// for (i = 1; i <= q; i++)
// fin >> qq[i];
// for (i = 1; i <= lg; i++) {
// fr[u[i]]++;
// fr_grupa[(u[i] + 316) / 317]++;
// }
// s = 0;
// i = 0;
//
// while (s < pp) {
// i++;
// s += fr_grupa[i];
// }
// aux = s - fr_grupa[i];
// auxx = pp - aux;
// st = dim * (i - 1) + 1;
// dr = i * dim;
// if (dr > maxi)
// dr = maxi;
// for (j = st; j <=dr ; j++) {
// if (fr[j] > 0) {
// auxx -= fr[j];
// }
// if (auxx <= 0) {
// rez[1] = j-50001;
// break;
// }
// }
// for (t = lg + 1; t <= n; t++) {
// fr[u[t - lg]]--;
// fr_grupa[(u[t - lg] + 316) / 317]--;
//
// fr[u[t]]++;
// fr_grupa[(u[t] + 316) / 317]++;
//
//
// s = 0;
// i = 0;
// while (s < pp) {
// i++;
// s += fr_grupa[i];
// }
// aux = s - fr_grupa[i];
// auxx = pp - aux;
// for (j = dim * (i - 1) + 1; j <= dim * i; j++) {
// if (fr[j] > 0) {
// auxx -= fr[j];
// }
// if (auxx <= 0) {
// rez[t-lg+1] = j-50001;
// break;
// }
// }
// }
// for (i = 1; i <= q; i++)
// fout << rez[qq[i]] << '\n';
//
//
//}
//
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int mat[102][102], n, i, j, s = 0, ss = 0;
// char h = true;
// fin >> n;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// fin >> mat[i][j];
// for (i = 1; i <= n; i++)
// ss += mat[1][i];
// for (i = 2; i <= n; i++) {
// s = 0;
// for (j = 1; j <= n; j++)
// s += mat[i][j];
// if (s != ss) {
// h = false;
// break;
// }
// }
//
// if (h) {
//
//
// for (j = 1; j <= n; j++) {
// s = 0;
// for (i = 1; i <= n; i++)
// s += mat[i][j];
// if (s != ss) {
// //fout << ss<<" "<<s << " " << i << " " << j;
// h = false;
// break;
// }
// }
//
// if (h) {
// s = 0;
// for (i = 1; i <= n; i++)
//
//
// s += mat[i][i];
// if (s != ss)
// h = false;
// s = 0;
// for (i = 1; i <= n; i++)
// s += mat[i][n - i + 1];
// if (s != ss)
// h = false;
// }
// }
// if (h)
// fout << "true";
// else
// fout << "false";
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, j, mat[102][102];
// fin >> n;
// for (i = 1; i <= n; i++)
// for (j = 1; j <= n; j++)
// mat[i][j] = n * (i - 1) + j;
//
// for (i = n / 4 + 1; i <= n - n / 4; i++)
// for (j = 1; j <= n / 4; j++) {
// swap(mat[i][j], mat[n - i + 1][n - j + 1]);
// swap(mat[j][i], mat[n - j + 1][n - i + 1]);
// }
//
//
// for (i = 1; i <= n; i++, fout << '\n')
// for (j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//}
//#include<fstream>
//#include<iomanip>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int vecaux[1002], i, j, x=7, ind=9;
// for (i = 1; i <= 5; i++) {
// vecaux[i] = 4 * ind;
// ind += x;
// x -= 2;
// //fout << vecaux[i] << " ";
// }
//}
//#include<iostream>
//using namespace std;
//int main() {
// long long int n, i, s = 0;
// cin >> n;
// for (i = 1; i * i <= n; i += 2) {
// if (n % i == 0) {
// s = s + i;
// cout << i << " ";
// if (i * i < n)
// if ((n / i) % 2 == 1)
// s = s + n / i;
// }
// }
//
//
// cout << s;
//
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int mat[1002][1002];
//int main() {
// int n, i, j, lin, col, curent = 0,lin_prec,col_prec;
// fin >> n;
// lin = n / 2 + 1;
// col = n;
// while (mat[lin][col] == 0) {
// mat[lin][col] = ++curent;
// lin_prec = lin;
// col_prec = col;
// lin++;
// if (lin == n + 1)
// lin = 1;
// col++;
// if (col == n + 1)
// col = 1;
// if (mat[lin][col] != 0) {
// lin = lin_prec;
// col = col_prec - 1;
// if (col == 0)
// col = n;
// }
// }
// for (i = 1; i <= n; i++, fout << '\n')
// for (j = 1; j <= n; j++)
// fout << mat[i][j] << " ";
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int p, nret3, nret4, cerinta, piese1, piese2,d,nrdiv=0;
// fin >> cerinta >> p;
// if (cerinta == 1)
// fout << int(sqrt(p));
// if (cerinta == 2) {
// nret3 = (p + 4) / 13;
// piese1 = nret3 * 13 - 4;
// nret4 = (p + 4) / 20;
// piese2 = nret4 * 20 - 4;
// if (nret4 == nret3)
// fout << piese2;
// else
// fout << piese1;
// }
// if (cerinta == 3) {
// for (d = 3; d * d <= p; d++) {
// if (p % d == 0) {
// nrdiv++;
// // fout << d << " ";
//
// if (d * d < p)
// nrdiv++;
// }
// }
// fout << nrdiv;
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n = 0, u[10002], m, i, x, cerinta, nr = 0,varf[1002],vale[1002],nrvf=0,nrva=0;
// fin >> cerinta >> m;
// u[0] = -1;
// for (i = 1; i <= m; i++) {
// fin >> x;
// if (x != u[n])
// u[++n] = x;
// }
// if (cerinta == 1) {
// for (i = 2; i < n; i++) {
// if (u[i] > u[i - 1] && u[i] > u[i + 1])
// nr++;
// }
// fout << nr;
// }
// if (cerinta == 2) {
// int pro,pro2, ind, j,minim=1000000;
// for (i = 2; i < n; i++) {
// if (u[i] > u[i - 1] && u[i] > u[i + 1])
// varf[++nrvf] = u[i];
// if (u[i] < u[i - 1] && u[i] < u[i + 1])
// vale[++nrva] = u[i];
// }
// /*for (i = 1; i <= nrvf; i++)
// fout << varf[i] << " ";
// fout << endl;
// for (i = 1; i <= nrva; i++)
// fout << vale[i] << " ";*/
//
// for (i = 1; i <= nrvf; i++) {
// pro = varf[i];
// minim = 100000;
// for (j = i - 1; j >= 1; j--) {
// if (varf[j] > varf[i]) {
// if (vale[j] < minim)
// minim = vale[j];
// pro = varf[i] - minim;
// break;
// }
// else {
// if (vale[j] < minim)
// minim = vale[j];
// }
// }
//
// minim = 10003;
// for (j = i + 1; j <= n;j++) {
// if (varf[j] > varf[i]) {
// if (vale[j-1] < minim)
// minim = vale[j-1];
// pro =min(pro,varf[i] - minim);
// break;
// }
// else {
// if (vale[j-1] < minim)
// minim = vale[j-1];
// }
// }
// fout << pro << " ";
// }
// }
//
//}
//#include<fstream>
//#include<stack>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct Nod {
// int val, eti;
//};
//int main() {
// int n = 0, u[10002], m, i, x, cerinta, nr = 0, varf[1002], vale[1002], nrvf = 0, nrva = 0;
// fin >> cerinta >> m;
// u[0] = -1;
// for (i = 1; i <= m; i++) {
// fin >> x;
// if (x != u[n])
// u[++n] = x;
// }
// if (cerinta == 1) {
// for (i = 2; i < n; i++) {
// if (u[i] > u[i - 1] && u[i] > u[i + 1])
// nr++;
// }
// fout << nr;
// }
// if (cerinta == 2) {
// int pro, pro2, ind, j, minim = 1000000,prost[10002],prodr[10002],auxst[10002], auxdr[10002];
// stack<Nod> stiva;
// Nod v[1002];
// for (i = 2; i < n; i++) {
// if (u[i] > u[i - 1] && u[i] > u[i + 1])
// varf[++nrvf] = u[i];
// if (u[i] < u[i - 1] && u[i] < u[i + 1])
// vale[++nrva] = u[i];
// }
// for (i = 1; i <= nrvf; i++)
// v[i] = { varf[i],i };
// stiva.push(v[1]);
// prost[1] = v[1].val;
// auxst[1] = varf[1];
// for (i = 2; i <= nrvf; i++) {
// auxst[i] = vale[i - 1];
// if (stiva.top().val > varf[i]) {
// prost[i] = varf[i] - auxst[i];
// stiva.push(v[i]);
// }
// else {
// while (stiva.empty() == false && stiva.top().val <= varf[i]) {
// auxst[i] = min(auxst[i], auxst[stiva.top().eti]);
//
// stiva.pop();
// }
// if (stiva.empty() == false)
// prost[i] = varf[i] - auxst[i];
// else {
// prost[i] = varf[i];
// auxst[i] = varf[i];
// }
// stiva.push(v[i]);
// }
// }
// while (stiva.empty() == false)
// stiva.pop();
// /*for (i = 1; i <= nrvf; i++)
// fout << prost[i] << " ";*/
//
//
//
// stiva.push(v[nrvf]);
// prodr[nrvf] = v[nrvf].val;
// auxdr[nrvf] = varf[nrvf];
// for (i = nrvf - 1; i >= 1;i--) {
// auxdr[i] = vale[i];
// if (stiva.top().val > varf[i]) {
// prodr[i] = varf[i] - auxdr[i];
// stiva.push(v[i]);
// }
// else {
// while (stiva.empty() == false && stiva.top().val <= varf[i]) {
// auxdr[i] = min(auxdr[i], auxdr[stiva.top().eti]);
//
// stiva.pop();
// }
// if (stiva.empty() == false)
// prodr[i] = varf[i] - auxdr[i];
// else {
// prodr[i] = varf[i];
// auxdr[i] = varf[i];
// }
// stiva.push(v[i]);
// }
// }
// while (stiva.empty() == false)
// stiva.pop();
// for (i = 1; i <= nrvf; i++) {
// prost[i] = min(prost[i], prodr[i]);
// fout << prost[i] << " ";
// }
// }
//
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, x, i,y, lmax = 0, st, dr, nr,cif,strez,drrez;
// nr = 1;
// fin >> n;
// fin >> y;
// cif = y % 10;
// st = 1;
// for (i = 2; i <= n; i++) {
// fin >> x;
// if (x % 10 == cif)
// nr++;
// else {
// if (nr > lmax) {
// lmax = nr;
// strez = st;
// drrez = i - 1;
// }
// nr = 0;
// st = i;
// cif = x % 10;
// }
// }
// if (x%10==cif&&nr > lmax) {
// lmax = nr;
// strez = st;
// drrez = i - 1;
// }
// fout << strez << " " << drrez;
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fr[10002], u[1002], n;
//bool Pal(int st, int dr) {
// int i;
// for (i = st; i <= (st + dr) / 2; i++) {
// if (u[i] != u[dr - i + st])
// return false;
// //fout << u[i] << " " << u[dr-i+st] << '\n';
// }
// return true;
//}
//int main() {
// int i, j, lmax = 0, l = 0, st, dr, strez, drrez;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> u[i];
// fr[u[i]]++;
// }
// //fout << Pal(3, 9);
// for (i = 1; i < n; i++) {
// if (fr[u[i]] > 1) {
// for (j = i + 1; j <= n,fr[u[i]]>1; j++) {
// if (u[i] == u[j]) {
// if (Pal(i, j)) {
// //fout << i << " " << j << '\n';
// l = j - i + 1;
// if (l > lmax) {
// st = i;
// dr = j;
// lmax = l;
// }
// }
// fr[u[i]]--;
// }
// }
// }
// }
// fout << st << " " << dr;
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i,u[1002],st,dr, j, nr = 0, p, k,l;
// fin >> n >> k;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// p = 1;
// st = 1;
// dr = 1;
// while (dr <= n) {
// p *= u[dr];
// if (p >= k) {
// dr--;
// fout << st << " " << dr << endl;
//
// l = dr - st + 1;
// nr += l*(l+1)/2;
// while (p >= k) {
// p /= u[st];
// st++;
// }
// }
// dr++;
// }
// //fout << nr;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, p, i, u[1002], prec, nrsecv, prod = 1;
// fin >> n >> p;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// prec = 1;
// nrsecv = 0;
// for (i = 1; i <= n; i++) {
// prod = prod * u[i];
// if (prod < p) {
// nrsecv += i - prec + 1;
// }
// else {
// while (prod >= p) {
// prod /= u[prec];
// prec++;
// }
// nrsecv += i - prec + 1;
// }
// }
// fout << nrsecv;
//}
//#include<fstream>
//#include<queue>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, u[1002], p;
// queue<int> coada;
// long long int prod = 1, nrsecv = 0;
// fin >> n >> p;
// for (i = 1; i <= n; i++)
// fin >> u[i];
// for (i = 1; i <= n; i++) {
// coada.push(i);
// prod *= u[i];
// if (prod < p)
// nrsecv += i - coada.front() + 1;
// else {
// while (prod >= p) {
// prod /= u[coada.front()];
// coada.pop();
// }
// nrsecv += i - coada.front() + 1;
// }
// }
// fout << nrsecv;
//}
//#include<fstream>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//const int dim = 11005;
//int u[dim + 1], prim[dim / 2], fr[10502], nrprim = 0;
//void Ciur() {
// int i, j;
// u[0] = 1;
// u[1] = 1;
// for (i = 4; i <= dim; i += 2)
// u[i] = 1;
// for (i = 3; i * i <= dim; i += 2) {
// if (u[i] == 0) {
// for (j = i * i; j <= dim; j += 2 * i)
// u[j] = 1;
// }
// }
// prim[++nrprim] = 2;
// for (i = 3; i <= dim; i+=2)
// if (u[i] == 0)
// prim[++nrprim] = i;
//}
//int Val_Max(int n) {
// int d, i = 0, maxi = 0;
// d = prim[++i];
// while (d <= n) {
// if (n % d == 0)
// maxi = d;
// d = prim[++i];
// }
// return maxi;
//}
//int main() {
// int n, i, j, v[10502], lmax = 0, cerinta, x, maxi = 0;
// Ciur();
// fin >> n >> cerinta;
// for (i = 1; i <= n; i++) {
// fin >> x;
// v[i] = Val_Max(x);
//
// //fout << v[i] << " ";
// if (maxi < v[i])
// maxi = v[i];
// }
//
// if (cerinta == 1) {
// for (i = 1; i <= n; i++) {
// if(fr[v[i]]==0)
// fr[v[i]] = i;
// else {
// if (lmax < i - fr[v[i]] + 1)
// lmax = i - fr[v[i]] + 1;
// }
// }
// fout << lmax;
// }
// else {
// int nr = 0;
// for (i = 1; i <= n; i++) {
// if (fr[v[i]] == 0)
// fr[v[i]]++;
// else {
// nr += fr[v[i]];
// fr[v[i]]++;
// }
// }
// fout << nr;
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, j, N;
// fin >> n;
// N = 1 << n; // N=2^n
// for (i = 1; i < N; i++) {
// for (j = 0; j < n; j++) {
// if (i & (1 << j))
// fout << j + 1 << " ";
// }
// fout << '\n';
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, j, N, vec[1002], s, nrsub = 0, sum = 0;
// fin >> n >> s;
// for (i = 1; i <= n; i++)
// fin >> vec[i];
//
// N = 1 << n; // N=2^n
// for (i = 1; i < N; i++) {
// sum = 0;
// for (j = 0; j < n; j++) {
// if (i & (1 << j)) {
// sum += vec[j+1];
// }
//
// }
// // fout << sum << " ";
// if (sum == s) {
// nrsub++;
// for (j = 0; j < n; j++) {
// if (i & (1 << j)) {
// fout << j << " ";
// }
//
// }
// fout << endl;
// }
//
// }
// fout << nrsub;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, i, j, u[1002], poz1, poz2, mini = 100000,k;
// fin >> n;
// for (i = 0; i <= n; i++)
// u[i] = i;
// while (u[0] == 0) {
// mini = 1000;
// for (i = 1; i <= n; i++)
// fout << u[i] << " ";
// fout << endl;
// for (j = n; j >= 1; j--) {
// if (u[j - 1] < u[j]) {
// poz1 = j - 1;
// break;
// }
//
// }
// if (poz1 > 0) {
// //fout << poz1 << " ";
// for (j = poz1 + 1; j <= n; j++) {
// if (u[poz1] < u[j]) {
// if (mini > u[j]) {
// mini = u[j];
// poz2 = j;
// }
// }
// }
// //fout << poz2 << endl;
// swap(u[poz1], u[poz2]);
//
// for (j = poz1 + 1, k = n; j <= k; j++, k--) {
// swap(u[j], u[k]);
// }
// }
// else {
// u[0] = 1;
// }
// }
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int fr[102];
//int nrcif(int x) {
// int nr = 0;
// while (x > 0) {
// nr++;
// x /= 10;
// }
// return nr;
//}
//bool fragil(int x) {
// int d;
// for (d = 2; d * d <= x; d++)
// if (x % d == 0)
// return false;
// return true;
//}
//int main() {
// int n, i, x, cerinta, nrc, xx, val, etc, vecaux[10] = { 0 }, j,u[1002],nrcuf=0,nrcufere=0;
// fin >> cerinta >> n;
// n = n * 27;
//
// for (i = 1; i <= n; i++)
// fin >> u[i];
//
// for (i = 1; i <= n; i++) {
// x = u[i];
// nrc = nrcif(x);
// j = 0;
// vecaux[4] = 0;
// if (nrc == 4 || nrc == 3) {
// xx = x;
// while (xx > 0) {
// vecaux[++j] = xx % 10;
// xx /= 10;
// }
// etc = vecaux[2] * 10 + vecaux[1];
// val = vecaux[4] * 10 + vecaux[3];
// fr[etc] += val;
// //fout << val << " " << etc << endl;
// }
// }
// if (cerinta == 1) {
// for (i = 10; i <= 99; i++)
// if (fr[i] != 0)
// fout << i << " " << fr[i] << '\n';
// }
// else {
// for (i = 10; i <= 99; i++) {
// if (fr[i] != 0) {
// while (fr[i] > 0) {
// if (fragil(i)) {
// if (fr[i] >= 16) {
// fout << 16 << i << " ";
// fr[i] -= 16;
// nrcuf++;
// nrcufere++;
// }
// else {
// fout << fr[i] << i << " ";
// nrcuf++;
// fr[i] = 0;
// nrcufere++;
// }
// }
// else {
// if (fr[i] >= 64) {
// fout << 64 << i << " ";
// fr[i] -= 64;
// nrcuf++;
// nrcufere++;
// }
// else {
// fout << fr[i] << i << " ";
// fr[i] = 0;
// nrcufere++;
// nrcuf++;
// }
// }
// if (nrcuf == 9) {
// nrcuf = 0;
// fout << '\n';
// }
// }
// }
// }
// //fout << " " << nrcuf << " ";
// while (nrcufere < n) {
// fout << 0 << " ";
// nrcufere++;
// if (nrcufere %9==0) {
// fout << '\n';
//
// }
// }
// }
//}
//
//#include<fstream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct DDD {
// int d, h;
//};
//vector<DDD> v[20];
//int main() {
// int n, i, hmax = 0, x, y;
// DDD aux;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x >> y;
// v[x].push_back({ x,y });
// }
// for (i = 1; i <= 18; i++)
// if(v[i].size()>0)
// sort(v[i].begin(), v[i].end());
//
//
// /*for (i = 18; i >= 2; i--) {
// while (v[i].size() > 0) {
// aux.d = i - 1;
// aux.h = v[i][v[i].size() - 1].h+ v[i][v[i].size() - 2].h;
// v[i - 1].push_back(aux);
// }
// }
// for (i = 1; i <= 18; i++, fout << endl) {
// fout << i << " ";
// fout << v[i].size();
// }*/
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, k, u[1002], i, j;
// fin >> n >> k;
// for (i = 0; i <= k; i++)
// u[i] = i;
// while (u[0] == 0) {
// for (i = 1; i <= k; i++)
// fout << u[i] << " ";
// fout << '\n';
// i = k;
// while (u[i] == n - k + i)
// i--;
// u[i]++;
// for (j = i + 1; j <= k; j++)
// u[j] = u[j - 1] + 1;
// }
//
//}
//
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int f[50], nr, v[1002];
//char mat[1502][1502], u[2250];
//void Fibo() {
// long long int x, y, aux;
// x = 1;
// y = 1;
// f[++nr] = 1;
// f[++nr] = 1;
// while (x + y < pow(2, 31)) {
// aux = x + y;
// x = y;
// y = aux;
// f[++nr] = aux;
//
// }
//}
//int Cb(int val) {
// int st, dr, mij,rez;
// st = 1;
// dr = nr;
// while (st <= dr) {
// mij = (st + dr) / 2;
// if (val == f[mij])
// return mij;
// else {
// if (val > f[mij]) {
// rez = mij;
// st = mij + 1;
// }
// else
// dr = mij - 1;
// }
// }
// if (f[rez + 1] - val < val - f[rez])
// return -(rez + 1);
// return -(rez);
//}
//int main() {
// int i, n, m, cerinta, x,j,pozitie,nrfibo=0,dimu=0,dimv=0,strez,drrez,maxi=0,sum=0;
// Fibo();
// /*for (i = 1; i <= nr; i++)
// fout << f[i] << " ";
// fout << '\n';*/
// fin >> cerinta >> n >> m;
// for (i = 1; i <= n; i++) {
// for (j = 1; j <= m; j++) {
// fin >> x;
// pozitie = Cb(x);
// if (pozitie == 2)
// pozitie = 1;
// mat[i][j] = pozitie;
// if (pozitie > 0)
// nrfibo++;
// }
// }
// if (cerinta == 1) {
// fout << nrfibo;
// }
// else {
// /*for (i = 1; i <= n; i++, fout << '\n')
// for (j = 1; j <= m; j++)
// fout << (int)mat[i][j] << " ";
// for (i = 1; i <= dimu; i++)
// fout << (int)u[i] << " ";*/
// for (j = 1; j <= m; j++)
// for (i = 1; i <= n; i++)
// u[++dimu] = mat[i][j];
// if ((int)u[1] > 0) {
// v[1] = 1;
// dimv++;
// }
// for (i = 2; i <= dimu; i++) {
// if ((int)u[i - 1] < 0 && (int)u[i]>0)
// v[++dimv] = i;
//
// if ((int)u[i - 1] > 0 && (int)u[i] < 0)
// v[++dimv] = i - 1;
// }
// if (dimv % 2 == 1)
// v[++dimv] = dimu;
// /*for (i = 1; i <= dimv; i++)
// fout << v[i] << " ";*/
// if (dimv >= 4) {
// for (i = 1; i <= dimv - 3; i += 2) {
// if (v[i + 3] - v[i] + 1 > maxi) {
// maxi = v[i + 3] - v[i] + 1;
// strez = i;
// drrez = i + 3;
// }
// }
// //fout << maxi << " " << strez << " " << drrez << '\n';
//
// if (v[1] > 1) {
// if (maxi <= v[2]) {
// maxi = v[2];
// strez = -1;
// drrez = 2;
// }
// }
// if (v[dimv] < dimu) {
// if (maxi < dimu - v[dimv - 1] + 1) {
// maxi = dimu - v[dimv - 1] + 1;
// strez = -2;
// drrez = dimu;
// }
// }
//
// if (strez > 0) {
// for (i = v[strez]; i <= v[drrez]; i++) {
// sum += f[abs((int)u[i])];
// //fout << abs(u[i]) << " ";
// }
//
// }
// else {
// if (strez == -1) {
// for (i = 1; i <= v[2]; i++)
// sum += f[abs((int)u[i])];
// }
// else {
// for (i = v[dimv - 1]; i <= dimu; i++)
// sum += f[abs((int)u[i])];
// }
// }
// fout << sum;
// }
// else {
// if (v[1] == 1 || v[2] == dimu||dimv==0) {
// for (i = 1; i <= dimu; i++)
// sum += f[abs((int)u[i])];
// fout << sum;
// }
// else {
// if (v[1] > 1) {
// if (maxi <= v[2]) {
// maxi = v[2];
// strez = -3;
// }
// }
// if (v[2] < dimu) {
// if (maxi < dimu - v[1] + 1) {
// maxi = dimu - v[1] + 1;
// strez = -4;
// }
// }
// if (strez == -3) {
// for (i = 1; i <= v[2]; i++)
// sum += f[abs((int)u[i])];
// }
// else {
// for (i = v[1]; i <= dimu; i++)
// sum += f[abs((int)u[i])];
// }
// fout << sum;
// }
// }
// }
//
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, k, u[1002], i, j;
// fin >> n >> k;
// for (i = 0; i <= k; i++)
// u[i] = i;
// while (u[0] == 0) {
// for (i = 1; i <= k; i++)
// fout << u[i] << " ";
// fout << '\n';
// i = k;
// while (u[i] == n - k + i)
// i--;
// u[i]++;
// for (j = i + 1; j <= k; j++)
// u[j] = u[j - 1] + 1;
// }
//
//}
//#include<fstream>
//#include<vector>
//#include<algorithm>
//#include<cmath>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct DDD {
// int d, h;
//};
//vector<DDD> v[20];
//bool comp(DDD a, DDD b) {
// if (a.h > b.h)
// return true;
// return false;
//}
//int main() {
// int n, i, hmax = 0, x, j,y,s=0;
// DDD aux;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x >> y;
// v[x].push_back({ x,y });
// }
// for (i = 1; i <= 18; i++)
// if (v[i].size() > 0)
// sort(v[i].begin(), v[i].end(),comp);
//
//
// for (i = 18; i >= 2; i--) {
// while (v[i].size() > 0) {
// aux.d = i - 1;
// aux.h = v[i][v[i].size() - 1].h+ v[i][v[i].size() - 2].h;
// v[i - 1].push_back(aux);
// //v[i].erase(v[i].begin()+v[i].size()-1)
// v[i].pop_back();
// v[i].pop_back();
// }
// }
//
// for (i = 0; i < v[1].size(); i+=2) {
// s += pow(v[1][i].h + v[1][i + 1].h, 2);
// }
// fout << s;
//}
//#include<fstream>
//#include<vector>
//#include<algorithm>
//#include<cmath>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//struct DDD {
// int d, h;
//};
//vector<DDD> v[20];
//bool comp(DDD a, DDD b) {
// if (a.h > b.h)
// return true;
// return false;
//}
//int main() {
// int n, i, hmax = 0, x, j, y, s = 0;
// DDD aux;
// fin >> n;
// for (i = 1; i <= n; i++) {
// fin >> x >> y;
// v[x].push_back({ x,y });
// }
// for (i = 1; i <= 18; i++)
// if (v[i].size() > 0)
// sort(v[i].begin(), v[i].end(), comp);
//
//
// for (i = 18; i >= 2; i--) {
// while (v[i].size() > 0) {
// aux.d = i - 1;
// aux.h = v[i][v[i].size() - 1].h + v[i][v[i].size() - 2].h;
// v[i - 1].push_back(aux);
// //v[i].erase(v[i].begin()+v[i].size()-1)
// v[i].pop_back();
// v[i].pop_back();
// }
// }
//
// for (i = 0; i < v[1].size(); i += 2) {
// s += pow(v[1][i].h + v[1][i + 1].h, 2);
// }
// fout << s;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int main() {
// int n, a, b, i, aux;
// a = 1;
// b = 1;
// //fout << 1 << " " << 1 << " ";
// for (i = 1; i <= 2000; i++) {
// aux = a % 100 + b % 100;
// fout << aux % 10 << " ";
// b = a;
// a = aux;
// if (i % 60==0)
// fout << '\n';
// }
//}
//int nrzero(int poz) {
// int nr = 0;
// nr += (poz / 60) * 4;
// poz = poz % 60;
// if (poz > 14)
// nr++;
// if (poz > 29)
// nr++;
// if (poz > 44)
// nr++;
// return nr;
//}
//#include<fstream>
//using namespace std;
//ifstream fin("date.in");
//ofstream fout("date.out");
//int nrzero(int poz);
//int f[65];
//void GenerareFibo() {
// int nr = 0 , aux;
// f[1] = 1;
// f[2] = 1;
// for (int i = 3; i <= 60; i++) {
// aux = f[i - 1] % 10 + f[i - 2] % 10;
// f[i] = aux % 10;
// }
//}
//int main() {
// int n, m, cerinta,i;
// fin >> cerinta >> n >> m;
// if (cerinta == 1) {
// fout << nrzero(n * m);
// }
// else {
// GenerareFibo();
// /*for (i = 1; i <= 60; i++)
// fout << f[i] << " ";*/
//
// }
//}
//
//int nrzero(int poz) {
// int nr = 0;
// nr += (poz / 60) * 4;
// poz = poz % 60;
// if (poz > 14)
// nr++;
// if (poz > 29)
// nr++;
// if (poz > 44)
// nr++;
// return nr;
//}
#include<fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
int main() {
int n, k, i, u[1002], x, maxi = 0, st, dr, y, mini = 100000, sp[1002], maxst[1002] = { -1 }, maxdr[1002] = { -1 };
fin >> n >> k;
/*sp[0] = 0;
for (i = 1; i <= n; i++) {
fin >> u[i];
sp[i] = sp[i - 1] + u[i];
if (i > k) {
if (sp[i - k] > maxi)
maxi = sp[i-k];
maxst[i] = maxi;
}
}
maxi = 0;
for (i = n; i >= 1; i--) {
if (sp[i] > maxi)
maxi = sp[i];
if(i<=n-k+1)
maxdr[i] = maxi;
}
for (i = 1; i <= n; i++)
fout << maxst[i] << " ";
fout << '\n';
for (i = 1; i <= n; i++)
fout << maxdr[i] << " ";*/
}