//#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] << " ";*/
}