void getCanonicalMatrix(vvd& a, vd& b, vd& c, const vc& sign, const vc& type)
{
    vvd a1;
    vd b1;
    vd c1 = c;

    for (size_t i = 0; i < type.size(); ++i)
    {
        if (type[i] == '<')
        {
            a1.push_back(a[i]);
            b1.push_back(b[i]);
        }
        if (type[i] == '>')
        {
            a1.push_back(a[i]);
            for (auto& j : a1.back())
            {
                j = -j;
            }
            b1.push_back(-b[i]);
        }
        if (type[i] == '=')
        {
            a1.push_back(a[i]);
            b1.push_back(b[i]); 
            a1.push_back(a[i]);
            for (auto& j : a1.back())
            {
                j = -j;
            }
            b1.push_back(-b[i]);
        }
    }

    for (int i = (int)sign.size() - 1; i >= 0; --i)
    {
        if (sign[i] == '0')
        {
            for (auto& v : a1)
            {
                v.insert(v.begin() + i + 1, -v[i]);
            }
            c1.insert(c1.begin() + i + 1, -c1[i]);
        }
    }

    a = a1;
    b = b1;
    c = c1;    
}

//el vector a debe ser de una longitud potencia de 2
//mult = 1 FFt
//mult = -1 lo usa el inv_fft
//el vector a debe ser de una longitud potencia de 2
//mult = 1 FFt
//mult = -1 lo usa el inv_fft
vc fft(vc &a){

  int n = a.size();
  vc y(n);
  int lg = 0;

  while((1<<lg)<n) lg++;

  for(int i=0;i<n;i++){
    y[rev(i,lg)]=a[i];
  }

  for(int i = 1; i <= lg; i++){
    int m = 1<<i;
    for(int k=0;k<n;k+=m){
        for(int j=0;j<m/2;j++){
            double angle = (mult*j*2.0*M_PI)/m;
            comp w = comp(cos(angle),sin(angle));;
            comp t = w * y[k+j+m/2];
            comp u = y[k+j];
            y[k+j]=u+t;
            y[k+j+m/2]=u-t;
        }
    }
  }
  return y; 
}

void printResult(const linearProgramming::SlackForm& condition, const vc& sign, bool f = true)
{
    auto vars = condition.getResult();
    for (size_t i = 0, k = 0; i < sign.size(); ++i)
    {
        if (sign[i] == '+')
        {
            cout << vars[k++];
        }
        else
        {
            cout << vars[k] - vars[k + 1] << endl;
        }
        cout << "\t";
    }
    cout << endl;
	if (f)
	{
		cout << "MAX = " << condition.getV() << endl;
	}
	else
	{
		cout << "MAX = " << -condition.getV() << endl;
	}
}

int main(void)
{
    int num;
    cin >> num;
    board = vcc (num, vc (3, 0));
    for (int i = 0; i < num; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        board[i][0] = x;
        board[i][1] = y;
        board[i][2] = z;
        sort(board[i].begin(), board[i].end(), wayToSort);
    }
    sort(board.begin(), board.end(), newComp);
    for (int i = 0; i < board.size(); i++) {
        list.push_back(board[i][0] * board[i][1] * board[i][2]);
    }
    /*for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[i].size(); j++) {
            cout << board[i][j] << " ";
        }cout << list[i] << endl;
    }*/
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        vc foo = {x,y,z};
        sort(foo.begin(), foo.end(), wayToSort);
        int pro = process(foo);
        if (pro)cout << pro << endl;
        else cout << "Item does not fit." << endl;
    }
}

bool check(vc ckset){
    int qw = 0;
    for (int i = 0; i < ckset.size()-1; i++) {
        if (ckset[i]%12 == 0 || ckset[i] == 12) {
            qw++;
        }
    }
    if (qw == 9) {
        return true;
    }
    return false;
}

void best(int index, string a, string b, vc s, vector<bool> limits){
    cout << "index: " << index << " a: " << a << " b: " << b<< " ";
    for (int w = 0; w < s.size(); w++) {
        cout << s[w];
    }
    cout << endl;
    if (s.size() < lim) {
    if (a == b) {
        cout << "*************************************" <<endl;
        bool p = true;
        for (int j = 0; j < num; j++) {
            if (limits[j] == false) {
                p = false;
                break;
            }
        }
        if (p == true) {
            cout << s.size() << endl;
            for (int q = 0; q < s.size(); q++) {
                cout << s[q] << endl;
            }
            return;
        }
       
    }
    int jkl = 0;
    for (int i = 0; i < min(a.length(), b.length()); i++) {
        if (a[i] != b[i]) {
            jkl++;
        }
    }
    if (jkl == 0) {
    for (int i = 0; i < num; i++) {
        if (b == "abaaaaaa") {
            cout << "yyyyyyyyyyyyyy" <<endl;
        }
        //cout << i <<endl;
        s.push_back(i);
        limits[i]= true;
        a+=str[0][i];
        b+=str[1][i];
        if (a == "abaaaaaab" || b == "abaaaaaab")
            cout << "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%";
        best(i, a, b, s, limits);
        limits[i] = false;
        s.pop_back();
    }
    }}
        
}

vc transform(int code, vc vec){
	int size = vec.size();
	vc initial  = vec;
	switch(code){
		case 1:
			for (int i=0; i<size; ++i){
				for (int j=0; j<size; ++j){
					vec[j][size-i-1] = initial[i][j];
				}
			}
			return vec;
			break;
		case 4:
			for (int i=0; i<size; ++i){
				for (int j=0; j<size; ++j){
					vec[i][size-j-1] = initial[i][j];
				}
			}
			return vec;
			break;
		case 3:
			for (int i=0; i<size; ++i){
				for (int j=0; j<size; ++j){
					vec[size-j-1][i] = initial[i][j];
				}
			}
			return vec;
			break;
		case 2:
			for (int i=0; i<size; ++i){
				for (int j=0; j<size; ++j){
					vec[size-i-1][size-j-1] = initial[i][j];
				}
			}
			return vec;
			break;
	}
}

//se encarga de evaluar un polinomio v en el valor val
//los coeficientes deben estar ordenados en orden creciente
// de la potencia de X
comp eval(vc v, comp val){
    comp s;
    for(int i=0;i<v.size();i++) 
        s+=pow(val,i)*v[i];
    return s;
}

void recurse(int num, string a, string b){
    if (!u) {
        return;
    }
    if (a == b && a != "") {
        //cout << a << endl;
        u=false;
        cout << order.size() << endl;
        for (int i = 0; i < order.size(); i++) {
            cout << order[i] << endl;
        }
        return;
    }
    if (num >= m) {
        return;
    }
    for (int i = 0; i < a1.size(); i++) {
        string p = a + a1[i];
        string q = b + b2[i];
        int least = min(p.length(), q.length());
        if (p.substr(0, least) == q.substr(0, least)) {
            order.push_back(i+1);
            recurse(num+1, p, q);
            order.pop_back();
        }
    }
}

int main(void)
{
    int num;
    cin >> num;
    
    for (int i = 0; i < num; i++) {
        int temp;
        cin >> temp;
        board.push_back(temp);
    }
    sort(board.begin(), board.end());
    cout << binary(0, (int) board.size()-1, 17);
}

int main ()
{
    srand (time (0));

    freopen (NAME".in", "r", stdin);
    freopen (NAME".out", "w", stdout);

    scanf ("%d", &n);

    primes.resize (n + 1, 1);
    primes [0] = primes [1] = 0;

    for (int i = 2; i * i <= n; i++)
        if (primes [i] && (i * 1ll * i <= n))
            for (int j = i * i; j <= n; j += i)
                primes [j] = 0;

    int ans = 0;
    int res = 2;

    for (int i = 1; i <= n; i++)
    {
        ans += primes [i];
        res = primes [i] ? i : res;
    }

    cout << ans << endl;
    cout << res << endl;

    return 0;
}

int main ()
{
    srand (time (0));

    freopen (NAME".in", "r", stdin);
    freopen (NAME".out", "w", stdout);

    scanf ("%d %d", &n, &m);
    g.resize (n + 1);
    used.resize (n + 1, 0);

    for (int i = 0; i < m; i++)
    {
        int x, y;
        scanf ("%d %d", &x, &y);
        g [x].pb (y);
        g [y].pb (x);
    }

    int ans = 0;

    for (int i = 1; i <= n; i++)
        if (!used [i])
        {
            ans++;
            dfs (i);
        }

    printf ("%d\n", ans);

    return 0;
}

int main(void)
{
    int num;
    cin >> num;
    while (num--) {
        int s;
        cin >> s;
        for (int k = 0; k < s; k++) {
            int temp;
            cin >> temp;
            trains.push_back(temp);
            sorted.push_back(temp);
        }
        sort(sorted.begin(), sorted.end());
        int count = 0;
        while (sorted != trains) {
            for (int i = 0; i+1 < trains.size(); i++) {
                if (trains[i] > trains[i+1]) {
                    int t= trains[i+1];
                    trains[i+1] = trains[i];
                    trains[i] = t;
                    count++;
                }
            }
        }
        cout << "Optimal train swapping takes "<< count << " swap(s)." <<endl;
        trains.clear();
        sorted.clear();
    }
    
}

int main(void)
{
    int cows, stalls;
    cin >> cows >> stalls;
    vector<bool> grid (stalls+1, false);
    umb.push_back(0);
    for (int i = 0; i < cows; i++) {
        int temp;
        cin >> temp;
        list.push_back(temp);
    }
    sort(list.begin(), list.end());
    for (int i = 0; i < stalls; i++) {
        int temp;
        cin >> temp;
        umb.push_back(temp);
    }
}

int main(void)
{
    int num;
    cin >> num;
    for (int i = 0; i < num; i++) {
        int temp;
        cin >> temp;
        if (temp == 0) {
            list.pop_back();
        }
        else list.push_back(temp);
    }
    int sum = 0;
    for (int i = 0; i < list.size(); i++) {
        sum += list[i];
    }
    cout << sum;
}

int main(void)
{
    int test;
    cin >> test;
    while (test--) {
        int num;
        cin >> num;
        for (int i = 0; i < num; i++) {
            int temp;
            cin >> temp;
            mount.push_back(temp);
        }
        lake.push_back(0);
        cout << check() << endl;
        lake.clear();
        mount.clear();
        branch.clear();
    }
}

int main(void)
{
    int num;
    cin >> num;
    
    for (int i = 0; i < num; i++) {
        int temp;
        cin >> temp;
        list.push_back(temp);
    }
    cout << "enter: ";
    int x, y;
    cin >> x >> y;
    tree = vector<int> (4*list.size(), 0);
    build(1,0,list[list.size()-1]);
    for (int i = 0; i < tree.size(); i++) {
        cout << tree[i] << endl;
    }
}

int main(void)
{
    freopen("censor.in", "r", stdin);
    freopen("censor.out", "w", stdout);
    cin >> str >> sub;
    
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == sub[0]) {
            list.push_back(i);
        }
    }
    
    while (1) {
        bool p = false;
    for (int i = 0; list[i] + sub.length() <= str.length() && i < list.size(); i++) {
            if (str.substr(list[i], sub.length()) == sub){
                p = true;
                str.erase(list[i], sub.length());
                i--;
            }
    }
        if (!p) {
            break;
        }
    }
    /*for (int i = 0; i + sub.length() <= str.length(); i++) {
        if (str[i] == sub[0]) {
            if (str.substr(i, sub.length()) == sub){
                str.erase(i, sub.length());
                if (list.size() > 0) {
                    i = -list.top() -1;
                    list.pop();
                    continue;
                }
            }
            else list.push(-i);
        }
    }*/
    cout << str;
}

int main(void)
{
    input;
    int num;
    cin >> num;
    

    for (int i = 0; i < num; i++) {
        int temp;
        cin >> temp;
        list.push_back(temp);
    }
}

int main(void)
{
    int num;
    cin >> num;
    
    for (int i = 0; i < num; i++) {
        int temp;
        cin >> temp;
        board.push_back(temp);
    }
    sort(board.end(), board.begin());
    
    while (1) {
        int cur = board[0]+1;
        for (int i = 0; i < board.size(); i++) {
            if(board[i] < cur){
                cur = board[i];
                board[i] = -5;
            }
            else if (<#condition#>)
        }
    }
}