//#include <iostream>
//using namespace std;
//int fRecursiv(int n) {
// if (n == 0) {
// return 0;
// }
// int c = n % 10;
// if (c % 2 == 0) {
// c++;
// }
// else {
// c--;
// }
// return fRecursiv(n / 10) * 10 + c;
//}
//int main()
//{
// int n;
// cin >> n;
// cout << fRecursiv(n);
//}
//#include <iostream>
//using namespace std;
//
//int kpn(int a, int b, int k)
//{
// int ok = 0;
// for (int i = a; i <= b; i++)
// {
// int w = i, S = 0;
// for (int j = 2; j <= w / 2; j++)
// {
// if (w % j == 0)
// {
// S = S + j;
// }
// }
// S = 1 + S + w;
// if (S % 2 == w % 2)
// {
// ok++;
// cout << w << " ";
// }
// if (ok == k)
// {
// return w;
// }
// }
// return -1;
//}
//
//int main()
//{
// int a, b, k;
// cin >> a >> b >> k;
// cout << kpn(a, b, k);
// cout << "\n";
// main();
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//int a;
//void GenerareMatrice(vector<vector<int>>& matrice, int posxStart, int posyStart, int posxStop, int posyStop, int marimeMatrice ) {
// int xSA = posxStart, xST = posxStop;
// int ySA = posyStart, yST = posyStop;
// for (ySA= posyStart; ySA < yST; ySA++) {
// for (xSA= posxStart; xSA < xST; xSA++) {
// matrice[ySA][xSA] = 1;
// }
// }
// if (marimeMatrice < 2) {
// return;
// }
// GenerareMatrice(matrice, xSA, posyStart, posxStop + (marimeMatrice / 4), posyStop-(marimeMatrice/4), marimeMatrice / 2);
// GenerareMatrice(matrice, posxStart, ySA, posxStop-(marimeMatrice/4), posyStop + (marimeMatrice / 4), marimeMatrice / 2);
// GenerareMatrice(matrice, xSA, ySA, posxStop + (marimeMatrice / 4), posyStop + (marimeMatrice / 4), marimeMatrice / 2);
//}
//int main() {
// int n;
// cin >> n;
// a = 1 << n;
// vector<vector<int>>matrice(a, vector<int>(a, 0));
// GenerareMatrice(matrice, 0, 0, a / 2, a / 2, a);
// for (int i = 0; i < a; i++) {
// for (int j = 0; j < a; j++) {
// cout << matrice[i][j] << " ";
// }
// cout << endl;
// }
// return 0;
////}
//#include <iostream>
//#include <vector>
//#include <cmath>
//using namespace std;
//int a;
//void ConstruireMatrice(vector<vector<int>>&matrice, int posX, int posY, int marimeMatrice) {
// if (marimeMatrice < 2) {
// return;
// }
// int cposX = posX+1, cposY = posY+1;
// matrice[posY][posX] = log2(marimeMatrice + 1);
// int cont = 0;
// while (cont < marimeMatrice/2) {
// matrice[posY][cposX] = 0;
// cposX++;
// cont++;
// }
// cont = 0;
// cposX = posX - 1;
// while (cont < marimeMatrice/2) {
// matrice[posY][cposX] = 0;
// cont++;
// cposX--;
// }
// cont = 0;
// while (cont < marimeMatrice/2) {
// matrice[cposY][posX] = 0;
// cposY++;
// cont++;
// }
// cont = 0;
// cposY = posY-1;
// while (cont < marimeMatrice / 2) {
// matrice[cposY][posX] = 0;
// cont++;
// cposY--;
// }
// ConstruireMatrice(matrice, posX - (int)((float)marimeMatrice / 4 + 0.5), posY - (int)((float)marimeMatrice / 4 + 0.5), marimeMatrice / 2);
// ConstruireMatrice(matrice, posX + (int)((float)marimeMatrice / 4+0.5), posY - (int)((float)marimeMatrice / 4 + 0.5), marimeMatrice / 2);
// ConstruireMatrice(matrice, posX - (int)((float)marimeMatrice / 4 + 0.5), posY + (int)((float)marimeMatrice / 4 + 0.5), marimeMatrice / 2);
// ConstruireMatrice(matrice, posX + (int)((float)marimeMatrice / 4 + 0.5), posY + (int)((float)marimeMatrice / 4 + 0.5), marimeMatrice / 2);
//}
//int main() {
// int n;
// cin >> n;
// a = 1 << n;
// a--;
// vector<vector<int>>matrice(a, vector<int>(a, 1));
// ConstruireMatrice(matrice, a / 2, a / 2, a);
// for (int i = 0; i < a; i++) {
// for (int j = 0; j < a; j++) {
// cout << matrice[i][j] << " ";
// }
// cout << endl;
// }
//}
//#include <iostream>
//using namespace std;
//int factorial(int n,int& f) {
// if (n == 0) {
// return 1;
// }
// if (n == 1) {
// return 1;
// }
// return f = n * factorial(n - 1,f);
//}
//int main() {
// int n,f;
// cin >> n;
// cout << factorial(n,f) << "\n";
// main();
//}
//#include <iostream>
//using namespace std;
//long long SumProdRec(int n) {
// if (n <= 1) {
// return 0;
// }
// return n *(n-1) + SumProdRec(n-1);
//}
//int main() {
// int n;
// cin >> n;
// cout << SumProdRec(n);
//}
//#include <iostream>
//using namespace std;
//int cmmmdc(int x, int y) {
// if (x == y) {
// return x;
// }
// if (x < y) {
// y -= x;
// }
// else {
// x -= y;
// }
// if (x == 0 || y == 0) {
// return -1;
// }
// cmmmdc(x, y);
//}
//int main() {
// int x, y;
// cin >> x >> y;
// cout << cmmmdc(x, y);
//
//
//}
//#include <iostream>
//using namespace std;
//int cmmdc(int x, int y) {
// if (x == y) {
// return x;
// }
// if (x < y) {
// y -= x;
// }
// if (x > y) {
// x -= y;
// }
// cmmdc(x, y);
//}
//int main() {
// int x, y;
// cin >> x >> y;
// cout << cmmdc(x, y);
// return 0;
//}
//#include <string>
//#include <fstream>
//#include <vector>
//using namespace std;
//ifstream fin("spioni.in");
//ofstream fout("spioni.out");
//string mesaj;
//size_t criptareMesaj(vector<vector<string>>&matrice, size_t lungime, size_t rand) {
// if (lungime == 0) {
// return rand - 1;
// }
// size_t contor = 0;
// while (contor < mesaj.length()) {
// size_t copieContor = contor;
// for (size_t i = copieContor; i < lungime+contor; i += 2) {
// matrice[rand][copieContor] = matrice[rand - 1][i];
// copieContor++;
// }
// for (size_t i = contor +1; i < lungime+contor; i += 2) {
// matrice[rand][copieContor] = matrice[rand - 1][i];
// copieContor++;
// }
// contor += lungime;
// }
// criptareMesaj(matrice, lungime / 2, rand + 1);
//}
//int main() {
// char Key;
// fin >> Key;
// fin >> mesaj;
// vector<vector<string>>matrice(mesaj.length()+1, vector<string>(mesaj.length() + 1));
// for (size_t i = 0; i < mesaj.length(); i++) {
// matrice[0][i] = mesaj[i];
// }
// int rand =criptareMesaj(matrice, mesaj.length(), 1);
// for (size_t i = 0; i < mesaj.length(); i++) {
// fout << matrice[rand][i];
// }
// return 0;
//}
//#include <iostream>
//#include <string.h>
//using namespace std;
//int main() {
// char a[10], b[10] = { 'a' };
// cin.get(a,10,'w');
// /*cout << a << b;
// * ne spune marimea sirului a
// cout << strlen(a);*/
// // copiaza sirul a in sirul b
// //strcpy_s(b, a);
// //cout << b;
// //copiaza primele n elemente de la a pt b
// /*strncpy_s(b, a, 5);*/
// //pune sirul a la finalul sirului b
// /*strcat_s(b,a);*/
// // iti da sirul de la stanga la dreapta de la prima aparitie a lui c in colo
// /*cout << strchr(a, 'c');*/
// cout << strrchr(a, 'c');
//}
//#include <iostream>
//#include <string>
//#include <fstream>
//ifstream cin("skip.in");
//ofstream cout("skip.out");
//using namespace std;
//void criptare(string& mesaj) {
// size_t spatiu = mesaj.find(' ');
// size_t inceput = 0;
// string primaJumatate, aDouaJumatate, Rezultat = mesaj,cuvant;
// while (spatiu != string::npos) {
// size_t q = 0;
// for (size_t i = inceput; i < spatiu; i++) {
// cuvant.push_back(mesaj[i]);
// }
// if (cuvant.size() % 2 == 0) {
// for (size_t i = 0; i < cuvant.size()/2; i++) {
// primaJumatate.push_back(cuvant[i]);
// }
// for (size_t i = cuvant.size() / 2; i < cuvant.size(); i++) {
// aDouaJumatate.push_back(cuvant[i]);
// }
// }
// else {
// for (size_t i = 0; i < cuvant.size()/2; i++) {
// primaJumatate.push_back(cuvant[i]);
// }
// for (size_t i = cuvant.size() / 2; i < cuvant.size()-1; i++) {
// aDouaJumatate.push_back(cuvant[i]);
// }
// q = cuvant.size() - 1;
// primaJumatate.push_back(cuvant[q]);
// }
// q = 0;
// bool turn = true;
// for (size_t i = inceput; i < spatiu; i++) {
// if (turn) {
// Rezultat[i] = primaJumatate[q];
// turn = false;
// }
// else {
// Rezultat[i] = aDouaJumatate[q];
// q++;
// turn = true;
// }
// }
// inceput = spatiu+1;
// spatiu = mesaj.find(' ',spatiu+1);
// cuvant.clear();
// primaJumatate.clear();
// aDouaJumatate.clear();
// }
// mesaj = Rezultat;
//
//}
//int main() {
// string mesaj;
// int c;
// cin >> c;
// /*getline(cin, mesaj);*/
// cin >> mesaj;
// criptare(mesaj);
// cout << mesaj;
// return 0;
//}
//#include<iostream>
//using namespace std;
//int NrXDivImp(int a[], int st, int dr, int x) {
// if (st == dr) {
// return (a[st] == x ? 1 : 0);
// }
//
// int m = (st + dr) / 2;
//
// int Stanga = NrXDivImp(a, st, m, x);
// int Dreapta = NrXDivImp(a, m + 1, dr, x);
//
// return Stanga + Dreapta;
//}
//int main() {
// int a[1000], st, dr, x,n;
// cin >> st >> dr >> x >>n;
// for (int i = 0; i < n; i++) {
// cin >> a[i];
// }
// cout << NrXDivImp(a, st, dr, x);
//}
//struct Coordonate {
// int x1, x2, y1, y2;
//};
//void func(vector<Coordonate>& sir, int n, int m, int a) {
// for (int i = 1,int q=0; i <= n / 2; i++) {
// if (n % i == 0) {
// sir[q].x1 =
// }
// }
//}
//#include <fstream>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//struct Pozitii {
// int x1, x2, y1, y2;
//};
//
//int calculDivizori(vector<Pozitii>& sir, int a) {
// int q = 1, contor = 0;
// for (int i = 1; i <= a / 2; i++) {
// if (a % i == 0) {
// int x = a / i;
// sir[q].x2 = i;
// sir[q].x1 = 1;
// sir[q].y2 = x;
// sir[q].y2 = 1;
// contor++;
// }
// }
// return contor;
//}
//
//int calculDeZerouri(vector<bool> R, vector<bool> C, int x1, int x2, int y1, int y2) {
// int nrDeZerouri = 0;
// for (int i = y1; i < y2; i++) {
// for (int j = x1; j < x2; j++) {
// if ((R[i] ^ C[j]) == 0) {
// nrDeZerouri++;
// }
// }
// }
// return nrDeZerouri;
//}
//
//int main() {
// int n, m, a, nrMaxDeZerouri = -1, nrMaxDreptunghi = 0;
// cin >> n >> m >> a;
// vector<bool> R(n + 1), C(m + 1);
// vector<Pozitii> Pozitii(a + 2);
//
// for (int i = 0; i < n; i++) {
// bool x;
// cin >> x;
// R[i] = x;
// }
//
// for (int i = 0; i < m; i++) {
// bool x;
// cin >> x;
// C[i] = x;
// }
//
// int contor = calculDivizori(Pozitii, a);
// for (int i = 0; i < contor; i++) {
// int nrDeZerouri = calculDeZerouri(R, C, Pozitii[i].x1, Pozitii[i].x2, Pozitii[i].y1, Pozitii[i].y2);
// if (nrDeZerouri == nrMaxDeZerouri) {
// nrMaxDreptunghi++;
// }
// if (nrDeZerouri > nrMaxDeZerouri) {
// nrMaxDeZerouri = nrDeZerouri;
// nrMaxDreptunghi = 1;
// }
// for (int w = Pozitii[i].y1 + 1; w < Pozitii[i].y2; w++) {
// for (int q = Pozitii[i].x1 + 1; q < Pozitii[i].y2; q++) {
// if (R[w - 1] ^ C[q - 1] == 0 && R[w] ^ C[q] != 0) {
// nrDeZerouri--;
// }
// else if (R[w - 1] ^ C[q - 1] != 0 && R[w] ^ C[q] == 0) {
// nrDeZerouri++;
// }
// if (nrDeZerouri == nrMaxDeZerouri) {
// nrMaxDreptunghi++;
// }
// if (nrDeZerouri > nrMaxDeZerouri) {
// nrMaxDeZerouri = nrDeZerouri;
// nrMaxDreptunghi = 1;
// }
// }
// }
// }
// cout << nrMaxDeZerouri << " " << nrMaxDreptunghi;
// return 0;
//}
//#include <iostream>
//using namespace std;
//int main() {
// char a[101];
// int nrMaxLitere = -1, nrMaxCuvinte = -1;
// cin.get(a, 101);
// for (int i = 0; a[i] != 0; i++) {
// int nrDeLitere = 0;
// if (a[i] != ' ') {
// while (a[i] != ' ' && a[i] !=0) {
// nrDeLitere++;
// i++;
// }
// if (nrDeLitere > nrMaxLitere) {
// nrMaxLitere = nrDeLitere;
// nrMaxCuvinte = 1;
// }
// else if (nrDeLitere == nrMaxLitere) {
// nrMaxCuvinte++;
// }
// if (a[i] == 0) {
// i--;
// }
// }
// }
// cout << nrMaxLitere << " " << nrMaxCuvinte;
//}
//#include <fstream>
//#include<iostream>
//#include <vector>
//using namespace std;
//ifstream fin("TextFile1.txt");
////ofstream fout("insule.out");
//void stanga(vector<vector<bool>>& verificare, vector<vector<int>>matrice, int i, int q, int indicator, int n, int m);
//void jos(vector<vector<bool>>& verificare, vector<vector<int>>matrice, int i, int q, int indicator, int n, int m);
//void dreapta(vector<vector<bool>>& verificare, vector<vector<int>>matrice, int i, int q,int indicator,int n,int m) {
// while (q<m && matrice[i][q] == indicator && verificare[i][q]==0) {
// verificare[i][q] = 1;
// int y = i + 1;
// if (i+1<n && matrice[y][q] == indicator && verificare[y][q] == 0) {
// jos(verificare, matrice, y, q, indicator, n, m);
// }
// q++;
// }
//}
//void jos(vector<vector<bool>>& verificare, vector<vector<int>>matrice, int i, int q, int indicator, int n, int m) {
// while (i < n && matrice[i][q] == indicator && verificare[i][q] == 0) {
// verificare[i][q] = 1;
// int y = q + 1;
// if (y < m && matrice[i][y] == indicator && verificare[i][y] == 0) {
// dreapta(verificare, matrice, i, y, indicator, n, m);
// }
// y -= 2;
// if (y >=0 && matrice[i][y] == indicator && verificare[i][y] == 0) {
// stanga(verificare, matrice, i, y, indicator, n, m);
// }
// i++;
// }
//}
//void stanga(vector<vector<bool>>& verificare, vector<vector<int>>matrice, int i, int q, int indicator, int n, int m) {
// while (q >= 0 && matrice[i][q] == indicator && verificare[i][q] == 0) {
// verificare[i][q] = 1;
// int y = i + 1;
// if (y < n && matrice[y][q] == indicator && verificare[y][q] == 0) {
// jos(verificare, matrice, y, q, indicator, n, m);
// }
// q--;
// }
//}
//int main() {
// int n, m, nr=0, ng=0, nb=0;
// fin >> n >> m;
// vector<vector<int>>matrice(n, vector<int>(m));
// vector<vector<bool>>verificare(n, vector<bool>(m));
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// fin >> matrice[i][j];
// verificare[i][j] = 0;
// }
// }
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (matrice[i][j] == 1 && verificare[i][j] == 0) {
// nr++;
// int q = j + 1;
// int indicator = 1;
// if (q < m && matrice[i][q] == 1 && verificare[i][q] == 0) {
// dreapta(verificare, matrice, i, q, indicator, n, m);
// }
// int y = i + 1;
// if (y < n && matrice[y][j] == 1 && verificare[y][q] == 0) {
// jos(verificare, matrice, y, j, indicator, n, m);
// }
// }
// if (matrice[i][j] == 2 && verificare[i][j] == 0) {
// ng++;
// int q = j + 1;
// int indicator = 2;
// if (q < m && matrice[i][q] == 2 && verificare[i][q] == 0) {
// dreapta(verificare, matrice, i, q, indicator, n, m);
// }
// int y = i + 1;
// if (y < n && matrice[y][j] == 2 && verificare[y][q] == 0) {
// jos(verificare, matrice, y, j, indicator, n, m);
// }
// }
// if (matrice[i][j] == 3 && verificare[i][j] == 0) {
// nb++;
// int q = j + 1;
// int indicator = 3;
// if (q < m && matrice[i][q] == 3 && verificare[i][q] == 0) {
// dreapta(verificare, matrice, i, q, indicator, n, m);
// }
// int y = i + 1;
// if (y < n && matrice[y][j] == 3 && verificare[i][q] == 0) {
// jos(verificare, matrice, y, j, indicator, n, m);
// }
// }
// verificare[i][j] = 1;
// }
// }
// cout << nr << " " << ng << " " << nb << " ";
//}
//#include <fstream>
//#include <iostream>
//#include <vector>
//using namespace std;
//ifstream fin("tort.in");
//ofstream fout("tort.out");
//int main() {
// int n;
// cin >> n;
// vector<int>a(n);
// vector<long long>prefix(n + 1);
// prefix[0] = 0;
//
// for (int i = 0; i < n; i++) {
// cin >> a[i];
// prefix[i+1] = prefix[i] + a[i];
// }
// long long total = prefix[n];
// int raspuns = 0;
// for (int i = 1; i <= n; i++) {
// long long Rest = total - prefix[i];
// for (int j = i + 1; j <= n; j++) {
// long long X = prefix[j] - prefix[i];
// if (X > Rest) {
// break;
// }
// if (Rest % X != 0) {
// continue;
// }
// long long sumaCurenta = 0;
// bool valid = true;
// for (int q = j + 1; q <= n; q++) {
// sumaCurenta += a[q - 1];
// if (sumaCurenta > X) {
// valid = false;
// break;
// }
// if (sumaCurenta == X) {
// sumaCurenta = 0;
// }
// }
// if (valid && sumaCurenta == 0) {
// raspuns++;
// }
// }
// }
// cout << raspuns;
//
// return 0;
//}
/*#include <fstream>
#include <iostream>
#include <vector>
#include<cmath>
using namespace std;
ifstream fin("tort.in");
ofstream fout("tort.out");
int main() {
int n;
cin >> n;
vector<int>a(n);
vector<long long>prefix(n + 1);
prefix[0] = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
prefix[i + 1] = prefix[i] + a[i];
}
long long total = prefix[n];
int raspuns = 0;
for (int i = 1; i <= n; i++) {
long long Rest = total - prefix[i];
raspuns++;
for (int j = 2; j <= (int)sqrt(Rest); j++) {
if (Rest % j != 0) {
continue;
}
int X = Rest / j;
long long sumaCurenta = 0;
bool valid = true;
for (int q = i + 1; q <= n; q++) {
sumaCurenta += a[q - 1];
if (sumaCurenta > X) {
valid = false;
break;
}
if (sumaCurenta == X) {
sumaCurenta = 0;
}
}
if (valid && sumaCurenta == 0) {
raspuns++;
}
}
}
cout << raspuns;
return 0;
}*/
//#include <iostream>
//#include <vector>
//using namespace std;
//struct Coordonate {
// int x, y;
//};
//int main() {
// int n;
// cin >> n;
// vector<Coordonate>sir(n);
// for (int i = 0; i < n; i++) {
//
// }
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("diferenta.in");
//ofstream fout("diferenta.out");
//int NrDePerechi(int numar) {
// int nrDePerechi = 0;
// for (long long d1 = 1; d1 * d1 <= numar; d1++) {
// if (numar % d1 == 0) {
// int d2 = numar / d1;
// if ((d1 + d2) % 2 == 0) {
// nrDePerechi++;
// }
// }
// }
// return nrDePerechi;
//}
//int main() {
// int n, m;
// fin >> n >> m;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// int c;
// fin >> c;
// fout << NrDePerechi(c) << " ";
// }
// fout << '\n';
// }
//}
/*#include <iostream>
#include <cmath>
using namespace std;
int Prime(int a[], int st, int dr) {
if (st == dr) {
if (a[st] % 2 == 1) {
return 1;
}
else {
return 0;
}
}
int mij = (st + dr) / 2;
int count = Prime(a, st, mij) + Prime(a, mij + 1, dr);
return count;
}
int main() {
int n, v[100];
cin >> n;
for (int i = 0; i < n; i++) {
cin >> v[i];
}
cout << Prime(v, 0, n - 1);
return 0;
}*/
//#include <iostream>
//#include <fstream>
//#include <vector>
//using namespace std;
//ifstream fin("ture.in");
//ofstream fout("ture.out");
//int main() {
// int n;
// fin >> n;
// vector<vector<int>> matrice(n, vector<int>(n));
// vector<long long> prefixOrz(n, 0), prefixVer(n, 0);
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// fin >> matrice[i][j];
// prefixOrz[i] += matrice[i][j];
// prefixVer[j] += matrice[i][j];
// }
// }
// long long maxim = 0;
// for (int r1 = 0; r1 < n; r1++) {
// for (int c1 = 0; c1 < n; c1++) {
// for (int r2 = r1; r2 < n; r2++) {
// for (int c2 = 0; c2 < n; c2++) {
//
// if (r1 == r2 && c1 >= c2) continue;
//
// int suma = 0;
//
// if (r1 == r2) {
// suma = prefixOrz[r1] + prefixVer[c1] + prefixVer[c2] - 2 * matrice[r1][c1] - 2 * matrice[r1][c2];
// }
// else if (c1 == c2) {
// suma = prefixVer[c1] + prefixOrz[r1] + prefixOrz[r2] - 2 * matrice[r1][c1] - 2 * matrice[r2][c1];
// }
// else {
// suma = prefixOrz[r1] + prefixVer[c1] + prefixOrz[r2] + prefixVer[c2] - 2 * matrice[r1][c1] - 2 * matrice[r2][c2] - matrice[r1][c2] - matrice[r2][c1];
// }
//
// if (suma > maxim)
// maxim = suma;
// }
// }
// }
// }
//
// fout << maxim;
// return 0;
//
// }
//#include <iostream>
//#include <fstream>
//#include <vector>
//using namespace std;
//ifstream fin("intersectie.in");
//ofstream fout("intersectie.out");
//struct Coordonate {
// int x, y;
//};
//int main() {
// int n, m, t;
// fin >> n >> m >> t;
// vector<Coordonate>sirNormal(m),sirSpecial(m),sirSpecialCuRotire(m);
// Coordonate a;
// int numarator = 0;
// for (int i = 0; i < m; i++) {
// fin >> a.x;
// fin >> a.y;
// if (a.x == a.y - 1 || a.x == 1 && a.y == n) {
// numarator++;
// continue;
// }
// if (a.x == a.y) {
// sirSpecial[i] = a;
// }
// else if (a.x > a.y) {
// sirSpecialCuRotire[i] = a;
// }
// else {
// sirNormal[i] = a;
// }
// }
// int cont=0;
// for (int i = 0; i < t; i++) {
// fin >> a.x >> a.y;
// if (a.x == a.y - 1 || a.x == 1 && a.y == n) {
// fout << numarator << "\n";
// continue;
// }
// if (a.x == a.y) {
// int nnm = sirSpecial.size();
// for (int i = 0; i < nnm; i++) {
// if (a.x == sirSpecial[i].x) {
// cont++;
// }
// }
// nnm = sirNormal.size();
// for (int i = 0; i < nnm; i++) {
// if (a.y <= sirNormal[i].y) {
// cont++;
// }
// }
// nnm = sirSpecialCuRotire.size();
// for (int i = 0; i < nnm; i++) {
// if (a.x >= sirSpecialCuRotire[i].x || a.y <= sirSpecialCuRotire[i].y) {
// cont++;
// }
// }
// fout << cont + numarator << '\n';
// continue;
// }
// if (a.x > a.y) {
// int nnm = sirSpecialCuRotire.size();
// for (int i = 0; i < nnm; i++) {
// if (a.x >= sirSpecialCuRotire[i].x && a.y <= sirSpecialCuRotire[i].y) {
// cont++;
// }
// }
// fout << cont + numarator << '\n';
// continue;
// }
// int nnm = sirNormal.size();
// for (int i = 0; i < nnm; i++) {
// if (a.x >= sirNormal[i].x && a.y <= sirNormal[i].y) {
// cont++;
// }
// }
//
// fout << cont+numarator << '\n';
// }
//}
//#include <iostream>
//#include <fstream>
//#include <vector>
//using namespace std;
//ifstream fin("intersectie.in");
//ofstream fout("intersectie.out");
//bool cautare(vector<vector<int>>matrice, int n, int m, int numar) {
// if (numar == 2) {
// for (int i = 0; i < n-1; i++) {
// for (int j = 0; j < m-1; j++) {
// if (matrice[i][j] < matrice[i][j + 1] || matrice[i][j] < matrice[i + 1][j]) {
// return true;
// }
// }
// }
// return false;
// }
//}
//int main() {
// int n, m;
// cin >> n >> m;
// vector<vector<int>>matrice(n, vector<int>(m));
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cin >> matrice[i][j];
// }
// }
// int numar = 1;
// bool advr = cautare(matrice, n, m, numar + 1);
// if (advr) {
// numar++;
// }
// cout << numar;
//}
//#include <iostream>
//using namespace std;
//int v[100], n;
//int vpoz[100];
//void back(int poz) {
// if (poz == n) {
// for (int i = 0; i < n; i++) {
// if (vpoz[i]) {
// cout << v[i];
// }
// }
// cout << '\n';
// return;
// }
// vpoz[poz] = 0;
// back(poz + 1);
// vpoz[poz] = 1;
// back(poz + 1);
//}
//int main() {
// cin >> n;
// for (int i = 0; i < n; i++) {
// cin >> v[i];
// }
// back(0);
//}
//#include <iostream>
//using namespace std;
//
//int n;
//int sol[10];
//bool used[10];
//
//void back(int k) {
// if (k == n) {
// for (int i = 0; i < n; i++)
// cout << sol[i] << " ";
// cout << "\n";
// return;
// }
//
// for (int x = 1; x <= n; x++) {
// if (!used[x]) {
// used[x] = true;
// sol[k] = x;
// back(k + 1);
// used[x] = false;
// }
// }
//}
//
//int main() {
// cin >> n;
// back(0);
// return 0;
//}
//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <string>
//#include <Set>
//#include <algorithm>
//using namespace std;
//ifstream fin("anagrame.in");
//ofstream fout("anagrame.out");
//bool verificare(set<int>a, set<int>b);
//int main() {
// int C,N,M;
// string A;
// set<int>poz[26];
// int frecvantaMinima[26], frecventa[26];
// fin >> C >> N >> M;
// fin >> A;
// for (int i = 0; i < N; i++) {
// poz[A[i] - 'a'].insert(i);
// }
// if (C == 1) {
// while (M) {
// string x;
// int y,numar;
// fin >> x>> y;
// if (isdigit(x[0])) {
// numar = stoi(x);
// for (int i = 0; i < 26; i++) {
// char litera = 'a'+i;
//
// }
//
// }
// else {
// A[y - 1] = x[0];
// }
// M--;
// }
//
//
// }
// else {
//
// }
//}
//#include <fstream>
//#include <vector>
//#include <string>
//#include <set>
//#include <algorithm>
//
//using namespace std;
//
//ifstream fin("anagrame.in");
//ofstream fout("anagrame.out");
//set<int> pos[26];
//int current_ranges[26], best_ranges[26];
//bool has_best = false;
//
//int main() {
// int C, N, M;
// if (!(fin >> C >> N >> M)) return 0;
//
// string A;
// fin >> A;
// for (int i = 0; i < N; i++) {
// pos[A[i] - 'a'].insert(i + 1);
// }
//
// if (C == 1) {
// while (M--) {
// string x_str;
// int y_val;
// fin >> x_str >> y_val;
//
// if (isdigit(x_str[0])) {
// int x = stoi(x_str);
// int y = y_val;
// for (int i = 0; i < 26; i++) {
// current_ranges[i] = 0;
//
// if (pos[i].empty()) continue;
// auto it_first = pos[i].lower_bound(x);
// if (it_first != pos[i].end() && *it_first <= y) {
// auto it_last = pos[i].upper_bound(y);
// --it_last;
//
// if (*it_first != *it_last) {
// current_ranges[i] = *it_last - *it_first;
// }
// }
// }
// bool is_better = false;
// if (!has_best) {
// is_better = true;
// }
// else {
// for (int i = 0; i < 26; i++) {
// if (current_ranges[i] > best_ranges[i]) {
// is_better = true;
// break;
// }
// if (current_ranges[i] < best_ranges[i]) {
// is_better = false;
// break;
// }
// }
// }
//
// if (is_better) {
// has_best = true;
// for (int i = 0; i < 26; i++) best_ranges[i] = current_ranges[i];
// }
// }
// else {
// char noua_litera = x_str[0];
// int pozitie = y_val;
//
// char litera_veche = A[pozitie - 1];
// pos[litera_veche - 'a'].erase(pozitie);
//
// A[pozitie - 1] = noua_litera;
// pos[noua_litera - 'a'].insert(pozitie);
// }
// }
// if (has_best) {
// for (int i = 0; i < 26; i++) {
// for (int j = 0; j < best_ranges[i]; j++) {
// fout << (char)('a' + i);
// }
// }
// }
// }
// else {
// while (M--) {
// string x_str;
// int y_val;
// fin >> x_str >> y_val;
//
// if (isdigit(x_str[0])) {
// int x = stoi(x_str);
// int y = y_val;
// for (int i = 0; i < 26; i++) {
// current_ranges[i] = 0;
//
// if (pos[i].empty()) continue;
// auto it_first = pos[i].lower_bound(x);
// if (it_first != pos[i].end() && *it_first <= y) {
// auto it_last = pos[i].upper_bound(y);
// --it_last;
//
// if (*it_first != *it_last) {
// current_ranges[i] = *it_last - *it_first;
// }
// }
// }
// int total = 0, inmultire = -1;
// for (int i = 0; i < 26; i++) {
// total += current_ranges[i];
// if (current_ranges[i] != 0) {
// inmultire++;
// }
// }
// if (inmultire == 0) {
// fout << 1 << endl;
// }
// else if (inmultire == -1) {
// continue;
// }
// else {
// fout << total * inmultire;
// }
// }
// else {
// char noua_litera = x_str[0];
// int pozitie = y_val;
//
// char litera_veche = A[pozitie - 1];
// pos[litera_veche - 'a'].erase(pozitie);
//
// A[pozitie - 1] = noua_litera;
// pos[noua_litera - 'a'].insert(pozitie);
// }
// }
// }
//
// return 0;
//}
//#include <iostream>
//#include <fstream>
//#include <vector>
//using namespace std;
//ifstream fin("golf.in");
//ofstream fout("golf.out");
//bool matrice[1005][1005], verificare[1005][1005];
//int total = 0;
//int n, m, t;
//
//void Exploreaza(int i, int j) {
// if (i < 0 || i >= n || j < 0 || j >= m || matrice[i][j] == 0) {
// return;
// }
// matrice[i][j] = 0;
// total++;
// Exploreaza(i + 1, j);
// Exploreaza(i - 1, j);
// Exploreaza(i, j + 1);
// Exploreaza(i, j - 1);
//}
//int main() {
// fin >> t >> n >> m;
// if (t == 1) {
// char x;
// int total = 0;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// fin >> x;
// total += x-'0';
// }
// }
// fout << total << '\n';
// }
// else if (t == 2) {
// char x;
// int max = 0, nrMax = 0;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// fin >> x;
// matrice[i][j] = x - '0';
// verificare[i][j] = 0;
// }
// }
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (matrice[i][j] == 1 &&verificare[i][j]!=1) {
// Exploreaza(i, j);
// if (total > max) {
// max = total;
// nrMax = 1;
// }
// else if (total == max) {
// nrMax++;
// }
// total = 0;
// }
// }
// }
// fout << nrMax;
// }
// else {
// char x;
// int max = 0, nrMax = 0;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// fin >> x;
// matrice[i][j] = x - '0';
// verificare[i][j] = 0;
// }
// }
// int q,y,a=0,b=0;
// fin >> q;
// while (q--) {
// fin >> x >> y;
// if (x == 'C') {
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < y-1; j++) {
// if (matrice[i][j] == 1)
// a++;
// }
// }
// for (int i = 0; i < n; i++) {
// for (int j = y; j < m; j++) {
// if (matrice[i][j] == 1)
// b++;
// }
// }
// fout << a * b<<'\n';
// a = b = 0;
// }
// if (x == 'L') {
// for (int i = 0; i < y-1; i++) {
// for (int j = 0; j < m; j++) {
// if (matrice[i][j] == 1)
// a++;
// }
// }
// for (int i =y; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (matrice[i][j] == 1)
// b++;
// }
// }
// fout << a * b <<'\n';
// a = b = 0;
// }
// }
// }
// return 0;
//}
//#include <iostream>
//#include <vector>
//#include <fstream>
//using namespace std;
//int n;
//vector<bool>sir;
//vector<int>sirnr;
//void back(int k) {
// for (int i = 0; i < n; i++) {
// if (sir[i] == false) {
// sirnr[k] = i + 1;
// sir[i] = true;
//
// if (k == n - 1) {
// for (i = 0; i < n; i++) {
// cout << sirnr[i] << " ";
// }
// cout << '\n';
// }
// else {
// back(k + 1);
// }
// sir[i] = false;
// }
// }
//
//}
//int main() {
// cin >> n;
// sir.resize(n);
// sirnr.resize(n);
// for (int i = 0; i < n;i++) {
// sir[i] = false;
// }
// back(0);
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//int n;
//int F23(int n) {
// if (n == 1) {
// return 1;
// }
// if (n == 0 || (n % 2 != 0 && n % 3 != 0)) {
// return 0;
// }
// if (n % 2 == 0) {
// return F23(n / 2);
// }
// if (n % 3 == 0) {
// return F23(n / 3);
// }
//}
//int main() {
// cin >> n;
// cout << F23(n);
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//int n, matrice[100][100];
//int cmmdc(int a, int b) {
// if (a == 1 || b == 1) {
// return 1;
// }
// while (b != 0) {
// int r = a % b;
// a = b;
// b = r;
// }
// return a;
//}
//int cmmdcMatrice(int c,int i = 0, int j = 0, int b = matrice[1][1]) {
// if (i >= n) {
// return b;
// }
// if (matrice[i][j] == 1 || b == 1) {
// return 1;
// }
// if(c==1){
// int r;
// if (matrice[i][j] > b) {
// r = cmmdc(matrice[i][j], b);
// }
// else if (matrice[i][j] == b) {
// r = b;
// }
// else {
// r = cmmdc(b, matrice[i][j]);
// }
// i++, j++;
// return cmmdcMatrice(1,i, j, r);
// }
// else if (c == 2) {
// int r;
// if (matrice[i][j] > b) {
// r = cmmdc(matrice[i][j], b);
// }
// else if (matrice[i][j] == b) {
// r = b;
// }
// else {
// r = cmmdc(b, matrice[i][j]);
// }
// i++, j--;
// return cmmdcMatrice(2,i, j, r);
// }
//}
//int main() {
// cin >> n;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cin >> matrice[i][j];
// }
// }
// cout << cmmdcMatrice(1) << " " << cmmdcMatrice(2) << " ";
//}
//#include <iostream>
//using namespace std;
//int FPareImpare(int n) {
// if (n == 0) {
// return 0;
// }
// int numar = 0;
// if (n % 2 == 0) {
// numar++;
// }
// else {
// numar--;
// }
// if (n / 10 == 0) {
// return numar;
// }
// return numar + FPareImpare(n / 10);
//}
//int main() {
// int n;
// cin >> n;
// cout << FPareImpare(n);
//
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//int n=1;
//void ColtStangaSus(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2);
//void ColtDreaptaSus(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2, int n);
//void ConstruireMatrice(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2, int n);
//void ColtDreaptaJos(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2, int n);
//void ColtStangaJos(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2, int n);
//void ColtStangaSus(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2) {
// for (int i=i1; i < i2; i++) {
// for (int j=j1; j < j2; j++) {
// matrice[i][j] = 1;
// }
// }
//}
//void ColtDreaptaSus(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2,int n) {
// ConstruireMatrice(matrice, i1, j1, i2, j2, n / 2);
//}
//void ColtDreaptaJos(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2, int n){
// ConstruireMatrice(matrice, i1, j1, i2, j2, n / 2);
//}
//void ColtStangaJos(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2, int n) {
// ConstruireMatrice(matrice, i1, j1, i2, j2, n / 2);
//}
//void ConstruireMatrice(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2,int n) {
// if (n == 1)
// return;
// ColtStangaSus(matrice, i1, j1, i2 + n / 2, j2 + n / 2);
// ColtDreaptaSus(matrice, i1, j1 + n / 2, i2, j2 + n / 2, n);
// ColtDreaptaJos(matrice, i1 + n / 2, j1 + n / 2, i2 + n / 2, j2 + n / 2, n);
// ColtStangaJos(matrice, i1 + n / 2, j1, i2 + n / 2, j2, n);
//}
//int main() {
// int a;
// cin >> a;
// n = n << a;
// vector<vector<bool>>matrice(n, vector<bool>(n));
// for (int i = 0; i < n; i++) {
// for (int j = 1; j < n; j++) {
// matrice[i][j] = 0;
// }
// }
// ConstruireMatrice(matrice, 0, 0, 0, 0, n);
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cout << matrice[i][j] << " ";
// }
// cout << endl;
// }
//}
//#include <iostream>
//#include<vector>
//using namespace std;
//void ConstruireMatrice(vector<vector<int>>& matrice, int i1, int j1,int n,int a) {
// if (a==0)
// return;
// matrice[i1][j1] = a;
// for (int i = 1; i < ((n + 1) / 2); i++) {
// matrice[i1+i][j1] = 0;
// }
// for (int i = -1; n / 2 + i+1 > 0; i--) {
// matrice[i1 - i][j1] = 0;
// }
// for (int j = 1; j < ((n + 1) / 2); j++) {
// matrice[i1][j1+j] = 0;
// }
// for (int j = -1; n / 2 + j + 1 > 0; j--) {
// matrice[i1][j1-j] = 0;
// }
// ConstruireMatrice(matrice, i1 - n /2, j1 - n / 2, n / 2,a-1);
// ConstruireMatrice(matrice, i1 - n / 2, j1 + n / 2, n / 2, a - 1);
// ConstruireMatrice(matrice, i1 + n / 2, j1 - n / 2, n / 2, a - 1);
// ConstruireMatrice(matrice, i1 + n / 2, j1 + n / 2, n / 2, a - 1);
//}
//int main() {
// int n = 1, a;
// cin >> a;
// n = n << a;
// n--;
// vector<vector<int>>matrice(n + 1, vector<int>(n + 1));
// ConstruireMatrice(matrice, n/2, n/2, n, a);
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << matrice[i][j] << " ";
// }
// cout << endl;
// }
//
// return 0;
//}
//#include <iostream>
//#include <vector>
//#include <string>
//#include <algorithm>
//
//using namespace std;
//vector<char> solutie;
//vector<bool> vizitat;
//void afiseaza_solutie() {
// for (char cifra : solutie) {
// cout << cifra;
// }
// cout << "\n";
//}
//void genereaza_permutari(string& numar, int pas) {
// if (pas == numar.length()) {
// afiseaza_solutie();
// return;
// }
// for (int i = 0; i < numar.length(); i++) {
// if (vizitat[i]) continue;
// if (i > 0 && numar[i] == numar[i - 1] && !vizitat[i - 1]) continue;
// vizitat[i] = true;
// solutie.push_back(numar[i]);
// genereaza_permutari(numar, pas + 1);
// solutie.pop_back();
// vizitat[i] = false;
// }
//}
//
//int main() {
// string numar;
// cout << "Introdu numarul: ";
// cin >> numar;
// sort(numar.begin(), numar.end());
// vizitat.resize(numar.length(), false);
// cout << "Permutarile numarului sunt:\n";
// genereaza_permutari(numar, 0);
//
// return 0;
//}
//#include <iostream>
//using namespace std;
//int cmmdc(int a, int b) {
// int r;
// while (b != 0) {
// r = a % b;
// a = b;
// b = r;
// }
// return a;
//}
//int DiagonalaPrincipala(int matrice[][100], int i, int j, int n) {
// if (i == n - 1) {
// return matrice[i][j];
// }
// return cmmdc(matrice[i][j], DiagonalaPrincipala(matrice, i+1, j+1, n));
//}
//int DiagonalaSecundara(int matrice[][100], int i, int j, int n) {
// if (i == n - 1) {
// return matrice[i][j];
// }
// return cmmdc(matrice[i][j], DiagonalaSecundara(matrice, i + 1, j-1, n));
//}
//int Contur(int matrice[][100], int i, int j, int n, int c) {
// if (c == 1) {
// if (j == n - 1) {
// return matrice[i][j];
// }
// return cmmdc(matrice[i][j], Contur(matrice, i, j + 1, n, c));
// }
// if (c == 2) {
// if (i == n - 1) {
// return matrice[i][j];
// }
// return cmmdc(matrice[i][j], Contur(matrice, i+1, j, n, c));
// }
// if (c == 3) {
// if (j == 0) {
// return matrice[i][j];
// }
// return cmmdc(matrice[i][j], Contur(matrice, i, j-1, n, c));
// }
// if (c == 4) {
// if (i == 0) {
// return matrice[i][j];
// }
// return cmmdc(matrice[i][j], Contur(matrice, i-1, j, n, c));
// }
//}
//int main() {
// int matrice[100][100];
// int n;
// cin >> n;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) {
// cin >> matrice[i][j];
// }
// }
// int a = Contur(matrice, 0, 0, n, 1), b = Contur(matrice, 0, n - 1, n, 2), c = Contur(matrice, n - 1, n - 1, n, 3), d = Contur(matrice, n - 1, 0, n, 4);
// a = cmmdc(a, b);
// c = cmmdc(c, d);
// a = cmmdc(a, c);
// cout << DiagonalaPrincipala(matrice, 0, 0, n) << " " << DiagonalaSecundara(matrice, 0, n - 1, n) << " " << a;
//}
//#include<iostream>
//using namespace std;
//int main() {
// int matrice[12][12] = { 0 };
// matrice[0][0] = 1;
// int n, m;
// cin >> n >> m;
// for (int i = 0; i <= n; i++) {
// for (int j = 0; j <= m; j++) {
// if (i > 0) {
// matrice[i][j] += matrice[i - 1][j];
// }
// if (j > 0) {
// matrice[i][j] += matrice[i][j - 1];
// }
// }
// }
// cout << matrice[n][m];
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//int n;
//vector<int>sir;
//void citire() {
// cin >> n;
// sir.resize(n);
// for (int i = 0; i < n; i++) {
// cin >> sir[i];
// }
//}
//void afisare() {
// for (int i = 0; i < n; i++) {
// cout << sir[i] << " ";
// }
//}
//int nr_ap(int numar, int c) {
// if (numar < 10) {
// if (numar % 10 == c) {
// return 1;
// }
// else {
// return 0;
// }
// }
// int r = 0;
// if (numar % 10 == c) {
// r= 1;
// }
// return r + nr_ap(numar / 10,c);
//}
//int prima_cifra(int numar) {
// if (numar < 10) {
// return numar;
// }
// return prima_cifra(numar / 10);
//}
//void inloc() {
// int a;
// for (int i = 0; i < n; i++) {
// a = prima_cifra(sir[i]);
// sir[i] = nr_ap(sir[i], a);
// }
//}
//int main() {
// citire();
// inloc();
// afisare();
//
// return 0;
//}
//#include <iostream>
//#include <vector>
//#include <cmath>
//#include <fstream>
//using namespace std;
//ifstream fin("sierpinski.in");
//ofstream fout("sierpinski.out");
//void fill(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2);
//void ConstruireMatrice(vector<vector<bool>>& matrice, int a, int i1, int j1, int i2, int j2);
//void fill(vector<vector<bool>>& matrice, int i1, int j1, int i2, int j2) {
// for (int i = i1; i < i2; i++) {
// for (int j = j1; j < j2; j++) {
// matrice[i][j] = 1;
// }
// }
//}
//void ConstruireMatrice(vector<vector<bool>>& matrice, int a, int i1, int j1, int i2, int j2) {
// if (a == 3) {
// fill(matrice, i1 + a / 3, j1 + a / 3, i2 - a / 3, j2 - a / 3);
// return;
// }
// fill(matrice, i1 + a / 3, j1 + a / 3, i2 - a / 3, j2 - a / 3);
// ConstruireMatrice(matrice, a / 3, i1, j1, i2 -2*a/ 3, j2 -2*a/ 3);
// ConstruireMatrice(matrice, a / 3, i1, j1 + a / 3, i2 - 2 * a / 3, j2 -a / 3);
// ConstruireMatrice(matrice, a / 3, i1, j1 + (2 * a) / 3, i2 - 2 * a / 3, j2);
// ConstruireMatrice(matrice, a / 3, i1+a/3, j1, i2 -a/3,j2 -2 * a / 3);
// ConstruireMatrice(matrice, a / 3, i1 + a / 3, j1 + (2 * a)/3, i2 -a/3, j2);
// ConstruireMatrice(matrice, a / 3, i1+ (2 * a)/3, j1, i2, j2 - 2 * a / 3);
// ConstruireMatrice(matrice, a / 3, i1 + (2 * a)/3, j1 + a / 3, i2, j2 -a/3);
// ConstruireMatrice(matrice, a / 3, i1 + (2 * a)/3, j1 + (2 * a)/3, i2, j2);
//}
//int main() {
// int n;
// cin >> n;
// int a = pow(3, n);
// vector<vector<bool>>matrice(a, vector <bool>(a));
// for (int i = 0; i < a; i++) {
// for (int j = 0; j < a; j++) {
// matrice[i][j] = 0;
// }
// }
// ConstruireMatrice(matrice, a, 0, 0, a, a);
// for (int i = 0; i < a; i++) {
// for (int j = 0; j < a; j++) {
// cout << matrice[i][j] << " ";
// }
// cout << endl;
// }
//}
#/*include<iostream>
#include<vector>
using namespace std;
int nr_min(vector<int>sir,int inceput,int final) {
int nr_min = 100000000;
for (int i = inceput; i < final; i++) {
if (sir[i] < nr_min) {
nr_min = sir[i];
}
}
return nr_min;
}
int main() {
int n,m= 100000000,count=0;
cin >> n;
vector<int>sir(n);
vector <bool>verificare(n+2);
verificare.assign(n+2, 1);
verificare[0] = 0;
verificare[n + 1] = 0;
for (int i = 0; i < n; i++) {
cin >> sir[i];
if (sir[i] < m) {
m = sir[i];
}
}
for (int i = 0; i < n; i++) {
sir[i] -= m;
if (sir[i] == 0) {
verificare[i+1] = 0;
}
}
count++;
bool cont = true;
while (cont) {
int inceput = -1;
int final = -1;
for (int i = 1; i < n+1; i++) {
if (verificare[i - 1] == 0 && verificare[i] == 1) {
inceput = i-1;
}
if (verificare[i] == 1 && verificare[i + 1] == 0) {
final = i;
}
if (final != -1 && inceput != -1) {
break;
}
}
if (final == -1 && inceput == -1) {
break;
}
m = nr_min(sir, inceput, final);
for (int i = inceput; i < final; i++) {
sir[i] -= m;
if (sir[i] == 0) {
verificare[i+1] = 0;
}
}
count++;
}
cout << count;
}*/
//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <stack>
//
//using namespace std;
//
//ifstream fin("alpinistii.in");
//ofstream fout("alpinistii.out");
//
//int n, m;
//vector<vector<bool>> matrice;
//vector<vector<bool>> verificare;
//
//void parcurgere(int i, int j, int& count) {
// if (i < 0 || i >= n || j < 0 || j >= m) {
// return;
// }
// if (matrice[i][j] != 0 || verificare[i][j] == 1) {
// return;
// }
// verificare[i][j] = 1;
// count++;
// parcurgere(i, j + 1, count);
// parcurgere(i, j - 1, count);
// parcurgere(i + 1, j, count);
// parcurgere(i - 1, j, count);
//}
//
//int main() {
// int x, max_zona = 0, c;
// if (!(fin >> c >> n >> m)) return 0;
//
// matrice.assign(n, vector<bool>(m, 0));
// verificare.assign(n, vector<bool>(m, 0));
//
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// fin >> x;
// matrice[i][j] = x;
// }
// }
//
// if (c == 1) {
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (verificare[i][j] == 1) {
// continue;
// }
// if (matrice[i][j] == 0) {
// int suma = 0;
// parcurgere(i, j, suma);
// if (suma > max_zona) {
// max_zona = suma;
// }
// }
// }
// }
// fout << max_zona;
// }
// else {
// int max_dreptunghi = 0;
// vector<int> heights(m, 0);
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (matrice[i][j] == 0) {
// heights[j]++;
// }
// else {
// heights[j] = 0;
// }
// }
// stack<int> s;
// int j = 0;
// while (j < m) {
// if (s.empty() || heights[s.top()] <= heights[j]) {
// s.push(j);
// j++;
// }
// else {
// int tp = s.top();
// s.pop();
// int latime = s.empty() ? j : j - s.top() - 1;
// int aria = heights[tp] * latime;
//
// if (aria > max_dreptunghi) {
// max_dreptunghi = aria;
// }
// }
// }
// while (!s.empty()) {
// int tp = s.top();
// s.pop();
// int latime = s.empty() ? j : j - s.top() - 1;
// int aria = heights[tp] * latime;
//
// if (aria > max_dreptunghi) {
// max_dreptunghi = aria;
// }
// }
// }
// fout << max_dreptunghi;
// }
//
// return 0;
//}
//#include <iostream>
//#include <vector>
//#include <fstream>
//#include <algorithm>
//#include <queue>
//using namespace std;
//ifstream fin("zana.in");
//ofstream fout("zana.out");
//int n, m;
//int matrice[185][185];
//bool verificare[185][185], vizitat[185][185];
//bool este_valid(int i, int j) {
// return(i > 0 && j > 0 && i <= n && j <= m && verificare[i][j] == 0&&vizitat[i][j]!=1);
//}
//bool posibil(int i, int j) {
// int stop_x = 1, stop_y = 1;
// queue<pair<int, int>>q;
// q.push({i,j});
// vizitat[i][j] = true;
// while (!q.empty()) {
// int x = q.front().first;
// int y = q.front().second;
// q.pop();
// if (x == stop_x && y == stop_y) {
// return true;
// }
// if (este_valid(x, y + 1)) {
// vizitat[x][y + 1] = true;
// q.push({ x,y + 1 });
// }
// if (este_valid(x, y - 1)) {
// vizitat[x][y - 1] = true;
// q.push({ x,y - 1 });
// }
// if (este_valid(x+1, y)) {
// vizitat[x+1][y] = true;
// q.push({ x+1,y});
// }
// if (este_valid(x-1, y)) {
// vizitat[x-1][y] = true;
// q.push({ x-1,y});
// }
// }
// return false;
//}
//int main() {
// int k;
// fin >> n >> m >> k;
// int n1 = 0, n2 = 0,max=0;
// int x, y;
// vector<int>v;
// while (k--) {
// fin >> x >> y;
// matrice[x][y]++;
// verificare[x][y] = 1;
// }
// if (matrice[1][1] > 0) {
// fout << 1 << endl << 1;
// }
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// vizitat[i][j] = 0;
// if (matrice[i][j] > 0) {
// v.push_back(matrice[i][j]);
// }
// }
// }
// sort(v.begin(), v.end(), greater<int>());
// auto it = unique(v.begin(), v.end());
// v.erase(it, v.end());
// int count = 0;
// bool sePoate = false;
// while (1&&count<v.size()) {
// max = v[count];
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// if (matrice[i][j] == max) {
// bool b = posibil(i, j);
// if (b == true) {
// sePoate = true;
// }
// for (int i = 1;i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// vizitat[i][j] = 0;
// }
// }
// if (sePoate == true&&n1==0) {
// n1 = max;
// n2 = 1;
// }
// else if (sePoate == true && b == true) {
// n2++;
// }
// }
// }
// }
// if (sePoate == true) {
// break;
// }
// count++;
// }
// fout << n1 << endl << n2;
//}
//#include<iostream>
//#include<fstream>
//#include<string>
//#include<vector>
//#include<algorithm>
//using namespace std;
//ifstream fin("logic.in");
//ofstream fout("logic.out");
//bool numarare(string a, string b,int& cont,bool verificare[]) {
// bool verificare2[26] = { false };
// for (char caracter : a) {
// if (caracter >= 'a' && caracter <= 'z' && verificare[caracter - 'a']==false) {
// verificare[caracter - 'a'] = true;
// cont++;
// }
// }
// for (char caracter : b) {
// if (caracter >= 'a' && caracter <= 'z') {
// verificare2[caracter - 'a'] = true;
// }
// }
// for (int i = 0; i < 26; i++) {
// if (verificare[i] == true && verificare2[i] == false) {
// return false;
// }
// if (verificare[i] == false && verificare2[i] == true) {
// return false;
// }
// }
// return true;
//}
//void RezolvareEcuatie(string& a) {
// while (a.rfind('(')!=string::npos) {
// size_t inceput = a.rfind('(');
// a.erase(inceput, 1);
// size_t final = a.find(')', inceput);
// a.erase(final, 1);
// final--;
// while (a.rfind('~', final) != string::npos) {
// size_t index = a.rfind('~', final);
// if (index < inceput || index == string::npos) {
// break;
// }
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// numarTemporar = !numarTemporar;
// a[index] = numarTemporar + 48;
// final--;
// }
// while (a.find('&', inceput) != string::npos) {
// size_t index = a.find('&', inceput);
// if (index > final) {
// break;
// }
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// int numarTemporar2 = a[index - 1] - 48;
// numarTemporar = numarTemporar & numarTemporar2;
// a[index - 1] = numarTemporar+48;
// a.erase(index,1);
// final = final - 2;
// }
// while (a.find('^', inceput) != string::npos) {
// size_t index = a.find('^', inceput);
// if (index > final) {
// break;
// }
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// int numarTemporar2 = a[index - 1] - 48;
// numarTemporar = numarTemporar ^ numarTemporar2;
// a[index - 1] = numarTemporar+48;
// a.erase(index,1);
// final = final - 2;
// }
// while (a.find('|',inceput) != string::npos) {
// size_t index = a.find('|', inceput);
// if (index > final) {
// break;
// }
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// int numarTemporar2 = a[index - 1] - 48;
// numarTemporar = numarTemporar | numarTemporar2;
// a[index - 1] = numarTemporar+48;
// a.erase(index,1);
// final = final - 2;
// }
// }
// while (a.rfind('~') != string::npos) {
// size_t index = a.rfind('~');
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// numarTemporar = !numarTemporar;
// a[index] = numarTemporar + 48;
// }
// while (a.find('&') != string::npos) {
// size_t index = a.find('&');
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// int numarTemporar2 = a[index - 1] - 48;
// numarTemporar = numarTemporar & numarTemporar2;
// a[index - 1] = numarTemporar+48;
// a.erase(index,1);
// }
// while (a.find('^') != string::npos) {
// size_t index = a.find('^');
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// int numarTemporar2 = a[index - 1] - 48;
// numarTemporar = numarTemporar ^ numarTemporar2;
// a[index - 1] = numarTemporar+48;
// a.erase(index,1);
// }
// while (a.find('|') != string::npos) {
// size_t index = a.find('|');
// a.erase(index, 1);
// int numarTemporar = a[index] - 48;
// int numarTemporar2 = a[index - 1] - 48;
// numarTemporar = numarTemporar | numarTemporar2;
// a[index - 1] = numarTemporar+48;
// a.erase(index,1);
// }
//}
//int main() {
// int k;
// fin >> k;
// fin.get();
// while (k--) {
// string a, b;
// getline(fin, a);
// getline(fin, b);
// int cont = 0;
// bool verificare[26] = { 0 };
// bool Adevarat = false;
// if (numarare(a, b,cont,verificare)) {
// int totalCombinati = 1 << cont;
// vector<bool>variabile(cont);
// for (int i = 0; i < totalCombinati; i++) {
// for (int j = 0; j < cont; j++) {
// variabile[j] = (i >> j) & 1;
// }
// int contorPtVariabile = 0;
// string temp_a = a;
// string temp_b = b;
// for (int q = 0; q < 26; q++) {
// if (verificare[q] == true) {
// int X = variabile[contorPtVariabile]+48;
// replace(temp_a.begin(), temp_a.end(), 'a' + q, X);
// replace(temp_b.begin(), temp_b.end(), 'a' + q, X);
// contorPtVariabile++;
// }
// }
// RezolvareEcuatie(temp_a);
// RezolvareEcuatie(temp_b);
// if (temp_a == temp_b) {
// Adevarat = true;
// continue;
// }
// else {
// Adevarat = false;
// fout << "diferite" << endl;
// break;
// }
// }
// if (Adevarat) {
// fout << "egale" << endl;
// }
// }
// else {
// fout << "diferite" << endl;
// }
// }
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("permutari.in");
//ofstream fout("permutari.out");
//int n,st[101];
//bool verif[101] = { 0 };
//void afisare() {
// for (int i = 1; i <= n; i++) {
// cout << st[i] << " ";
// }
// cout << endl;
//}
//void back(int k) {
// if (k > n) {
// afisare();
// return;
// }
// for (int i = 1; i <= n; i++) {
// if (verif[i] == false) {
// st[k] = i;
// verif[i] = true;
// back(k + 1);
// verif[i] = false;
// }
// }
//}
//int main() {
// cin >> n;
// back(1);
// return 0;
//}
//#include <iostream>
//#include <vector>
//#include <fstream>
//using namespace std;
//ifstream fin("soarece.in");
//ofstream fout("soarece.out");
//int n, m;
//int dx[] = { -1, 0, 1, 0 };
//int dy[] = { 0, 1, 0, -1 };
//int matrice[15][15];
//int is, js, ib, jb;
//int solutii = 0;
//void back(int x, int y) {
// if (x == ib && y == jb) {
// solutii++;
// return;
// }
// for (int i = 0; i < 4; i++) {
// int nou_x = x + dx[i];
// int nou_y = y + dy[i];
// if (nou_x <= n && nou_x >= 1 && nou_y <= m && nou_y >= 1 && matrice[nou_x][nou_y] == 0) {
// matrice[nou_x][nou_y] = 1;
// back(nou_x, nou_y);
// matrice[nou_x][nou_y] = 0;
// }
// }
//}
//int main() {
// fin >> n >> m;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// fin >> matrice[i][j];
// }
// }
// fin >> is >> js >> ib >> jb;
// matrice[is][js] = 1;
// back(is, js);
// fout << solutii;
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("partitiinumar.in");
//ofstream fout("partitiinumar.out");
//int n;
//int v[42];
//int suma=0;
//void Afisare(int k) {
// for (int i = 1; i <=k; i++) {
// cout << v[i] << " ";
// }
// cout << endl;
//}
//void back(int k) {
// if (suma == n) {
// Afisare(k - 1);
// return;
// }
// for (int i = v[k - 1]; i <= n; i++) {
// if (suma + i <= n) {
// v[k] = i;
// suma += i;
// back(k + 1);
// suma -= i;
// }
// }
//}
//int main() {
// cin >> n;
// v[0] = 1;
// back(1);
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("partitiinumar1.in");
//ofstream fout("partitiinumar1.out");
//int n, v[41], suma = 0;
//bool verificare[41];
//void Afisare(int k) {
// for (int i = 1; i <= k; i++) {
// fout << v[i] << " ";
// }
// fout << endl;
//}
//void back(int k) {
// if (suma == n) {
// Afisare(k - 1);
// return;
// }
// for (int i = v[k - 1] + 1; i <= n; i++) {
// if (suma + i <= n) {
// suma += i;
// v[k] = i;
// back(k + 1);
// suma -= i;
// }
// }
//}
//int main() {
// fin >> n;
// v[0] = 0;
// back(1);
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("permutari1.in");
//ofstream fout("permutari1.out");
//int n, v[11];
//bool verif[11];
//void Afisare() {
// for (int i = 1; i <= n; i++) {
// fout << v[i] << " ";
// }
// fout << endl;
//}
//void back(int k) {
// if (k > n) {
// Afisare();
// return;
// }
// for (int i = n; i > 0; i--) {
// if (!verif[i]) {
// v[k] = i;
// verif[i] = true;
// back(k + 1);
// verif[i] = false;
// }
// }
//}
//int main() {
// fin >> n;
// back(1);
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("partitiinumar1.in");
//ofstream fout("partitiinumar1.out");
//int n, v[41], suma = 0;
//bool posibil = false;
//void Afisare(int k) {
// for (int i = 1; i <= k; i++) {
// cout << v[i] << " ";
// }
// cout << endl;
// posibil = true;
//}
//void back(int k) {
// if (suma == n) {
// Afisare(k - 1);
// return;
// }
// for (int i = v[k - 1]; i <= n; i+=2) {
// if (suma + i <= n) {
// suma += i;
// v[k] = i;
// back(k + 1);
// suma -= i;
// }
// }
//}
//int main() {
// cin >> n;
// v[0] = 2;
// back(1);
// if (!posibil) {
// cout << "imposibil";
// }
//}
//#include <iostream>
//#include <fstream>
//#include <algorithm>
//using namespace std;
//int n, v[11],rez[11];
//bool verificare[11];
//ifstream fin("permutari2.in");
//ofstream fout("permutari2.out");
//void Afisare() {
// for (int i = 1; i <= n; i++) {
// fout << rez[i] << " ";
// }
// fout << endl;
//}
//void Back(int k) {
// if (k > n) {
// Afisare();
// return;
// }
// for (int i = 1; i <= n; i++) {
// if (!verificare[i]) {
// rez[k] = v[i];
// verificare[i] = true;
// Back(k + 1);
// verificare[i] = false;
// }
// }
//}
//int main() {
// fin >> n;
// for (int i = 1; i <= n; i++) {
// fin >> v[i];
// }
// sort(v + 1, v + n+1);
// Back(1);
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("traseucal.in");
//ofstream fout("traseucal.out");
//int n, m;
//int matrice[12][12];
//int traseu[12][12];
//bool oprire = false;
//int di[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
//int dj[] = { -1, 1, -2, 2, -2, 2, -1, 1 };
//void Afisare() {
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// cout << traseu[i][j] << " ";
// }
// cout << "\n";
// }
//}
//void back(int x, int y, int pas) {
// if (x == n && y == m) {
// Afisare();
// oprire = true;
// return;
// }
// for (int i = 0; i < 8; i++) {
// int nx = x + di[i];
// int ny = y + dj[i];
// if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && matrice[nx][ny] == 0 && traseu[nx][ny] == 0) {
// traseu[nx][ny] = pas + 1;
// back(nx, ny, pas + 1);
// if (oprire) return;
// traseu[nx][ny] = 0;
// }
// }
//}
//
//int main() {
// cin >> n >> m;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// fin >> matrice[i][j];
// }
// }
// traseu[1][1] = 1;
// back(1, 1, 1);
// if (!oprire) {
// traseu[1][1] = 0;
// Afisare();
// }
// return 0;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//int n, m, matrice[11][11], matrice2[11][11], numar = 0,matrice3[11][11];
//bool mat3 = false;
//int di[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
//int dj[] = { -1, 1, -2, 2, -2, 2, -1, 1 };
//ifstream fin("traseucal1.in");
//ofstream fout("traseucal1.out");
//void back(int x, int y,int pas) {
// if (x == n && y == m) {
// if (!mat3) {
// mat3 = true;
// }
// numar++;
// return;
// }
// for (int i = 0; i < 8; i++) {
// int nx= x + di[i];
// int ny= y + dj[i];
// if (nx > 0 && ny > 0 && nx <= n && ny <= m && matrice[nx][ny] == 0 && matrice2[nx][ny] == 0) {
// matrice2[nx][ny] = pas + 1;
// if (!mat3) {
// matrice3[nx][ny] = pas + 1;
// }
// back(nx, ny, pas + 1);
// matrice2[nx][ny] = 0;
// }
// }
//}
//int main() {
// fin >> n >> m;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// fin >> matrice[i][j];
// matrice2[i][j] = 0;
// }
// }
// matrice2[1][1] = 1;
// matrice3[1][1] = 1;
// back(1, 1, 1);
// fout << numar << endl;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// fout << matrice3[i][j] << " ";
// }
// fout << endl;
// }
//}
//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <cmath>
//using namespace std;
//int n, k;
//long long maximilianIoan = 0;
//long long limita;
//vector<int>factori;
//vector<long long>puteri;
//void Descompunere(int n) {
// int i = 2,pas=0;
// bool Add = false;
// do {
// while (n!=1 && n % i == 0) {
// n /= i;
// if (!Add) {
// Add = true;
// factori.push_back(i);
// puteri.push_back(1);
// }
// else {
// puteri[pas]++;
// }
// }
// if (Add) {
// Add = false;
// pas++;
// }
// i++;
// } while (n != 1);
//}
//void GasesteMax(int index, long long valoare) {
// if (valoare > maximilianIoan) {
// maximilianIoan = valoare;
// }
// if (index == puteri.size()) {
// return;
// }
// long long p = factori[index];
// long long max_exp = puteri[index];
// long long f = 1;
// for (int i = 0; i <= max_exp; i++) {
// if (limita / f < valoare) {
// break;
// }
// GasesteMax(index + 1, valoare * f);
// if (limita / p < f) {
// break;
// }
// f *= p;
// }
//
//}
//int main() {
// cin >> n >> k;
// Descompunere(n);
// int max = puteri.size();
// for (int i = 0; i < max; i++) {
// puteri[i] = puteri[i] * n;
// }
// limita = pow(10, k)-1;
// GasesteMax(0, 1);
// cout << maximilianIoan;
//}
//#include <iostream>
//#include <fstream>
//#include <queue>
//using namespace std;
//ifstream fin("lee1.in");
//ofstream fout("lee1.out");
//struct Poz {
// int i, j;
//};
//int n, m, k, i2, j2, distanta[6][7],matrice2[101][101],minim=999999999,current=0,traseuOptim[7],traseuCurent[7];
//bool matrice[101][101], verificare[101][101], st[8];
//Poz v[6];
//int di[4] = { 1,-1,0,0 }, dj[4] = { 0,0,1,-1 };
//void Back(int index,int cont) {
// if (cont == k) {
// if (distanta[index][k + 1] > 0) {
// int cost_total = current + distanta[index][k + 1];
//
// if (cost_total < minim) {
// minim = cost_total;
// for (int i = 0; i < k; i++) {
// traseuOptim[i] = traseuCurent[i];
// }
// }
// }
// return;
// }
// for (int j = 1; j < k+1; j++) {
// if (distanta[index][j] == 0) {
// continue;
// }
// if (!st[j]) {
// st[j] = true;
// current += distanta[index][j];
// traseuCurent[cont] = j;
// Back(j, cont + 1);
// current -= distanta[index][j];
// st[j] = false;
// }
// }
//}
//void BFS(int i,int j, int index) {
// queue<pair<int,int>>q;
// q.push({ i,j });
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// verificare[i][j] = 0;
// }
// }
// verificare[i][j] = true;
// bool oprire = false;
// matrice2[i][j] = 0;
// while (!q.empty() && oprire == false) {
// int x = q.front().first;
// int y = q.front().second;
// q.pop();
// for (int o = 0; o < 4; o++) {
// int new_x=x +di[o];
// int new_y=y +dj[o];
// if (new_x <= n && new_y <= m && new_x > 0 && new_y > 0 && matrice[new_x][new_y] == 0 && verificare[new_x][new_y] == 0) {
// q.push({ new_x,new_y });
// verificare[new_x][new_y] = true;
// matrice2[new_x][new_y] = matrice2[x][y] + 1;
// if (index > 0 && new_x == i2 && new_y == j2) {
// distanta[index][k+1] = matrice2[new_x][new_y];
// }
// for (int iv = 1; iv <= k; iv++) {
// if (new_x == v[iv].i && new_y == v[iv].j) {
// distanta[index][iv] = matrice2[new_x][new_y];
// }
// }
// }
// }
// }
//}
//int main() {
// fin >> n >> m;
// bool x;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// fin >> x;
// matrice[i][j] = x;
// verificare[i][j]=0;
// }
// }
// int i1, j1;
// fin >> i1 >> j1 >> i2 >> j2;
// fin >> k;
// for (int i = 1; i <= k; i++) {
// fin >> v[i].i >> v[i].j;
// }
// for (int i = 1; i < k; i++) {
// for (int j = i + 1; j <= k; j++) {
// if (v[i].i > v[j].i || (v[i].i == v[j].i && v[i].j > v[j].j)) {
// swap(v[i], v[j]);
// }
// }
// }
// BFS(i1, j1, 0);
// for (int j = 1; j <= k; j++) {
// BFS(v[j].i, v[j].j,j);
// }
// Back(0, 0);
// fout << minim << endl;
// fout << i1 << "," << j1 << endl;
// for (int i = 0; i < k; i++) {
// fout << v[traseuOptim[i]].i << "," << v[traseuOptim[i]].j << endl;
// }
// fout << i2 << "," << j2;
//}
//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//ifstream fin("fibonacci3.in");
//ofstream fout("fibonacci3.out");
//int n,cont=0;
//unsigned long long int v[26], sumaMax;
//vector<unsigned long long int>sir;
//void Fibonaci(unsigned long long int a, unsigned long long int b) {
// sir.push_back(b);
// if (a + b <= sumaMax) {
// unsigned long long int r = a + b;
// a = b;
// b = r;
// Fibonaci(a, b);
// }
//}
//void Back(unsigned long long int suma, int index,int elemente) {
// if (index == n) {
// if (elemente > 0) {
// if (binary_search(sir.begin(),sir.end(),suma) ){
// cont++;
// }
// }
// return;
// }
// Back(suma, index + 1,elemente);
// Back(suma + v[index], index + 1, elemente+1);
//}
//
//int main() {
// fin >> n;
// for (int i = 0; i < n; i++) {
// fin >> v[i];
// sumaMax += v[i];
// }
// sir.push_back(0);
// Fibonaci(1, 1);
// Back(0, 0,0);
// fout << cont;
//}
//#include <iostream>
//#include <fstream>
//using namespace std;
//ifstream fin("partitiimultime2.in");
//ofstream fout("partitiimultime2.out");
//int n;
//int st[12],v[12];
//void afisare(int nr_submultimi) {
// int count = 0;
// for (int g = 1; g <= nr_submultimi; g++) {
// for (int i = 1; i <= n; i++) {
// if (st[i] == g) {
// fout << i;
// count++;
// }
// if (v[g] == count) {
// count = 0;
// break;
// }
// }
// fout << '*';
// }
// fout << '\n';
//}
//void back(int k, int max_so_far) {
// if (k > n) {
// afisare(max_so_far);
// return;
// }
// for (int i = 1; i <= max_so_far + 1; i++) {
// st[k] = i;
// v[i]++;
// int noul_max = (i > max_so_far) ? i : max_so_far;
// back(k + 1, noul_max);
// v[i]--;
// }
//}
//
//int main() {
// if (fin >> n) {
// back(1, 0);
// }
// return 0;
//}
//#include <iostream>
//#include <algorithm>
//using namespace std;
//int n, m,c;
//int st[17],verif[17];
//void Afisare() {
// for (int q = 1; q <= c; q++) {
// cout << "{";
// int count = 0;
// for (int i = 1; i <= n; i++) {
// if (st[i] == q) {
// cout << i;
// count++;
// if (count + 1 <= m) {
// cout << ',';
// }
// }
// }
// cout << "}";
// if (q + 1 <= c) {
// cout << "U";
// }
// }
// cout << '\n';
//}
//void Back(int k,int maxim) {
// if (k > n) {
// Afisare();
// return;
// }
// int limita = min(maxim + 1, c);
// for (int i = 1; i <= limita; i++) {
// if (verif[i] < m) {
// st[k] = i;
// verif[i]++;
// Back(k + 1,max(maxim,i));
// verif[i]--;
// }
// }
//}
//int main() {
// cin >> n>>m;
// if (n % m != 0) {
// cout << "IMPOSIBIL";
// return 0;
// }
// c = n / m;
// Back(1,0);
//}
#/*include <fstream>
#include <vector>
using namespace std;
ifstream fin("immortal.in");
ofstream fout("immortal.out");
struct Mutare {
int r1, c1, r2, c2;
};
int n, m, I;
int board[22][22];
vector<Mutare> sol;
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
bool back(int rem) {
if (rem == 1) {
return true;
}
for (int r = 1; r <= n; ++r) {
for (int c = 1; c <= m; ++c) {
if (board[r][c] == 1) {
for (int d = 0; d < 4; ++d) {
int mr = r + dx[d];
int mc = c + dy[d];
int nr = r + 2 * dx[d];
int nc = c + 2 * dy[d];
if (nr >= 1 && nr <= n && nc >= 1 && nc <= m) {
if (board[mr][mc] == 1 && board[nr][nc] == 0) {
board[r][c] = 0;
board[mr][mc] = 0;
board[nr][nc] = 1;
sol.push_back({ r, c, nr, nc });
if (back(rem - 1)) {
return true;
}
sol.pop_back();
board[r][c] = 1;
board[mr][mc] = 1;
board[nr][nc] = 0;
}
}
}
}
}
}
return false;
}
int main() {
fin >> n >> m >> I;
for (int i = 0; i < I; ++i) {
int r, c;
fin >> r >> c;
board[r][c] = 1;
}
back(I);
for (const auto& mtr : sol) {
fout << mtr.r1 << " " << mtr.c1 << " " << mtr.r2 << " " << mtr.c2 << "\n";
}
return 0;
}*/
//#include <iostream>
//#include <fstream>
//#include <vector>
//#include <string>
//#include <sstream>
//#include <algorithm>
//using namespace std;
//ifstream fin("mesaj.in");
//ofstream fout("mesaj.out");
//int maiMare(int numar, vector<vector<int>>& matrice, int final) {
// int max = numar;
// for (int i = numar + 1; i < final; i++) {
// if (matrice[i] > matrice[max]) {
// max = i;
// }
// }
// return max;
//}
//int main() {
// bool gasit = false;
// vector<bool> verif(30005, false);;
// int contor = 0,final=0,contor_copie=0;
// vector<vector<int>>matrice;
// vector<int>vector_pt_mare;
// vector<string>v;
// string prop,cuvant,propozitie_finala="";
// while (getline(fin, prop)) {
// v.push_back(prop);
// }
// if (v.size() == 1) {
// fout << count(v[0].begin(), v[0].end(), ' ') + 1 << '\n';
// stringstream qq(v[0]);
// while (qq >> cuvant) {
// for (int i = cuvant.size() - 1; i >= 0; i--) {
// fout << cuvant[i];
// }
// fout << " ";
// }
// return 0;
// }
// for (int i = v.size()-1; i>0; i--) {
// if (gasit) {
// break;
// }
// int numarare = 0;
// stringstream ss(v[i]);
// stringstream aa(propozitie_finala);
// if (!gasit) {
// stringstream qq(v[0]);
// while (ss >> prop) {
// qq >> cuvant;
// if (cuvant == prop) {
// if (!gasit) {
// gasit = true;
// }
// contor++;
// propozitie_finala += (cuvant + " ");
// verif[numarare] = true;
// final = numarare;
// }
// numarare++;
// }
// if (gasit) {
// matrice.resize(contor, vector<int>(0));
// for (int x = 0; x < contor; x++) {
// matrice[x].push_back(i);
// }
// }
// }
// }
// if (!gasit) {
// fout << count(v[0].begin(), v[0].end(), ' ') + 1 << '\n';
// stringstream qq(v[0]);
// while (qq >> cuvant) {
// for (int i = cuvant.size() - 1; i >= 0; i--) {
// fout << cuvant[i];
// }
// fout << " ";
// }
// return 0;
// }
// for (int i = v.size() - 1; i > 0; i--) {
// int numarare = 0;
// contor_copie = 0;
// stringstream ss(v[i]);
// stringstream aa(propozitie_finala);
// aa >> cuvant;
// while (ss >> prop) {
// if (cuvant == prop && verif[numarare] &&contor_copie<contor && numarare<=final) {
// matrice[contor_copie].push_back(i);
// }
// if (verif[numarare]) {
// aa >> cuvant;
// contor_copie++;
// }
// numarare++;
// }
// }
// v.clear();
// v.resize(contor);
// stringstream aa(propozitie_finala);
// int numarare_pt_v = 0;
// while (aa >> cuvant) {
// v[numarare_pt_v] = cuvant;
// numarare_pt_v++;
// }
// for (int i = 0; i < contor; i++) {
// int c = maiMare(i, matrice, contor);
// swap(v[i], v[c]);
// swap(matrice[i], matrice[c]);
// }
// fout << contor << '\n';
// for (int i = 0; i < v.size(); i++) {
// for (int j = v[i].size() - 1; j >= 0; j--) {
// fout << v[i][j];
// }
// fout << " ";
// }
//}
//#include <iostream>
//#include <fstream>
//#include <vector>
//using namespace std;
//ifstream fin("unuzero.in");
//ofstream fout("unuzero.out");
//int m, k, q, dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
//vector<vector<bool>>verificare;
//void DFS(vector<vector<bool>>&matrice,int x,int y,int n) {
// verificare[x][y] = 1;
// for (int i = 0; i < 4; i++) {
// int cx = x + dx[i];
// int cy = y + dy[i];
// if (cx > 0 && cy > 0 && cx <= n && cy <= m && matrice[cx][cy] == 1 && verificare[cx][cy]==0) {
// DFS(matrice, cx, cy,n);
// }
// }
//}
//int main() {
// int n;
// fin >> n >> m >> k >> q;
// int poz, i = 1, j = 0;
// int contor = 0, contor2 = 0;
// vector<vector<bool>>matrice(n + 1, vector<bool>(m + 1)), matrice2(n * 2 + 1, vector<bool>(m + 1));
// while (q--) {
// fin >> poz;
// while (poz > m) {
// poz -= m;
// i++;
// }
// j = poz;
// matrice[i][j] = 1;
// matrice2[i][j] = 1;
// matrice2[i + n][j] = 1;
// i = 1;
// j = 0;
// }
// if (k == 1) {
// verificare.resize(matrice.size(), vector<bool>(matrice[0].size(), 0));
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// if (matrice[i][j] == 1 && verificare[i][j] == 0) {
// contor++;
// DFS(matrice, i, j,n);
// }
// }
// }
// fout << contor;
// }
// else {
// verificare.resize(matrice.size(), vector<bool>(matrice[0].size(), 0));
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= m; j++) {
// if (matrice[i][j] == 1 && verificare[i][j] == 0) {
// contor++;
// DFS(matrice, i, j,n);
// }
// }
// }
// verificare.clear();
// verificare.resize(matrice2.size(), vector<bool>(matrice2[0].size(), 0));
// for (int i = 1; i <= 2 * n; i++) {
// for (int j = 1; j <= m; j++) {
// if (matrice2[i][j] == 1 && verificare[i][j] == 0) {
// contor2++;
// DFS(matrice2, i, j,2*n);
// }
// }
// }
// fout << contor + (contor2 - contor) * (k - 1);
// }
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//void Merge(vector<int>& v, int st, int mijloc, int dr);
//void MergeSort(vector<int>&v,int st,int dr) {
// if (st >= dr) {
// return;
// }
// int mijloc = (st + dr) / 2;
// MergeSort(v, st, mijloc);
// MergeSort(v, mijloc + 1, dr);
// Merge(v, st,mijloc, dr);
//}
//void Merge(vector<int>&v, int st,int mijloc, int dr) {
// int i = st, j = mijloc+1;
// vector<int>temporar;
// while (i <= mijloc && j <= dr) {
// if (v[i] < v[j]) {
// temporar.push_back(v[i]);
// i++;
// }
// else {
// temporar.push_back(v[j]);
// j++;
// }
// }
// while (i <= mijloc) {
// temporar.push_back(v[i]);
// i++;
// }
// while ( j <= dr) {
// temporar.push_back(v[j]);
// j++;
// }
// for (int poz = 0; poz < temporar.size(); poz++) {
// v[st + poz] = temporar[poz];
// }
//}
//int main() {
// vector<int> v(10);
// v = { 2,6,1,8,9,3,4,7,5,10 };
// MergeSort(v, 0,9);
// for (auto i : v) {
// cout << i << " ";
// }
//}
//#include <iostream>
//#include <vector>
//using namespace std;
//int Pivot(vector<int>& v, int start, int end);
//void QuickSort(vector<int>& v, int start, int end) {
// if (end <= start) {
// return;
// }
// int pivot = Pivot(v, start, end);
// QuickSort(v, start, pivot-1);
// QuickSort(v, pivot + 1, end);
//}
//int Pivot(vector<int>& v, int start, int end) {
// int i = start - 1;
// int pivot = v[end];
// for (int j = start; j < end; j++) {
// if (v[j] < pivot) {
// i++;
// swap(v[i], v[j]);
// }
// }
// i++;
// swap(v[i], v[end]);
// return i;
//}
//int main() {
// vector<int> v(10);
// v = { 2,6,1,8,9,3,4,7,5,10 };
// QuickSort(v,0,9);
// for (auto i : v) {
// cout << i << " ";
// }
//}
//#include <vector>
//#include <iostream>
//#include <fstream>
//using namespace std;
//int n, m;
//vector<int>sir, ait;
//void Build(int node, int st, int dr) {
// if (st == dr) {
// ait[node] = sir[st];
// return;
// }
// int mijloc = (st + dr) / 2;
// Build(node * 2, st, mijloc);
// Build(node * 2+1, mijloc+1, dr);
// ait[node] = ait[2 * node] + ait[2 * node + 1];
//}
//void Update(int nod, int st, int dr, int poz, int val) {
// if (st == dr) {
// ait[nod] = val;
// return;
// }
// int mijloc = (st + dr) / 2;
// if (poz <= mijloc) {
// Update(nod * 2, st, mijloc, poz, val);
// }
// else {
// Update(nod * 2, mijloc+1, dr, poz, val);
// }
// ait[nod] = ait[nod * 2] + ait[nod * 2+1];
//}
//int query(int node, int st, int dr, int L, int R) {
// if (L <= st && R >= dr) {
// return ait[node];
// }
// else if (dr<L || st>R) {
// return 0;
// }
// int mijloc = (st + dr) / 2;
// return query(node * 2, st, mijloc, L, R) + query(node * 2, mijloc + 1, dr, L, R);
//}
//int main() {
// cin >> n >> m;
// sir.resize(n);
// ait.resize(4 * n);
// Build(1, 1, n);
//}
//#include <iostream>
//#include <fstream>
//#include <vector>
//using namespace std;
//ifstream fin("arbint.in");
//ofstream fout("arbint.out");
//int n, m;
//vector<int>sir, ait;
//void build(int nod, int st, int dr) {
// if (st == dr) {
// ait[nod] = sir[st];
// return;
// }
// int mijloc = (st + dr) / 2;
// build(nod * 2, st, mijloc);
// build(nod * 2+1, mijloc + 1, dr);
// ait[nod] = max(ait[2 * nod], ait[2 * nod + 1]);
//}
//void Update(int nod, int st, int dr, int poz, int val) {
// if (st == dr) {
// ait[nod] = val;
// return;
// }
// int mijloc = (st + dr) / 2;
// if (poz <= mijloc) {
// Update(nod * 2, st, mijloc, poz, val);
// }
// else {
// Update(nod * 2+1, mijloc + 1, dr, poz, val);
// }
// ait[nod] = max(ait[2 * nod], ait[2 * nod + 1]);
//}
//int query(int nod, int st, int dr, int L, int R) {
// if (L <= st && R >= dr) {
// return ait[nod];
// }
// else if (st > R || dr < L) {
// return 0;
// }
// int mijloc = (st + dr) / 2;
// return max(query(nod * 2, st, mijloc, L, R), query(nod * 2+1, mijloc + 1, dr, L, R));
//}
//int main() {
// fin >> n >> m;
// sir.resize(n+1);
// ait.resize((n + 1) * 4);
// for (int i = 1; i <= n; i++) {
// fin >> sir[i];
// }
// build(1, 1, n);
// int op,a,b;
// while (m--) {
// fin >> op >> a>>b;
// if (op == 0) {
// fout << query(1, 1, n, a, b) << '\n';
// }
// else {
// Update(1, 1, n, a, b);
// }
// }
//}
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("datorii.in");
ofstream fout("datorii.out");
int n, m;
vector<int>sir, ait;
void Build(int nod, int st, int dr) {
if (st == dr) {
ait[nod] = sir[st];
return;
}
int mijloc = (st + dr) / 2;
Build(nod * 2, st, mijloc);
Build(nod * 2+1, mijloc + 1, dr);
ait[nod] = ait[nod * 2] + ait[nod * 2 + 1];
}
void Update(int nod, int st, int dr, int poz, int val) {
if (st == dr) {
ait[nod] -=val;
return;
}
int mijloc = (st + dr) / 2;
if (poz < mijloc) {
Update(nod * 2, st, mijloc, poz, val);
}
else {
Update(nod * 2 + 1, mijloc + 1, dr, poz, val);
}
ait[nod] = ait[nod * 2] + ait[nod * 2 + 1];
}
int query(int nod, int st, int dr, int L, int R) {
if (L <= st && R >= dr) {
return ait[nod];
}
else if (st > R || dr < L) {
return 0;
}
int mijloc = (st + dr) / 2;
return query(nod * 2, st, mijloc, L, R) + query(nod * 2 + 1, mijloc + 1, n, L, R);
}
int main() {
fin >> n >> m;
sir.resize(n+1);
ait.resize(4 * (n+1));
for (int i = 1; i <= n; i++) {
fin >> sir[i];
}
int optiune;
Build(1, 1, n);
while (m--) {
fin >> optiune;
if (optiune) {
int P, Q;
fin >> P >> Q;
fout << query(1, 1, n, P, Q) << '\n';
}
else {
int T, V;
fin >> T >> V;
Update(1, 1, n, T, V);
}
}
}
Joita Cristian gilbus