acwing.cpp

浏览该文件的文档.

#include "acwing.h"
#include "templates.h"
 
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
using namespace std;
 
namespace acwing {
    int acwing1::main(istream &cin, ostream &cout) {
        int a;
        int b;
        cin >> a >> b;
        cout << a + b;
        return 0;
    }
 
    int acwing4200::main(istream &cin, ostream &cout) {
        int p1;
        int p2;
        int p3;
        int p4;
        int a;
        int b;
        cin >> p1 >> p2 >> p3 >> p4 >> a >> b;
        int min       = p1;
        min           = p2 < min ? p2 : min;
        min           = p3 < min ? p3 : min;
        min           = p4 < min ? p4 : min;
        const int ans = min - a < b - a + 1 ? min - a : b - a + 1;
        cout << (ans < 0 ? 0 : ans);
        return 0;
    }
 
    int acwing4201::main(istream &cin, ostream &cout) {
        int number;
        cin >> number;
        int copy = number;
        int len  = 0;
        while(copy != 0) {
            copy /= 10;
            len++;
        }
        auto arr = vector<int>(len);
        copy     = number;
        for(int i = len - 1; i >= 0; i--) {
            arr[i] = copy % 10;
            copy /= 10;
        }
 
        int sum = static_cast<int>(pow(2, len));
        for(int i = 0; i < len; i++) {
            if(arr[i] > 1) {
                break;
            }
            if(arr[i] == 0) {
                sum -= static_cast<int>(pow(2, len - i - 1));
            }
        }
        cout << --sum;
        return 0;
    }
 
    int acwing608::main(istream &cin, ostream &cout) {
        int a;
        int b;
        int c;
        int d;
        cin >> a >> b >> c >> d;
        cout << "DIFERENCA = " << a * b - c * d;
        return 0;
    }
 
    int acwing604::main(istream &cin, ostream &cout) {
        const double pi = 3.14159;
        double r;
        cin >> r;
        cout << "A=" << setiosflags(ios::fixed) << setprecision(4) << pi * r * r;
        return 0;
    }
 
    int acwing606::main(istream &cin, ostream &cout) {
        double a;
        double b;
        cin >> a >> b;
        cout << "MEDIA = " << setiosflags(ios::fixed) << setprecision(5) << (a * 3.5 + b * 7.5) / 11;
        return 0;
    }
 
    int acwing609::main(istream &cin, ostream &cout) {
        int a;
        double b;
        double c;
        cin >> a >> b >> c;
        cout << "NUMBER = " << a << endl
             << "SALARY = U$ " << setiosflags(ios::fixed) << setprecision(2) << b * c;
        return 0;
    }
 
    int acwing615::main(istream &cin, ostream &cout) {
        int x;
        float y;
        cin >> x >> y;
        cout << setiosflags(ios::fixed) << setprecision(3) << static_cast<float>(x) / y << " km/l";
        return 0;
    }
 
    int acwing616::main(istream &cin, ostream &cout) {
        double x1;
        double y1;
        double x2;
        double y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << setiosflags(ios::fixed) << setprecision(4) << sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
        return 0;
    }
 
    int acwing653::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        cout << n << endl;
        int arr[] = {100, 50, 20, 10, 5, 2, 1};
        for(const int i: arr) {
            cout << n / i << " nota(s) de R$ " << i << ",00";
            if(i != 1) {
                cout << endl;
            }
            n %= i;
        }
        return 0;
    }
 
    int acwing4203::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        int count0 = 0;
        int count1 = 0;
        for(const char c: str) {
            if(c == '1') {
                count1++;
                count0 = 0;
            } else {
                count0++;
                count1 = 0;
            }
            if(count1 == 7 || count0 == 7) {
                cout << "YES";
                return 0;
            }
        }
        cout << "NO";
        return 0;
    }
 
    int acwing4204::main(istream &cin, ostream &cout) {
        int n;
        const int N = 1010;
        auto *g     = new int *[N];
        for(int i = 0; i < N; i++) {
            g[i] = new int[N];
            for(int j = 0; j < N; j++) {
                g[i][j] = 0;
            }
        }
        cin >> n;
        for(int i = 1; i <= n; i++) {
            g[1][i] = i - 1;
            g[i][1] = i - 1;
        }
        for(int i = 2; i < n; i++) {
            for(int j = 2; j < n; j++) {
                if(i == j) {
                    g[i][j] = 0;//对角线为0
                } else {
                    if(g[i][j - 1] == 0) {
                        //在0后面一格
                        g[i][j] = g[i - 1][j] + 1;//上面一格的值+1
                    } else {
                        //否则
                        g[i][j] = g[i][j - 1] + 1;//前面一格的值+1
                    }
                    if(g[i][j] == n) {
                        //达到上限
                        g[i][j] = 1;//回归到1
                    }
                }
            }
        }
        for(int i = 1; i < n; i++) {
            set<int> s;
            for(int j = 1; j < n; j++) {
                s.insert(g[i][j]);
            }
            for(int j = 0; j < n; j++) {
                if(!s.contains(j)) {
                    g[i][n] = g[n][i] = j;//补最后一列和最后一行的值
                }
            }
        }
 
        //输出
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                cout << g[i][j];
                if(j != n) {
                    cout << " ";
                }
            }
            if(i != n) {
                cout << endl;
            }
        }
        for(int i = 0; i < N; i++) {
            delete[] g[i];
        }
        delete[] g;
        return 0;
    }
 
    int acwing2058::main(istream &cin, ostream &cout) {
        string n2;
        string n3;
        cin >> n2 >> n3;
        auto s = set<long long>();
 
        for(int i = 0; i < n2.length(); i++) {
            long long val = 0;
            for(int j = 0; j < n2.length(); j++) {
                bool bit = n2[j] != '0';
                if(j == i) {
                    bit = !bit;
                }
                if(bit) {
                    val += static_cast<long long>(pow(2, n2.size() - j - 1));
                }
            }
            s.insert(val);
        }
 
        for(int n = 1; n <= 2; n++) {
            for(int i = 0; i < n3.length(); i++) {
                long long val = 0;
                for(int j = 0; j < n3.length(); j++) {
                    int v = n3[j] - '0';
                    if(i == j) {
                        v += n;
                        v %= 3;
                    }
                    val += static_cast<long long>(v * pow(3, n3.size() - j - 1));
                }
                if(s.contains(val)) {
                    cout << val;
                    return 0;
                }
                s.insert(val);
            }
        }
        return 0;
    }
 
    int acwing654::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        const int s = n % 60;
        n /= 60;
        const int m = n % 60;
        n /= 60;
        const int h = n;
        cout << h << ":" << m << ":" << s;
        return 0;
    }
 
    int acwing605::main(istream &cin, ostream &cout) {
        int a;
        int b;
        cin >> a >> b;
        cout << "PROD = " << a * b;
        return 0;
    }
 
    int acwing2041::main(istream &cin, ostream &cout) {
        auto *haystack = new int[1000010];
        memset(haystack, 0, 1000010 * sizeof *haystack);
        int n;
        int k;
        cin >> n >> k;
        for(int i = 0; i < k; i++) {
            int a;
            int b;
            cin >> a >> b;
            haystack[a]++;
            haystack[b + 1]--;
        }
        for(int i = 1; i <= n; i++) {
            haystack[i] += haystack[i - 1];
        }
        sort(haystack + 1, haystack + n + 1);
        cout << haystack[(n + 1) / 2];
        delete[] haystack;
        return 0;
    }
 
    namespace acwing2060 {
        int acwing2060::main(istream &cin, ostream &cout) {
            char cowhide[55][55]{};
            bool occupy[55][55]{};
            auto edge = unordered_set<point, pointhash, pointequal>();
            int n;
            int m;
            cin >> n >> m;
            bool flag = true;
            point first{};
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    cin >> cowhide[i][j];
                    if(flag && cowhide[i][j] == 'X') {
                        occupy[i][j] = true;
                        first        = point(i, j);
                        flag         = false;
                    } else {
                        occupy[i][j] = false;
                    }
                }
            }
 
            flood(first, occupy, &edge, cowhide, n, m);
 
            int count     = 0;
            auto nextedge = unordered_set<point, pointhash, pointequal>();
            while(true) {
                for(const auto p: edge) {
                    point nexts[] = {
                            point(p.x + 1, p.y), point(p.x - 1, p.y), point(p.x, p.y + 1),
                            point(p.x, p.y - 1)};
                    for(auto next: nexts) {
                        if(0 <= next.x && next.x <= n && 0 <= next.y && next.y <= m && !occupy[next.x][next.y]) {
                            if(cowhide[next.x][next.y] == 'X') {
                                cout << count;
                                return 0;
                            }
                            cowhide[next.x][next.y] = 'X';
                            occupy[next.x][next.y]  = true;
                            nextedge.insert(next);
                        }
                    }
                }
                count++;
                edge     = nextedge;
                nextedge = unordered_set<point, pointhash, pointequal>();
            }
        }
 
        size_t pointhash::operator()(const point &p) const { return p.x * 50 + p.y; }
 
        bool pointequal::operator()(const point &p1, const point &p2) const { return p1.x == p2.x && p1.y == p2.y; }
 
        void
        flood(point first, bool occupy[55][55], unordered_set<point, pointhash, pointequal> *edge, char cowhide[55][55],
              int n, int m) {
            auto que      = queue<point>();
            const auto eq = pointequal();
            que.push(first);
            while(!que.empty()) {
                auto p = que.front();
                if(!eq(p, first) && occupy[p.x][p.y]) {
                    que.pop();
                    continue;
                }
                occupy[p.x][p.y] = true;
                point nexts[]    = {point(p.x + 1, p.y), point(p.x - 1, p.y), point(p.x, p.y + 1), point(p.x, p.y - 1)};
                for(auto next: nexts) {
                    if(0 <= next.x && next.x <= n && 0 <= next.y && next.y <= m && !occupy[next.x][next.y]) {
                        if(cowhide[next.x][next.y] == 'X') {
                            que.push(next);
                        } else {
                            edge->insert(p);
                        }
                    }
                }
                que.pop();
            }
        }
    }// namespace acwing2060
 
    namespace acwing2019 {
        int acwing2019::main(istream &cin, ostream &cout) {
            int n;
            int start_x;
            int start_y;
            auto *field = new int *[N + 10];
            for(int i = 0; i < N + 10; i++) {
                field[i] = new int[N + 10];
                memset(field[i], 0, (N + 10) * sizeof(int));
            }
            //int field[N + 10][N + 10];   //记录状态。0=没有 1=墙 2=已经被搜索过
 
            cin >> n >> start_x >> start_y;
            //memset(field, 0, sizeof field);
            int max_x = 0;
            int max_y = 0;
            for(int i = 0; i < n; i++) {
                int x;
                int y;
                cin >> x >> y;
                if(max_x < x) {
                    max_x = x;
                }
                if(max_y < y) {
                    max_y = y;
                }
                field[x][y] = 1;
            }
            cout << bfs(point(start_x, start_y, 0), field, max_x, max_y);
            for(int i = 0; i < N + 10; i++) {
                delete[] field[i];
            }
            delete[] field;
            return 0;
        }
 
        int bfs(point start, int **field, int max_x, int max_y) {
            auto que = deque<point>();
            que.push_front(start);
            while(!que.empty()) {
                const auto p = que.front();
                que.pop_front();
                point nexts[] = {
                        point(p.x + 1, p.y, p.step), point(p.x - 1, p.y, p.step),
                        point(p.x, p.y + 1, p.step), point(p.x, p.y - 1, p.step)};
                for(auto next: nexts) {
                    if(next.x == 0 && next.y == 0) {
                        return next.step;
                    }
                    if(0 <= next.x && next.x <= max_x + 2 && 0 <= next.y && next.y <= max_y + 2 &&
                       field[next.x][next.y] != 2) {
                        if(field[next.x][next.y] == 0) {
                            que.push_front(next);
                        } else {
                            //field[nexts.first][nexts.second]==1
                            next.step++;
                            que.push_back(next);
                        }
                        field[next.x][next.y] = 2;
                    }
                }
            }
            return start.step;
        }
    }// namespace acwing2019
 
    int acwing611::main(istream &cin, ostream &cout) {
        int a1;
        int b1;
        int a2;
        int b2;
        double c1;
        double c2;
        cin >> a1 >> b1 >> c1 >> a2 >> b2 >> c2;
        cout << "VALOR A PAGAR: R$ " << setiosflags(ios::fixed) << setprecision(2) << b1 * c1 + b2 * c2;
        return 0;
    }
 
    int acwing612::main(istream &cin, ostream &cout) {
        double r;
        cin >> r;
        cout << "VOLUME = " << setiosflags(ios::fixed) << setprecision(3) << 4.0 / 3.0 * 3.14159 * r * r * r;
        return 0;
    }
 
    int acwing2014::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *above  = new bool[n];
        auto heights = set<unsigned int>();
        auto m       = map<unsigned int, vector<unsigned int>>();
        for(int i = 0; i < n; i++) {
            int height;
            cin >> height;
            heights.insert(height);
            above[i] = true;//露出水面
            if(!m.contains(height)) {
                m[height] = vector<unsigned int>();
            }
            m[height].push_back(i);
        }
        int count = 1;
        int max   = count;
        for(auto height: heights) {
            for(const auto index: m[height]) {
                above[index] = false;
                if(0 < index && index + 1 < n) {
                    if(above[index - 1] && above[index + 1]) {
                        count++;
                    } else if(!above[index - 1] && !above[index + 1]) {
                        count--;
                    }
                } else if(index == 0 && !above[1] || index == n - 1 && !above[n - 2]) {
                    count--;
                }
            }
            if(max < count) {
                max = count;
            }
        }
        cout << max;
        delete[] above;
        return 0;
    }
 
    int acwing607::main(istream &cin, ostream &cout) {
        double a;
        double b;
        double c;
        cin >> a >> b >> c;
        cout << "MEDIA = " << setiosflags(ios::fixed) << setprecision(1) << (a * 2 + b * 3 + c * 5) / 10;
        return 0;
    }
 
    int acwing613::main(istream &cin, ostream &cout) {
        double a;
        double b;
        double c;
        cin >> a >> b >> c;
        cout << "TRIANGULO: " << setiosflags(ios::fixed) << setprecision(3) << a * c / 2 << endl;
        cout << "CIRCULO: " << setiosflags(ios::fixed) << setprecision(3) << c * c * 3.14159 << endl;
        cout << "TRAPEZIO: " << setiosflags(ios::fixed) << setprecision(3) << (a + b) * c / 2 << endl;
        cout << "QUADRADO: " << setiosflags(ios::fixed) << setprecision(3) << b * b << endl;
        cout << "RETANGULO: " << setiosflags(ios::fixed) << setprecision(3) << a * b;
        return 0;
    }
 
    int acwing610::main(istream &cin, ostream &cout) {
        string name;
        double b;
        double m;
        cin >> name >> b >> m;
        cout << "TOTAL = R$ " << setiosflags(ios::fixed) << setprecision(2) << b + 0.15 * m;
        return 0;
    }
 
    int acwing614::main(istream &cin, ostream &cout) {
        int a;
        int b;
        int c;
        cin >> a >> b >> c;
        const int maxab = (a + b + abs(a - b)) / 2;
        cout << (maxab + c + abs(maxab - c)) / 2 << " eh o maior";
        return 0;
    }
 
    int acwing2005::main(istream &cin, ostream &cout) {
        char horseshoes[5][5];
        bool picked[5][5];
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cin >> horseshoes[i][j];
            }
        }
        memset(picked, 0, sizeof picked);
        if(horseshoes[0][0] == ')') {
            cout << 0;
            return 0;
        }
        cout << dfs(true, horseshoes, picked, 1, 1, 0, 0, n);
        return 0;
    }
 
    int acwing2005::dfs(bool stage, char horseshoes[5][5], const bool picked[5][5], int count, int level, int x, int y,
                        int n) {
        if(level == 0 && !stage) {
            if(count == 13) {
                printf("13");
            }
            return count;
        }
 
        pair<int, int> nexts[4] = {pair(x - 1, y), pair(x + 1, y), pair(x, y - 1),
                                   pair(x, y + 1)};
        //复制状态
        bool picked_cpy[5][5];
        memcpy(picked_cpy, picked, sizeof picked_cpy);
 
        int max          = 0;
        picked_cpy[x][y] = true;
 
        for(const auto next: nexts) {
            if(0 <= next.first && next.first < n && 0 <= next.second && next.second < n &&
               !picked_cpy[next.first][next.second]) {
                int res = 0;
                if(stage && horseshoes[next.first][next.second] == '(') {
                    res = dfs(true, horseshoes, picked_cpy, count + 1, level + 1, next.first, next.second, n);
                } else if(stage && horseshoes[next.first][next.second] == ')') {
                    res = dfs(false, horseshoes, picked_cpy, count + 1, level - 1, next.first, next.second, n);
                } else if(!stage && horseshoes[next.first][next.second] == ')') {
                    res = dfs(false, horseshoes, picked_cpy, count + 1, level - 1, next.first, next.second, n);
                }
                if(max < res) {
                    max = res;
                }
            }
        }
        return max;
    }
 
    int acwing617::main(istream &cin, ostream &cout) {
        int l;
        cin >> l;
        cout << 2 * l << " minutos";
        return 0;
    }
 
    int acwing618::main(istream &cin, ostream &cout) {
        long t;
        long s;
        cin >> t >> s;
        cout << setiosflags(ios::fixed) << setprecision(3) << static_cast<double>(t * s) / 12;
        return 0;
    }
 
    int acwing4206::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        int count = 0;
        for(const char ch: str) {
            if(ch == '4' || ch == '7') {
                count++;
            }
        }
        if(count == 4 || count == 7) {
            cout << "YES";
        } else {
            cout << "NO";
        }
        return 0;
    }
 
    int acwing4207::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        auto *in_sub = new bool[str.length()];
        int count    = 0;
        memset(in_sub, 0, str.length() * sizeof(bool));
 
        int prev_left = -1;
        for(int i = 0; i < str.length(); i++) {
            if(str[i] == '(') {
                prev_left = i;
                break;
            }
        }
        for(int i = prev_left; i < str.length(); i++) {
            if(str[i] == ')' && prev_left != -1) {
                count += 2;
                in_sub[prev_left] = true;
                in_sub[i]         = true;
                for(int j = prev_left + 1; j < i; j++) {
                    if(str[j] == '(') {
                        prev_left = j;
                        break;
                    }
                }
                if(in_sub[prev_left]) {
                    prev_left = -1;
                }
            } else if(prev_left == -1 && str[i] == '(') {
                prev_left = i;
            }
        }
        cout << count;
        delete[] in_sub;
        return 0;
    }
 
    namespace acwing4208 {
        int acwing4208::main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            auto records = map<string, trie_node *>();
            for(int i = 0; i < n; i++) {
                string name;
                cin >> name;
                if(!records.contains(name)) {
                    //不存在记录
                    records[name] = new trie_node(-1, nullptr);
                }
                int n2;
                cin >> n2;
                for(int j = 0; j < n2; j++) {
                    string phone_number;
                    cin >> phone_number;
                    string phone_number_trim_left;
                    for(int k = 0; k < phone_number.length(); k++) {
                        if(phone_number[k] != '0') {
                            phone_number_trim_left = phone_number.substr(k);
                            break;
                        }
                    }
                    reverse(phone_number_trim_left.begin(), phone_number_trim_left.end());
                    records[name]->insert(phone_number_trim_left);
                }
            }
            cout << records.size();
            for(auto it: records) {
                cout << it.first << " ";
                cout << it.second->count() << " ";
                it.second->display();
            }
            return 0;
        }
 
        void trie_node::insert(string str) {
            if(str.length() == 0) {
                return;
            }
            if(this->nexts[str[0] - '0'] == nullptr) {
                this->nexts[str[0] - '0'] = new trie_node(str[0] - '0', this);
            }
            this->nexts[str[0] - '0']->insert(str.substr(1));
        }
 
        void trie_node::display() {
            bool flag = true;
            for(auto *next: this->nexts) {
                if(next != nullptr) {
                    flag = false;
                    next->display();
                }
            }
            if(flag) {
                const auto *current = this;
                while(current->val != -1) {
                    cout << static_cast<char>(current->val + '0');
                    current = current->father;
                }
                cout << " ";
            }
        }
 
        int trie_node::count() {
            int count = 0;
            bool flag = true;
            for(auto *next: this->nexts) {
                if(next != nullptr) {
                    flag = false;
                    count += next->count();
                }
            }
            if(flag) {
                return 1;
            }
            return count;
        }
    }// namespace acwing4208
 
    int acwing1996::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto names = vector<string>();
        names.resize(n);
        auto min_names = vector<string>();
        auto max_names = vector<string>();
        min_names.resize(n);
        max_names.resize(n);
        for(int i = 0; i < n; i++) {
            cin >> names[i];
            const auto *min_name_const_c_str = names[i].c_str();
            const auto *max_name_const_c_str = names[i].c_str();
            auto *min_name_c_str             = new char[names[i].length() + 1];
            auto *max_name_c_str             = new char[names[i].length() + 1];
            strcpy(min_name_c_str, min_name_const_c_str);
            strcpy(max_name_c_str, max_name_const_c_str);
            sort(min_name_c_str, min_name_c_str + names[i].length() * sizeof(char));
            sort(max_name_c_str, max_name_c_str + names[i].length() * sizeof(char), cmp);
            const auto min_name = string(min_name_c_str);
            const auto max_name = string(max_name_c_str);
            min_names[i]        = min_name;
            max_names[i]        = max_name;
            delete[] min_name_c_str;
            delete[] max_name_c_str;
        }
        auto min_names_sorted = vector(min_names);
        auto max_names_sorted = vector(max_names);
        sort(min_names_sorted.begin(), min_names_sorted.end());
        sort(max_names_sorted.begin(), max_names_sorted.end());
        for(int i = 0; i < n; i++) {
            auto min_name = min_names[i];
            auto max_name = max_names[i];
            cout << lower_bound(max_names_sorted.begin(), max_names_sorted.end(), min_name) - max_names_sorted.begin() +
                            1
                 << " "
                 << upper_bound(min_names_sorted.begin(), min_names_sorted.end(), max_name) - min_names_sorted.begin()
                 << endl;
        }
        return 0;
    }
 
    bool acwing1996::cmp(char x, char y) { return x > y; }
 
    int acwing656::main(istream &cin, ostream &cout) {
        double n;
        cin >> n;
        int total                 = static_cast<int>(n * static_cast<double>(100));
        const int denominations[] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 25, 10, 5, 1};
        int count[12];
        for(int i = 0; i < 12; i++) {
            count[i] = total / denominations[i];
            total %= denominations[i];
        }
        cout << "NOTAS:" << endl
             << count[0] << " nota(s) de R$ 100.00" << endl
             << count[1] << " nota(s) de R$ 50.00" << endl
             << count[2] << " nota(s) de R$ 20.00" << endl
             << count[3] << " nota(s) de R$ 10.00" << endl
             << count[4] << " nota(s) de R$ 5.00" << endl
             << count[5] << " nota(s) de R$ 2.00" << endl
             << "MOEDAS:" << endl
             << count[6] << " moeda(s) de R$ 1.00" << endl
             << count[7] << " moeda(s) de R$ 0.50" << endl
             << count[8] << " moeda(s) de R$ 0.25" << endl
             << count[9] << " moeda(s) de R$ 0.10" << endl
             << count[10] << " moeda(s) de R$ 0.05" << endl
             << count[11] << " moeda(s) de R$ 0.01";
        return 0;
    }
 
    int acwing655::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        cout << n / 365 << " ano(s)" << endl;
        n %= 365;
        cout << n / 30 << " mes(es)" << endl;
        n %= 30;
        cout << n << " dia(s)";
        return 0;
    }
 
    int acwing665::main(istream &cin, ostream &cout) {
        int a;
        int b;
        cin >> a >> b;
        if(a % b == 0 || b % a == 0) {
            cout << "Sao Multiplos";
        } else {
            cout << "Nao sao Multiplos";
        }
        return 0;
    }
 
    int acwing657::main(istream &cin, ostream &cout) {
        int a;
        int b;
        int c;
        int d;
        cin >> a >> b >> c >> d;
        if(b > c && d > a && c + d > a + b && c > 0 && d > 0 && a % 2 == 0) {
            cout << "Valores aceitos";
        } else {
            cout << "Valores nao aceitos";
        }
        return 0;
    }
 
    int acwing1987::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto m      = map<int, int>();
        int current = 0;
        for(int i = 0; i < n; i++) {
            int length;
            char direction;
            cin >> length >> direction;
            if(direction == 'R') {
                if(!m.contains(current)) {
                    m.insert(pair(current, 1));
                } else {
                    m[current]++;
                }
                if(!m.contains(current + length)) {
                    m.insert(pair(current + length, -1));
                } else {
                    m[current + length]--;
                }
                current += length;
            } else {
                if(!m.contains(current)) {
                    m.insert(pair(current, -1));
                } else {
                    m[current]--;
                }
                if(!m.contains(current - length)) {
                    m.insert(pair(current - length, 1));
                } else {
                    m[current - length]++;
                }
                current -= length;
            }
        }
        unsigned int layer_count = 0;
        unsigned int count       = 0;
        bool above2              = false;
        int prev;
        for(const auto p: m) {
            layer_count += p.second;
            if(layer_count >= 2) {
                if(above2) {
                    count += p.first - prev;
                }
                above2 = true;
                prev   = p.first;
            } else {
                if(above2) {
                    count += p.first - prev;
                }
                above2 = false;
            }
        }
        cout << count;
        return 0;
    }
 
    int acwing660::main(istream &cin, ostream &cout) {
        const double snacks[] = {4, 4.5, 5, 2, 1.5};
        int x;
        int y;
        cin >> x >> y;
        cout << "Total: R$ " << setiosflags(ios::fixed) << setprecision(2) << snacks[x - 1] * y;
        return 0;
    }
 
    int acwing671::main(istream &cin, ostream &cout) {
        auto cities = unordered_map<unsigned int, string>();
        cities[61]  = "Brasilia";
        cities[71]  = "Salvador";
        cities[11]  = "Sao Paulo";
        cities[21]  = "Rio de Janeiro";
        cities[32]  = "Juiz de Fora";
        cities[19]  = "Campinas";
        cities[27]  = "Vitoria";
        cities[31]  = "Belo Horizonte";
        int number;
        cin >> number;
        if(cities.contains(number)) {
            cout << cities[number];
        } else {
            cout << "DDD nao cadastrado";
        }
        return 0;
    }
 
    namespace acwing1978 {
        int acwing1978::main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            auto *maximum = new int[n];
            auto *minimum = new int[n];
            memset(maximum, 0, n * sizeof(int));
            memset(minimum, 0, n * sizeof(int));
            auto *paths = new path[n];
            for(int i = 0; i < n; i++) {
                int a;
                int b;
                cin >> a >> b;
                paths[i] = path(a, b);
            }
            sort(paths, paths + n);
            maximum[0]     = paths[0].b;    //i以前b的最大值
            minimum[n - 1] = paths[n - 1].b;//i以后b的最小值
            for(int i = 1; i < n; i++) {
                maximum[i] = max(maximum[i - 1], paths[i].b);
            }
            for(int i = n - 2; i >= 0; i--) {
                minimum[i] = min(minimum[i + 1], paths[i].b);
            }
            int ans = n;
            for(int i = 0; i < n; i++) {
                if(maximum[i] > paths[i].b || minimum[i] < paths[i].b) {
                    ans--;
                }
            }
            cout << ans;
            delete[] paths;
            delete[] minimum;
            delete[] maximum;
            return 0;
        }
 
        bool path::operator<(const path &p) const { return this->a < p.a; }
    }// namespace acwing1978
 
    int acwing659::main(istream &cin, ostream &cout) {
        double x;
        const string output[] = {"[0,25]", "(25,50]", "(50,75]", "(75,100]"};
        cin >> x;
        if(x < 0.0 || x > 100.0) {
            cout << "Fora de intervalo";
        } else if(x > 75.0) {
            cout << "Intervalo " << output[3];
        } else if(x > 50.0) {
            cout << "Intervalo " << output[2];
        } else if(x > 25.0) {
            cout << "Intervalo " << output[1];
        } else {
            cout << "Intervalo " << output[0];
        }
        return 0;
    }
 
    int acwing662::main(istream &cin, ostream &cout) {
        float x;
        float y;
        cin >> x >> y;
        if(x == 0 && y == 0) {
            cout << "Origem";
        } else if(x == 0) {
            cout << "Eixo Y";
        } else if(y == 0) {
            cout << "Eixo X";
        } else if(x > 0 && y > 0) {
            cout << "Q1";
        } else if(x < 0 && y > 0) {
            cout << "Q2";
        } else if(x < 0 && y < 0) {
            cout << "Q3";
        } else {
            cout << "Q4";
        }
        return 0;
    }
 
    int acwing1969::main(istream &cin, ostream &cout) {
        unsigned int n;
        unsigned int k;
        cin >> n >> k;
        auto um           = unordered_map<unsigned int, unsigned int>();
        auto overcrowding = set<unsigned int>();
        for(unsigned int i = 0; i < n; i++) {
            unsigned int id;
            cin >> id;
            if(!um.contains(id)) {
                um.insert(pair(id, i));
            } else if(!overcrowding.contains(id)) {
                if(i - um[id] > k) {
                    um[id] = i;
                } else {
                    overcrowding.insert(id);
                }
            }
        }
        if(overcrowding.empty()) {
            cout << -1;
        } else {
            cout << *--overcrowding.end();
        }
        return 0;
    }
 
    int acwing664::main(istream &cin, ostream &cout) {
        double a;
        double b;
        double c;
        cin >> a >> b >> c;
        cout << setiosflags(ios::fixed) << setprecision(1);
        if(a + b <= c || a + c <= b || b + c <= a) {
            cout << "Area = " << (a + b) * c / 2;
        } else {
            cout << "Perimetro = " << a + b + c;
        }
        return 0;
    }
 
    int acwing666::main(istream &cin, ostream &cout) {
        double arr[3];
        cin >> arr[0] >> arr[1] >> arr[2];
        sort(arr, arr + 3);
        const double a = arr[2];
        const double b = arr[1];
        const double c = arr[0];
        if(a >= b + c) {
            cout << "NAO FORMA TRIANGULO";
        } else {
            if(a * a == b * b + c * c) {
                cout << "TRIANGULO RETANGULO" << endl;
            }
            if(a * a > b * b + c * c) {
                cout << "TRIANGULO OBTUSANGULO" << endl;
            }
            if(a * a < b * b + c * c) {
                cout << "TRIANGULO ACUTANGULO" << endl;
            }
            if(a == b && b == c) {
                cout << "TRIANGULO EQUILATERO" << endl;
            }
            if(a == b && b != c || b == c && a != b || a == c && a != b) {
                cout << "TRIANGULO ISOSCELES" << endl;
            }
        }
        return 0;
    }
 
    int acwing1960::main(istream &cin, ostream &cout) {
        memset(fsm, -2, sizeof fsm);
        unsigned long long b;
        cin >> n >> b;
        unsigned int status = 0;
        for(int i = 0; i < n; i++) {
            unsigned int bulb;
            cin >> bulb;
            status += bulb;
            status <<= 1;
        }
        status >>= 1;
        fsm[status] = -1;
 
        int count          = 0;
        int round          = 0;
        unsigned int index = 0;
        for(int i = 0; i < b; i++) {
            if(fsm[status] >= 0) {
                if(round == 0) {
                    round = 1;
                    index = status;
                } else if(round == 1 && status == index) {
                    b     = (b - i) % count + i;
                    round = 2;
                }
            }
            if(round == 1) {
                count++;
            }
            status = get_next(status);
        }
        const auto *const ans = decompress(status);
        for(int i = 0; i < n; i++) {
            cout << static_cast<int>(ans[i]) << endl;
        }
        delete[] ans;
        return 0;
    }
 
    unsigned int acwing1960::get_next(unsigned int status) {
        if(fsm[status] >= 0) {
            return fsm[status];
        }
        const bool *bulbs      = decompress(status);
        auto *const next_bulbs = new bool[n];
        for(int i = 0; i < n; i++) {
            if(bulbs[(i - 1 + n) % n]) {
                next_bulbs[i] = !bulbs[i];
            } else {
                next_bulbs[i] = bulbs[i];
            }
        }
        const int next_status = compress(next_bulbs);
        fsm[status]           = next_status;
        delete[] next_bulbs;
        delete[] bulbs;
        return next_status;
    }
 
    bool *acwing1960::decompress(unsigned int status) const {
        auto *const bulbs = new bool[n];
        for(int i = n - 1; i >= 0; i--) {
            bulbs[i] = (status & 1) != 0U;
            status >>= 1;
        }
        return bulbs;
    }
 
    unsigned int acwing1960::compress(const bool *bulbs) const {
        int status = 0;
        for(int i = 0; i < n; i++) {
            status += static_cast<int>(bulbs[i]);
            status <<= 1;
        }
        status >>= 1;
        return status;
    }
 
    int acwing667::main(istream &cin, ostream &cout) {
        unsigned int a;
        unsigned int b;
        cin >> a >> b;
        int t = (b - a + 24) % 24;
        if(t == 0) {
            t = 24;
        }
        cout << "O JOGO DUROU " << t << " HORA(S)";
        return 0;
    }
 
    int acwing668::main(istream &cin, ostream &cout) {
        unsigned int a;
        unsigned int b;
        unsigned int c;
        unsigned int d;
        cin >> a >> b >> c >> d;
        unsigned int t = (c * 60 + d - (a * 60 + b) + 24 * 60) % (24 * 60);
        if(t == 0) {
            t = 24 * 60;
        }
        cout << "O JOGO DUROU " << t / 60 << " HORA(S) E " << t % 60 << " MINUTO(S)";
        return 0;
    }
 
    int acwing1952::main(istream &cin, ostream &cout) {
        unsigned short n;
        unsigned short x;
        unsigned short y;
        unsigned short z;
        cin >> n >> x >> y >> z;
        auto as    = unordered_map<unsigned int, unsigned int>();
        auto bs    = unordered_map<unsigned int, unsigned int>();
        auto edges = set<unsigned int>();
        for(unsigned short i = 0; i < n; i++) {
            unsigned int a;
            unsigned int b;
            cin >> a >> b;
            if(!as.contains(a)) {
                as.insert(pair<unsigned int, unsigned int>(a, 1));
                edges.insert(a);
            } else {
                as[a]++;
            }
            if(!bs.contains(b)) {
                bs.insert(pair<unsigned int, unsigned int>(b, 1));
                edges.insert(b);
            } else {
                bs[b]++;
            }
        }
        unsigned int count = x * n;
        unsigned int max   = count;
        for(unsigned int edge: edges) {
            if(as.contains(edge)) {
                count += (y - x) * as[edge];
            }
            if(max < count) {
                max = count;
            }
            if(bs.contains(edge)) {
                count -= (y - z) * bs[edge];
            }
        }
        cout << max;
        return 0;
    }
 
    int acwing669::main(istream &cin, ostream &cout) {
        double salary;
        cin >> salary;
        unsigned short percentual = 0;
        if(salary <= 400) {
            percentual = 15;
        } else if(salary <= 800) {
            percentual = 12;
        } else if(salary <= 1200) {
            percentual = 10;
        } else if(salary <= 2000) {
            percentual = 7;
        } else {
            percentual = 4;
        }
        const double new_salary = salary * (100 + percentual) / 100;
        cout << setiosflags(ios::fixed) << setprecision(2);
        cout << "Novo salario: " << new_salary << endl;
        cout << "Reajuste ganho: " << new_salary - salary << endl;
        cout << "Em percentual: " << percentual << " %";
        return 0;
    }
 
    int acwing672::main(istream &cin, ostream &cout) {
        double income;
        cin >> income;
        double tax = 0;
        if(income <= 2000) {
            tax = 0;
        } else if(2000 < income && income <= 3000) {
            income -= 2000;
            tax += income * 0.08;
        } else if(income <= 4500) {
            tax = 80;
            income -= 3000;
            tax += income * 0.18;
        } else {
            tax = 350;
            income -= 4500;
            tax += income * 0.28;
        }
        if(tax == 0) {
            cout << "Isento";
        } else {
            cout << setiosflags(ios::fixed) << setprecision(2) << "R$ " << tax;
        }
        return 0;
    }
 
    int acwing1945::main(istream &cin, ostream &cout) {
        unsigned int count = 0;
        unsigned short n;
        cin >> n;
        auto cows = vector<unsigned int>();
        cows.resize(n);
        for(int i = 0; i < n; i++) {
            unsigned int cow;
            cin >> cow;
            cows[i] = cow;
        }
        sort(cows.begin(), cows.end());
        for(auto i = cows.begin(); i != cows.end(); ++i) {
            for(auto j = i + 1; j != cows.end(); ++j) {
                const unsigned int xy = *j - *i;
                auto min              = lower_bound(j, cows.end(), *j + xy);
                auto max              = upper_bound(j, cows.end(), *j + 2 * xy);
                count += max - min;
            }
        }
        cout << count;
        return 0;
    }
 
    int acwing4209::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        int x = 0;
        int y = 0;
        int z = 0;
        for(int i = 0; i < n; i++) {
            int xi;
            int yi;
            int zi;
            cin >> xi >> yi >> zi;
            x += xi;
            y += yi;
            z += zi;
        }
        if(x == 0 && y == 0 && z == 0) {
            cout << "YES";
        } else {
            cout << "NO";
        }
        return 0;
    }
 
    int acwing4210::main(istream &cin, ostream &cout) {
        unsigned short a;
        cin >> a;
        unsigned int count = 0;
        for(int i = 2; i <= a - 1; i++) {
            unsigned short cpy = a;
            while(cpy != 0) {
                count += cpy % i;
                cpy /= i;
            }
        }
        unsigned int denominator = a - 2;
        unsigned int molecular   = count;
        while(denominator % molecular != 0) {
            const unsigned int temp = denominator;
            denominator             = molecular;
            molecular               = temp % molecular;
        }
        cout << count / molecular << "/" << (a - 2) / molecular;
        return 0;
    }
 
    int acwing4211::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        auto vec = vector<unsigned long long>();
        for(unsigned short i = 0; i < n; i++) {
            unsigned long long a;
            cin >> a;
            vec.push_back(a);
        }
        sort(vec.begin(), vec.end(), cmp);
        for(const auto i: vec) {
            cout << i << " ";
        }
        return 0;
    }
 
    unsigned int acwing4211::no2(unsigned long long a) {
        unsigned int count = 0;
        while(a % 2 == 0) {
            count++;
            a /= 2;
        }
        return count;
    }
 
    unsigned int acwing4211::no3(unsigned long long a) {
        unsigned int count = 0;
        while(a % 3 == 0) {
            count++;
            a /= 3;
        }
        return count;
    }
 
    bool acwing4211::cmp(unsigned long long a, unsigned long long b) {
        const unsigned a3 = no3(a);
        const unsigned b3 = no3(b);
        if(a3 == b3) {
            const unsigned a2 = no2(a);
            const unsigned b2 = no2(b);
            return a2 < b2;
        }
        return a3 > b3;
    }
 
    int acwing670::main(istream &cin, ostream &cout) {
        string str1;
        string str2;
        string str3;
        cin >> str1 >> str2 >> str3;
        if(str1 == "vertebrado") {
            if(str2 == "ave") {
                if(str3 == "carnivoro") {
                    cout << "aguia";
                } else {
                    cout << "pomba";
                }
            } else {
                if(str3 == "onivoro") {
                    cout << "homem";
                } else {
                    cout << "vaca";
                }
            }
        } else {
            if(str2 == "inseto") {
                if(str3 == "hematofago") {
                    cout << "pulga";
                } else {
                    cout << "lagarta";
                }
            } else {
                if(str3 == "hematofago") {
                    cout << "sanguessuga";
                } else {
                    cout << "minhoca";
                }
            }
        }
        return 0;
    }
 
    int acwing633::main(istream &cin, ostream &cout) {
        auto vec = vector<short>();
        vec.resize(3);
        cin >> vec[0];
        cin >> vec[1];
        cin >> vec[2];
        auto sorted = vector(vec);
        sort(sorted.begin(), sorted.end());
        for(const auto num: sorted) {
            cout << num << endl;
        }
        cout << endl;
        for(const auto num: vec) {
            cout << num << endl;
        }
        return 0;
    }
 
    int acwing1934::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto t = vector<int>();
        auto d = vector<int>();
        for(int i = 0; i < n; i++) {
            char op;
            int x;
            cin >> op >> x;
            if(op == 'T') {
                t.push_back(x);
            } else {
                d.push_back(x);
            }
        }
        sort(t.begin(), t.end());
        sort(d.begin(), d.end());
        double current_d     = 0;
        double current_t     = 0;
        double decelerations = 1;
        auto it_d            = d.begin();
        auto it_t            = t.begin();
        while(true) {
            int next_d = 1000;
            if(it_d != d.end()) {
                next_d = *it_d;
            }
            const auto t_for_next_d = (next_d - current_d) * decelerations;//到下一个D的时间
            bool next_is_d          = true;
            if(it_t != t.end()) {
                next_is_d = t_for_next_d < *it_t - current_t;
            }
            if(next_is_d) {
                //先到D
                current_d = next_d;
                ++it_d;
                current_t += t_for_next_d;
            } else if(it_t != t.end()) {
                //先到T
                current_d += (*it_t - current_t) * (1.0 / decelerations);
                current_t = *it_t;
                ++it_t;
            }
            decelerations++;
            if(it_d == d.end() && it_t == t.end()) {
                current_t += (1000 - current_d) * decelerations;
                break;
            }
        }
        cout << lround(current_t);
        return 0;
    }
 
    int acwing658::main(istream &cin, ostream &cout) {
        double a;
        double b;
        double c;
        cin >> a >> b >> c;
        if(b * b - 4 * a * c < 0 || a == 0) {
            cout << "Impossivel calcular";
            return 0;
        }
        const auto r1 = (-b + sqrt(b * b - 4 * a * c)) / (2 * a);
        const auto r2 = (-b - sqrt(b * b - 4 * a * c)) / (2 * a);
        cout << setiosflags(ios::fixed) << setprecision(5)
             << "R1 = " << r1 << endl
             << "R2 = " << r2;
        return 0;
    }
 
    int acwing661::main(istream &cin, ostream &cout) {
        double n1;
        double n2;
        double n3;
        double n4;
        cin >> n1 >> n2 >> n3 >> n4;
        const double x = (2 * n1 + 3 * n2 + 4 * n3 + n4) / 10;
        cout << setiosflags(ios::fixed) << setprecision(1);
        cout << "Media: " << x << endl;
        if(x >= 7.0) {
            cout << "Aluno aprovado.";
        } else if(x <= 5.0) {
            cout << "Aluno reprovado.";
        } else {
            cout << "Aluno em exame." << endl;
            double y;
            cin >> y;
            cout << "Nota do exame: " << y << endl;
            const double z = (x + y) / 2;
            if(z >= 5.0) {
                cout << "Aluno aprovado." << endl;
            } else {
                cout << "Aluno reprovado." << endl;
            }
            cout << "Media final: " << z;
        }
        return 0;
    }
 
    namespace acwing1929 {
        int Solution::main(istream &cin, ostream &cout) {
            cin >> n >> m;
            for(unsigned short i = 0; i < n; i++) {
                for(unsigned short j = 0; j < m; j++) {
                    cin >> mirrors[i][j];
                }
            }
            int maximum = -1;
            for(unsigned short j = 0; j < m; j++) {
                maximum = max(maximum, static_cast<int>(count_reflect(down, 0, j)));
            }
            for(unsigned short j = 0; j < m; j++) {
                maximum = max(maximum, static_cast<int>(count_reflect(up, n - 1, j)));
            }
            for(unsigned short i = 0; i < n; i++) {
                maximum = max(maximum, static_cast<int>(count_reflect(right, i, 0)));
            }
            for(unsigned short i = 0; i < n; i++) {
                maximum = max(maximum, static_cast<int>(count_reflect(left, i, m - 1)));
            }
            cout << maximum;
            return 0;
        }
 
        unsigned int Solution::count_reflect(direction d, unsigned int x, unsigned int y) {
            if(x == 0 || y == 0 || x == n - 1 || y == m - 1) {
                unsigned int count  = 0;
                int current_x       = x;
                int current_y       = y;
                direction current_d = d;
                auto path           = unordered_set<step, step_hash, step_equal>();
                while(0 <= current_x && current_x < n && 0 <= current_y && current_y < m) {
                    auto s = step(current_d, current_x, current_y);
                    if(!path.contains(s)) {
                        path.insert(s);
                    } else {
                        return -1;
                    }
 
                    const auto *record = get_record(d);
                    if((*record)[x][y] != 0) {
                        return count + (*record)[x][y];
                    }
                    current_d = reflect(current_d, mirrors[current_x][current_y]);
                    count++;
                    (*get_record(!current_d))[current_x][current_y] = count;
                    switch(current_d) {
                        case left: {
                            current_y--;
                            break;
                        }
                        case right: {
                            current_y++;
                            break;
                        }
                        case up: {
                            current_x--;
                            break;
                        }
                        case down: {
                            current_x++;
                            break;
                        }
                    }
                }
                return count;
            }
            return -1;
        }
 
        unsigned int (*Solution::get_record(direction d))[1000][1000] {
            switch(d) {
                case left: {
                    return &left_map;
                }
                case right: {
                    return &right_map;
                }
                case up: {
                    return &up_map;
                }
                case down: {
                    return &down_map;
                }
            }
            return nullptr;
        }
 
        direction reflect(direction d, char mirror) {
            switch(d) {
                case left: {
                    if(mirror == '/') {
                        return down;
                    }
                    if(mirror == '\\') {
                        return up;
                    }
                    break;
                }
                case right: {
                    if(mirror == '/') {
                        return up;
                    }
                    if(mirror == '\\') {
                        return down;
                    }
                    break;
                }
                case up: {
                    if(mirror == '/') {
                        return right;
                    }
                    if(mirror == '\\') {
                        return left;
                    }
                    break;
                }
                case down: {
                    if(mirror == '/') {
                        return left;
                    }
                    if(mirror == '\\') {
                        return right;
                    }
                    break;
                }
            }
            return {};
        }
 
        direction operator!(const direction &d) {
            switch(d) {
                case left: {
                    return right;
                }
                case right: {
                    return left;
                }
                case up: {
                    return down;
                }
                case down: {
                    return up;
                }
            }
            return {};
        }
 
        unsigned long step_hash::operator()(const step &s) const { return s.d * 1000 * 1000 + s.x * 1000 + s.y; }
 
        bool step_equal::operator()(const step &s1, const step &s2) const { return s1.d == s2.d && s1.x == s2.x && s1.y == s2.y; }
    }// namespace acwing1929
 
    int acwing708::main(istream & /*cin*/, ostream &cout) {
        for(int i = 1; i <= 100; i++) {
            if(i % 2 == 0) {
                cout << i << endl;
            }
        }
        return 0;
    }
 
    int acwing715::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for(int i = 2; i < 10000; i += n) {
            cout << i << endl;
        }
        return 0;
    }
 
    int acwing1922::main(istream &cin, ostream &cout) {
        unsigned int n;
        unsigned int k;
        cin >> n >> k;
        auto um            = unordered_map<unsigned int, unsigned int>();
        unsigned int max_x = 0;
        for(unsigned int i = 0; i < n; i++) {
            unsigned int g;
            unsigned int x;
            cin >> g >> x;
            max_x = max(max_x, x);
            um.insert(pair(x, g));
        }
        unsigned int count = 0;
        for(int i = 0; i < 2 * k; i++) {
            if(um.contains(i)) {
                count += um[i];
            }
        }
        unsigned int maximum = count;
        for(int i = 1; i + 2 * k <= max_x; i++) {
            if(um.contains(i - 1)) {
                count -= um[i - 1];
            }
            if(um.contains(i + 2 * k)) {
                count += um[i + 2 * k];
            }
            maximum = max(maximum, count);
        }
        cout << maximum;
        return 0;
    }
 
    int acwing709::main(istream &cin, ostream &cout) {
        int x;
        cin >> x;
        for(int i = 1; i <= x; i += 2) {
            cout << i << endl;
        }
        return 0;
    }
 
    int acwing710::main(istream &cin, ostream &cout) {
        int x;
        cin >> x;
        if(x % 2 == 0) {
            x++;
        }
        for(int i = 0; i < 6; i++) {
            cout << x + i * 2 << endl;
        }
        return 0;
    }
 
    int acwing1913::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        auto cows    = map<unsigned int, int>();
        auto indexes = vector<unsigned int>();
        auto sum     = unordered_map<int, set<unsigned int>>();
        for(unsigned int i = 0; i < n; i++) {
            unsigned int x;
            char b;
            cin >> x >> b;
            indexes.push_back(x);
            if(b == 'G') {
                cows.insert(pair(x, 1));
            } else {
                cows.insert(pair(x, -1));
            }
        }
        sort(indexes.begin(), indexes.end());
 
        unsigned int g_count = 0;
        unsigned int h_count = 0;
        unsigned int g_max   = 0;
        unsigned int h_max   = 0;
        int g_start          = -1;
        int h_start          = -1;
        int count            = 0;
        for(auto &cow: cows) {
            if(cow.second == 1) {
                //G
                h_count = 0;
                h_start = -1;
                if(g_start == -1) {
                    g_start = cow.first;
                } else {
                    g_count = cow.first - g_start;
                }
                g_max = max(g_max, g_count);
            } else {
                //H
                g_count = 0;
                g_start = -1;
                if(h_start == -1) {
                    h_start = cow.first;
                } else {
                    h_count = cow.first - h_start;
                }
                h_max = max(h_max, h_count);
            }
            count += cow.second;
            cow.second = count;
            if(!sum.contains(cow.second)) {
                auto s = set<unsigned int>();
                s.insert(cow.first);
                sum.insert(pair(cow.second, s));
            } else {
                sum[cow.second].insert(cow.first);
            }
        }
        unsigned int maximum = 0;
        for(const auto &i: sum) {
            if(i.first == 0) {
                maximum = max(maximum, *i.second.rbegin() - indexes[0]);
            } else if(i.second.size() >= 2) {
                maximum = max(maximum, *i.second.rbegin() - *upper_bound(indexes.begin(), indexes.end(), *i.second.begin()));
            }
        }
        cout << max(maximum, max(g_max, h_max));
        return 0;
    }
 
    int acwing712::main(istream &cin, ostream &cout) {
        int count = 0;
        for(int i = 0; i < 6; i++) {
            double x;
            cin >> x;
            if(x > 0) {
                count++;
            }
        }
        cout << count << " positive numbers";
        return 0;
    }
 
    int acwing711::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for(int i = 1; i <= 10; i++) {
            cout << i << " x " << n << " = " << i * n << endl;
        }
        return 0;
    }
 
    int acwing1904::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        auto speeds = map<unsigned int, unsigned int>();
        for(unsigned int i = 0; i < n; i++) {
            unsigned int pos;
            unsigned int speed;
            cin >> pos >> speed;
            speeds.insert(pair(pos, speed));
        }
        unsigned int current_min = 1000000000;
        unsigned int count       = 0;
        for(auto i = speeds.rbegin(); i != speeds.rend(); ++i) {
            if((*i).second <= current_min) {
                current_min = (*i).second;
                count++;
            }
        }
        cout << count;
        return 0;
    }
 
    int acwing714::main(istream &cin, ostream &cout) {
        short x;
        short y;
        cin >> x >> y;
        if(y < x) {
            const auto temp = x;
            x               = y;
            y               = temp;
        }
        int count = 0;
        for(int i = x + 1; i < y; i++) {
            if(i % 2 != 0) {
                count += i;
            }
        }
        cout << count;
        return 0;
    }
 
    int acwing718::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        unsigned int c_count = 0;
        unsigned int r_count = 0;
        unsigned int f_count = 0;
        for(unsigned short i = 0; i < n; i++) {
            unsigned short a;
            char t;
            cin >> a >> t;
            switch(t) {
                case 'C':
                    c_count += a;
                    break;
                case 'R':
                    r_count += a;
                    break;
                case 'F':
                    f_count += a;
                    break;
            }
        }
        const unsigned int count = c_count + r_count + f_count;
        cout << setiosflags(ios::fixed) << setprecision(2) << "Total: " << count << " animals" << endl
             << "Total coneys: " << c_count << endl
             << "Total rats: " << r_count << endl
             << "Total frogs: " << f_count << endl
             << "Percentage of coneys: " << static_cast<double>(c_count) / static_cast<double>(count) * 100
             << " %" << endl
             << "Percentage of rats: " << static_cast<double>(r_count) / static_cast<double>(count) * 100
             << " %" << endl
             << "Percentage of frogs: " << static_cast<double>(f_count) / static_cast<double>(count) * 100
             << " %";
        return 0;
    }
 
    int acwing1884::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *cow = new char[n];
        auto *c   = new int[n];//当前项左边有多少个C
        auto *w   = new int[n];//当前项右边有多少个W
        c[0]      = 0;
        w[n - 1]  = 0;
        for(int i = 0; i < n; i++) {
            cin >> cow[i];
            if(i >= 1) {
                c[i] = c[i - 1];
                if(cow[i - 1] == 'C') {
                    c[i]++;
                }
            }
        }
        for(int i = n - 2; i >= 0; i--) {
            w[i] = w[i + 1];
            if(cow[i + 1] == 'W') {
                w[i]++;
            }
        }
        unsigned long count = 0;
        for(int i = 0; i < n; i++) {
            if(cow[i] == 'O') {
                count += c[i] * w[i];
            }
        }
        cout << count;
        delete[] w;
        delete[] c;
        delete[] cow;
        return 0;
    }
 
    int acwing4212::main(istream &cin, ostream &cout) {
        string a;
        string b;
        cin >> a >> b;
        auto ossa = ostringstream();
        auto ossb = ostringstream();
        for(char ch: a) {
            if(isupper(ch) != 0) {
                ch = tolower(ch);
            }
            ossa << ch;
        }
        for(char ch: b) {
            if(isupper(ch) != 0) {
                ch = tolower(ch);
            }
            ossb << ch;
        }
        a = ossa.str();
        b = ossb.str();
        if(a > b) {
            cout << 1;
        } else if(a < b) {
            cout << -1;
        } else {
            cout << 0;
        }
        return 0;
    }
 
    int acwing4213::main(istream &cin, ostream &cout) {
        unsigned int num[4];
        cin >> num[0] >> num[1] >> num[2] >> num[3];
        vector<char> ops;
        char op;
        for(int i = 0; i < 3; i++) {
            cin >> op;
            ops.push_back(op);
        }
        cout << get_min(ops, vector<unsigned long long>(begin(num), end(num)));
        return 0;
    }
 
    unsigned long long acwing4213::get_min(vector<char> ops, vector<unsigned long long> vec) {
        const char op = ops[0];
        if(vec.size() == 2) {
            if(op == '+') {
                return vec[0] + vec[1];
            }
            return vec[0] * vec[1];
        }
        const auto next_ops        = vector(ops.begin() + 1, ops.end());
        unsigned long long minimum = 1000000000000;
        for(int i = 0; i < vec.size() - 1; i++) {
            for(int j = i + 1; j < vec.size(); j++) {
                unsigned long long new_num;
                if(op == '+') {
                    new_num = vec[i] + vec[j];
                } else {
                    new_num = vec[i] * vec[j];
                }
                auto new_vec = vector<unsigned long long>();
                new_vec.push_back(new_num);
                for(int k = 0; k < vec.size(); k++) {
                    if(k != i && k != j) {
                        new_vec.push_back(vec[k]);
                    }
                }
                const auto ret = get_min(next_ops, new_vec);
                if(minimum > ret) {
                    minimum = ret;
                }
            }
        }
        return minimum;
    }
 
    int acwing4214::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        auto *s = new unsigned int[n];
        auto *c = new unsigned int[n];
        for(unsigned short i = 0; i < n; i++) {
            cin >> s[i];
        }
        for(unsigned short i = 0; i < n; i++) {
            cin >> c[i];
        }
        unsigned int minimum = 300000001;
        for(int j = 1; j < n - 1; j++) {
            unsigned int min_left  = 100000001;
            unsigned int min_right = 100000001;
            for(int i = 0; i < j; i++) {
                if(s[i] < s[j]) {
                    if(c[i] < min_left) {
                        min_left = c[i];
                    }
                }
            }
            for(int k = j + 1; k < n; k++) {
                if(s[j] < s[k]) {
                    if(c[k] < min_right) {
                        min_right = c[k];
                    }
                }
            }
            if(min_left != 100000001 && min_right != 100000001 && minimum > min_left + c[j] + min_right) {
                minimum = min_left + c[j] + min_right;
            }
        }
        if(minimum != 300000001) {
            cout << minimum;
        } else {
            cout << -1;
        }
        return 0;
    }
 
    int acwing716::main(istream &cin, ostream &cout) {
        int maximum = 0;
        int max_i   = 0;
        for(int i = 1; i <= 100; i++) {
            int num;
            cin >> num;
            if(num > maximum) {
                maximum = num;
                max_i   = i;
            }
        }
        cout << maximum << endl
             << max_i;
        return 0;
    }
 
    int acwing713::main(istream &cin, ostream &cout) {
        int n;
        unsigned int in  = 0;
        unsigned int out = 0;
        cin >> n;
        for(int i = 0; i < n; i++) {
            int num;
            cin >> num;
            if(10 <= num && num <= 20) {
                in++;
            } else {
                out++;
            }
        }
        cout << in << " in" << endl
             << out << " out";
        return 0;
    }
 
    int acwing721::main(istream &cin, ostream &cout) {
        unsigned short x;
        while(cin >> x) {
            if(x == 0) {
                return 0;
            }
            for(int i = 1; i <= x; i++) {
                cout << i << " ";
            }
            cout << endl;
        }
        return 0;
    }
 
    int acwing719::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        for(unsigned short i = 0; i < n; i++) {
            int count = 0;
            int x;
            int y;
            cin >> x >> y;
            if(x > y) {
                const int temp = y;
                y              = x;
                x              = temp;
            }
            if(x % 2 == 0) {
                x++;
            } else {
                x += 2;
            }
            for(int j = x; j < y; j += 2) {
                count += j;
            }
            cout << count << endl;
        }
        return 0;
    }
 
    int acwing1875::main(istream &cin, ostream &cout) {
        auto b = vector<int>();
        auto e = vector<int>();
        auto s = vector<int>();
        auto i = vector<int>();
        auto g = vector<int>();
        auto o = vector<int>();
        auto m = vector<int>();
        unsigned short n;
        cin >> n;
        for(unsigned short j = 0; j < n; j++) {
            char ch;
            int val;
            cin >> ch >> val;
            switch(ch) {
                case 'B':
                    b.push_back(val);
                    break;
                case 'E':
                    e.push_back(val);
                    break;
                case 'S':
                    s.push_back(val);
                    break;
                case 'I':
                    i.push_back(val);
                    break;
                case 'G':
                    g.push_back(val);
                    break;
                case 'O':
                    o.push_back(val);
                    break;
                case 'M':
                    m.push_back(val);
                    break;
                default: return 1;
            }
        }
        unsigned int count_a = 0;
        for(const auto ms: m) {
            if(ms % 2 != 0) {
                count_a++;
            }
        }
        unsigned int count_b = 0;
        for(const auto bs: b) {
            for(const auto is: i) {
                if((bs + is) % 2 != 0) {
                    count_b++;
                }
            }
        }
        unsigned int count_c = 0;
        for(const auto gs: g) {
            for(const auto os: o) {
                for(const auto es: e) {
                    for(const auto ss: s) {
                        if((gs + os + es + ss) % 2 != 0) {
                            count_c++;
                        }
                    }
                }
            }
        }
        const unsigned long long count = b.size() * e.size() * s.size() * i.size() * g.size() * o.size() * m.size();
        cout << count - count_a * count_b * count_c;
        return 0;
    }
 
    int acwing720::main(istream &cin, ostream &cout) {
        int a;
        int count = 0;
        cin >> a;
        int n;
        do {
            cin >> n;
        } while(n <= 0);
        for(int i = 0; i < n; i++) {
            count += a + i;
        }
        cout << count;
        return 0;
    }
 
    int acwing717::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        auto fibb = vector<unsigned int>();
        fibb.resize(n);
        fibb[0] = 0;
        fibb[1] = 1;
        for(unsigned short i = 2; i < n; i++) {
            fibb[i] = fibb[i - 1] + fibb[i - 2];
        }
        for(const auto num: fibb) {
            cout << num << " ";
        }
        return 0;
    }
 
    int acwing1855::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        auto hay = vector<unsigned int>();
        for(unsigned short i = 0; i < n; i++) {
            unsigned int x;
            cin >> x;
            hay.push_back(x);
        }
        sort(hay.begin(), hay.end());
        unsigned int maximum = 0;
        for(auto start = hay.begin(); start != hay.end(); ++start) {
            bool left_end  = false;
            bool right_end = false;
            auto left      = start;
            auto right     = start;
            for(int i = 1;; i++) {
                if(!left_end) {
                    auto l = lower_bound(hay.begin(), hay.end(), *left - i);
                    if(l == hay.end() || l == left) {
                        left_end = true;
                    } else {
                        left = l;
                    }
                }
                if(!right_end) {
                    auto r = upper_bound(hay.begin(), hay.end(), *right + i) - 1;
                    if(r == hay.end() || r == right) {
                        right_end = true;
                    } else {
                        right = r;
                    }
                }
                if(left_end && right_end) {
                    maximum = max(maximum, static_cast<unsigned int>(right - left) + 1);
                    break;
                }
            }
        }
        cout << maximum;
        return 0;
    }
 
    int acwing724::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        cout << 1 << endl;
        for(unsigned short i = 2; i < n; i++) {
            if(n % i == 0) {
                cout << i << endl;
            }
        }
        if(n != 1) {
            cout << n;
        }
        return 0;
    }
 
    int acwing722::main(istream &cin, ostream &cout) {
        int count = 0;
        int m;
        int n;
        cin >> m >> n;
        while(n > 0 && m > 0) {
            if(m > n) {
                swap(m, n);
            }
            for(int i = m; i <= n; i++) {
                cout << i << " ";
            }
            count += 2 * (m + n);
            cout << "Sum=" << (n - m + 1) * (m + n) / 2 << endl;
            cin >> m >> n;
        }
        return 0;
    }
 
    int acwing1843::main(istream &cin, ostream &cout) {
        unsigned short n;
        unsigned int min = 0;
        cin >> n;
        auto *r = new unsigned short[n];
        for(unsigned short i = 0; i < n; i++) {
            cin >> r[i];
        }
        for(unsigned short i = 0; i < n; i++) {
            unsigned int count = 0;
            for(unsigned short j = 0; j < n - 1; j++) {
                count += r[(i - j + n) % n] * (n - j - 1);
            }
            if(min == 0 || min > count) {
                min = count;
            }
        }
        cout << min;
        delete[] r;
        return 0;
    }
 
    int acwing723::main(istream &cin, ostream &cout) {
        unsigned short n;
        unsigned short m;
        cin >> n >> m;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(j != m - 1) {
                    cout << i * m + j + 1 << " ";
                } else {
                    cout << "PUM" << endl;
                }
            }
        }
        return 0;
    }
 
    int acwing725::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        unsigned int x;
        for(unsigned short i = 0; i < n; i++) {
            cin >> x;
            unsigned int count = 1;
            const auto max     = static_cast<unsigned int>(sqrt(static_cast<double>(x)));
            for(unsigned int j = 2; j <= max; j++) {
                if(x % j == 0) {
                    count += j;
                    count += x / j;
                    if(j == x / j) {
                        count -= j;
                    }
                }
            }
            cout << x;
            if(x == 1 || count != x) {
                cout << " is not perfect";
            } else {
                cout << " is perfect";
            }
            cout << endl;
        }
        return 0;
    }
 
    namespace acwing1826 {
        int acwing1826::main(istream &cin, ostream &cout) {
            unsigned int n;
            unsigned int x;
            unsigned int y;
            cin >> n;
            multiset<pair<unsigned int, unsigned int>, cmprow> row;
            multiset<pair<unsigned int, unsigned int>, cmpcol> col;
            for(unsigned int i = 0; i < n; i++) {
                cin >> x >> y;
                row.insert(pair(x, y));
                col.insert(pair(x, y));
            }
            unsigned int minimum = ((*row.rbegin()).first - (*row.begin()).first) * ((*col.rbegin()).second - (*col.begin()).second);
 
            auto row_cpy = multiset(row);
            auto col_cpy = multiset(col);
            auto r_pair  = *row_cpy.begin();
            row_cpy.erase(row_cpy.find(r_pair));
            col_cpy.erase(col_cpy.find(r_pair));
            minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
 
            row_cpy = multiset(row);
            col_cpy = multiset(col);
            r_pair  = *row_cpy.rbegin();
            row_cpy.erase(row_cpy.find(r_pair));
            col_cpy.erase(col_cpy.find(r_pair));
            minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
 
            row_cpy     = multiset(row);
            col_cpy     = multiset(col);
            auto c_pair = *col_cpy.begin();
            row_cpy.erase(row_cpy.find(c_pair));
            col_cpy.erase(col_cpy.find(c_pair));
            minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
 
            row_cpy = multiset(row);
            col_cpy = multiset(col);
            c_pair  = *col_cpy.rbegin();
            row_cpy.erase(row_cpy.find(c_pair));
            col_cpy.erase(col_cpy.find(c_pair));
            minimum = min(minimum, ((*row_cpy.rbegin()).first - (*row_cpy.begin()).first) * ((*col_cpy.rbegin()).second - (*col_cpy.begin()).second));
 
            cout << minimum;
            return 0;
        }
 
        bool cmprow::operator()(const pair<unsigned int, unsigned int> &left, const pair<unsigned int, unsigned int> &right) const { return left.first < right.first; }
 
        bool cmpcol::operator()(const pair<unsigned int, unsigned int> &left, const pair<unsigned int, unsigned int> &right) const { return left.second < right.second; }
    }// namespace acwing1826
 
    int acwing1813::main(istream &cin, ostream &cout) {
        int n;
        int charmap[26] = {};
        cin >> n;
        for(int i = 0; i < n; i++) {
            int charmap_a[26] = {};
            int charmap_b[26] = {};
            string a;
            string b;
            cin >> a >> b;
            for(const char ch: a) {
                charmap_a[ch - 'a']++;
            }
            for(const char ch: b) {
                charmap_b[ch - 'a']++;
            }
            for(int j = 0; j < 26; j++) {
                charmap[j] += max(charmap_a[j], charmap_b[j]);
            }
        }
        for(const int i: charmap) {
            cout << i << endl;
        }
        return 0;
    }
 
    int acwing726::main(istream &cin, ostream &cout) {
        int n;
        int x;
        cin >> n;
        for(int i = 0; i < n; i++) {
            cin >> x;
            for(int j = 2; j <= sqrt(x); j++) {
                if(x % j == 0) {
                    cout << x << " is not prime" << endl;
                    goto next;
                }
            }
            cout << x << " is prime" << endl;
        next:;
        }
        return 0;
    }
 
    int acwing727::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for(int i = 0; i <= n / 2; i++) {
            for(int j = 0; j < n / 2 - i; j++) {
                cout << ' ';
            }
            for(int k = 0; k < 1 + 2 * i; k++) {
                cout << '*';
            }
            cout << endl;
        }
        for(int i = n / 2 + 1; i < n; i++) {
            for(int j = 0; j < i - n / 2; j++) {
                cout << ' ';
            }
            for(int k = 0; k < 1 + 2 * (n - i - 1); k++) {
                cout << '*';
            }
            cout << endl;
        }
        return 0;
    }
 
    int acwing737::main(istream &cin, ostream &cout) {
        short x;
        for(int i = 0; i < 10; i++) {
            cin >> x;
            if(x <= 0) {
                x = 1;
            }
            cout << "X[" << i << "] = " << x << endl;
        }
        return 0;
    }
 
    int acwing740::main(istream &cin, ostream &cout) {
        short n[20];
        for(int i = 0; i < 20; i++) {
            cin >> n[20 - i - 1];
        }
        for(int i = 0; i < 20; i++) {
            cout << "N[" << i << "] = " << n[i] << endl;
        }
        return 0;
    }
 
    int acwing1801::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int count_123 = 0;
        int count_132 = 0;
        int count_213 = 0;
        int count_231 = 0;
        int count_312 = 0;
        int count_321 = 0;
        for(int i = 0; i < n; i++) {
            int a;
            int b;
            cin >> a >> b;
            if(a == 1 && b == 2) {
                count_132++;
                count_213++;
                count_321++;
            } else if(a == 1 && b == 3) {
                count_123++;
                count_231++;
                count_312++;
            } else if(a == 2 && b == 1) {
                count_123++;
                count_231++;
                count_312++;
            } else if(a == 2 && b == 3) {
                count_132++;
                count_213++;
                count_321++;
            } else if(a == 3 && b == 1) {
                count_132++;
                count_213++;
                count_321++;
            } else if(a == 3 && b == 2) {
                count_123++;
                count_231++;
                count_312++;
            }
        }
        int maximum = count_123;
        maximum     = max(maximum, count_132);
        maximum     = max(maximum, count_213);
        maximum     = max(maximum, count_231);
        maximum     = max(maximum, count_312);
        maximum     = max(maximum, count_321);
        cout << maximum;
        return 0;
    }
 
    int acwing4215::main(istream &cin, ostream &cout) {
        char ch;
        while(cin >> ch) {
            if(isupper(ch) != 0) {
                ch = tolower(ch);
            }
            if(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'y') {
                continue;
            }
            cout << '.' << ch;
        }
        return 0;
    }
 
    int acwing4216::main(istream &cin, ostream &cout) {
        unsigned short n;
        unsigned short m;
        unsigned short a;
        unsigned short b;
        cin >> n >> m;
        auto flag = vector(n, false);
        auto edge = vector(n, unordered_set<unsigned short>());
        for(unsigned short i = 0; i < m; i++) {
            cin >> a >> b;
            edge[a - 1].insert(b - 1);
            edge[b - 1].insert(a - 1);
        }
        int circle = 0;
        auto que   = queue<pair<unsigned short, unsigned short>>();
        que.push(pair(0, 0));
        flag[0] = true;
        while(!que.empty()) {
            auto [prev, current] = que.front();
            que.pop();
            for(auto next: edge[current]) {
                if(next != prev) {
                    if(flag[next]) {
                        if(circle == 2) {
                            cout << "NO";
                            return 0;
                        }
                        circle += 1;
                    } else {
                        que.push(pair(current, next));
                        flag[next] = true;
                    }
                }
            }
        }
        for(unsigned short i = 0; i < n; i++) {
            if(!flag[i]) {
                cout << "NO";
                return 0;
            }
        }
        if(circle != 2) {
            cout << "NO";
            return 0;
        }
        cout << "YES";
        return 0;
    }
 
    int acwing4217::main(istream &cin, ostream &cout) {
        cin >> n;
        ops   = vector<char>();
        forth = vector<pair<int, int>>();
        back  = vector<pair<int, int>>();
        ops.resize(n);
        forth.emplace_back(0, 0);
        for(int i = 0; i < n; i++) {
            cin >> ops[i];
            switch(ops[i]) {
                case 'U': {
                    forth.emplace_back(forth.back().first, forth.back().second + 1);
                    break;
                }
                case 'D': {
                    forth.emplace_back(forth.back().first, forth.back().second - 1);
                    break;
                }
                case 'L': {
                    forth.emplace_back(forth.back().first - 1, forth.back().second);
                    break;
                }
                case 'R': {
                    forth.emplace_back(forth.back().first + 1, forth.back().second);
                    break;
                }
            }
        }
        cin >> a >> b;
        if(forth.back().first == a && forth.back().second == b) {
            cout << 0;
            return 0;
        }
        if(n < abs(a) + abs(b) || (n - (abs(a) + abs(b))) % 2 != 0) {
            cout << -1;
            return 0;
        }
        back.emplace_back(a, b);
        for(int i = n - 1; i >= 0; i--) {
            switch(ops[i]) {
                case 'U': {
                    back.emplace_back(back.back().first, back.back().second - 1);
                    break;
                }
                case 'D': {
                    back.emplace_back(back.back().first, back.back().second + 1);
                    break;
                }
                case 'L': {
                    back.emplace_back(back.back().first + 1, back.back().second);
                    break;
                }
                case 'R': {
                    back.emplace_back(back.back().first - 1, back.back().second);
                    break;
                }
            }
        }
        back  = vector(back.rbegin(), back.rend());
        int l = 1;
        int r = n;
        while(l < r) {
            const int mid = (l + r) / 2;
            if(check(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        cout << l;
        return 0;
    }
 
    bool acwing4217::check(int len) const {
        for(int i = 0; i + len < n + 1; i++) {
            const auto s    = forth[i];
            const auto e    = back[i + len];
            const auto dist = abs(s.first - e.first) + abs(s.second - e.second);
            if(len - dist >= 0 && (len - dist) % 2 == 0) {
                return true;
            }
        }
        return false;
    }
 
    int acwing738::main(istream &cin, ostream &cout) {
        unsigned int v;
        cin >> v;
        for(int i = 0; i < 10; i++) {
            cout << "N[" << i << "] = " << v * static_cast<unsigned int>(pow(2, i)) << endl;
        }
        return 0;
    }
 
    int acwing741::main(istream &cin, ostream &cout) {
        unsigned int t;
        unsigned short n;
        cin >> t;
        unsigned int fib[60];
        fib[0] = 0;
        fib[1] = 1;
        for(int i = 2; i < 60; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        for(unsigned i = 0; i < t; i++) {
            cin >> n;
            cout << "Fib(" << n << ") = " << fib[n] << endl;
        }
        return 0;
    }
 
    int acwing1789::main(istream &cin, ostream &cout) {
        char str[52];
        int count  = 0;
        auto poses = vector(26, vector<int>());
        for(int i = 0; i < 52; i++) {
            char ch;
            cin >> ch;
            str[i] = ch;
            poses[ch - 'A'].push_back(i);
        }
        for(auto pos: poses) {
            auto um = unordered_map<int, int>();
            for(int i = pos[0] + 1; i < pos[1]; i++) {
                if(!um.contains(str[i])) {
                    um.insert(pair(str[i], 1));
                } else {
                    um[str[i]] = 0;
                }
            }
            for(const auto p: um) {
                if(p.second == 1) {
                    count++;
                }
            }
            um = unordered_map<int, int>();
            for(int i = pos[1] + 1; i < pos[0] + 52; i++) {
                if(!um.contains(str[i % 52])) {
                    um.insert(pair(str[i % 52], 1));
                } else {
                    um[str[i % 52]] = 0;
                }
            }
            for(const auto p: um) {
                if(p.second == 1) {
                    count++;
                }
            }
        }
        cout << count / 4;
        return 0;
    }
 
    int acwing739::main(istream &cin, ostream &cout) {
        double a;
        cout << setiosflags(ios::fixed) << setprecision(1);
        for(int i = 0; i < 100; i++) {
            cin >> a;
            if(a <= 10) {
                cout << "A[" << i << "] = " << a << endl;
            }
        }
        return 0;
    }
 
    int acwing742::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        unsigned short minimum_i = 0;
        short minimum            = 1000;
        short x;
        for(unsigned short i = 0; i < n; i++) {
            cin >> x;
            if(minimum > x) {
                minimum   = x;
                minimum_i = i;
            }
        }
        cout << "Minimum value: " << minimum << endl
             << "Position: " << minimum_i;
        return 0;
    }
 
    int acwing1776::main(istream &cin, ostream &cout) {
        int n;
        int m;
        cin >> n >> m;
        char ch;
        auto *dot = new int[m];
        memset(dot, 0, m * sizeof(int));
        auto *normal = new int[m];
        memset(normal, 0, m * sizeof(int));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cin >> ch;
                dot[j] |= 1 << ch - 'A';
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cin >> ch;
                normal[j] |= 1 << ch - 'A';
            }
        }
        int count = 0;
        for(int i = 0; i < m; i++) {
            if((dot[i] & normal[i]) == 0) {
                count++;
            }
        }
        cout << count;
        delete[] normal;
        delete[] dot;
        return 0;
    }
 
    int acwing743::main(istream &cin, ostream &cout) {
        int l;
        char op;
        double m[12][12];
        cin >> l >> op;
        for(auto &i: m) {
            for(auto &j: i) {
                cin >> j;
            }
        }
        double ans = 0;
        for(int j = 0; j < 12; j++) {
            ans += m[l][j];
        }
        if(op == 'M') {
            ans /= 12;
        }
        cout << fixed << setprecision(1) << ans;
        return 0;
    }
 
    int acwing744::main(istream &cin, ostream &cout) {
        int l;
        char op;
        double m[12][12];
        cin >> l >> op;
        for(auto &i: m) {
            for(auto &j: i) {
                cin >> j;
            }
        }
        double ans = 0;
        for(const auto &j: m) {
            ans += j[l];
        }
        if(op == 'M') {
            ans /= 12;
        }
        cout << fixed << setprecision(1) << ans;
        return 0;
    }
 
    int acwing745::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(j > i) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing748::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(i + j >= 12) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing1762::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *a  = new int[n + 1];
        auto *id = new string[n + 1];
        for(int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for(int i = 1; i <= n; i++) {
            cin >> id[i];
        }
        for(int i = 1; i <= n; i++) {
            cout << id[a[a[a[i]]]] << endl;
        }
        delete[] a;
        delete[] id;
        return 0;
    }
 
    int acwing1750::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto start  = unordered_set<int>();
        auto end    = unordered_set<int>();
        auto t      = vector<pair<int, int>>();
        auto levels = vector<int>();
        levels.resize(1000);
        for(int i = 0; i < n; i++) {
            int t1;
            int t2;
            cin >> t1 >> t2;
            start.insert(t1);
            end.insert(t2);
            t.emplace_back(make_pair(t1, t2));
        }
        int level   = 0;
        int maximum = 0;
        for(int i = 0; i < 1000; i++) {
            if(start.count(i) == 1) {
                level++;
            }
            if(end.count(i) == 1) {
                level--;
            }
            levels[i] = level;
            if(level > 0) {
                maximum++;
            }
        }
        int ans = 0;
        for(auto [t1, t2]: t) {
            int len = maximum;
            for(int i = t1; i < t2; i++) {
                if(levels[i] == 1) {
                    len--;
                }
            }
            ans = max(ans, len);
        }
        cout << ans;
        return 0;
    }
 
    int acwing747::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(i + j < 11) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing746::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(j < i) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing1738::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        if(n == 1 || n == 2) {
            cout << 1;
            return 0;
        }
        auto *x   = new int[n];
        auto *jmp = new int[n];
        auto *in  = new int[n];
        memset(in, 0, n * sizeof(int));
        for(int i = 0; i < n; i++) {
            cin >> x[i];
        }
        sort(x, x + n);
        in[1]      = 1;
        in[n - 2]  = 1;
        jmp[0]     = 1;
        jmp[n - 1] = n - 2;
        for(int i = 1; i < n - 1; i++) {
            if(x[i + 1] - x[i] < x[i] - x[i - 1]) {
                in[i + 1]++;
                jmp[i] = i + 1;
            } else {
                in[i - 1]++;
                jmp[i] = i - 1;
            }
        }
        int circle_count = 0;
        int ans          = 0;
        for(int i = 0; i < n; i++) {
            if(in[i] == 0) {
                ans++;
            }
            if(jmp[jmp[i]] == i && in[i] == 1 && in[jmp[i]] == 1) {
                circle_count++;
            }
        }
        circle_count /= 2;
        cout << ans + circle_count;
        delete[] x;
        delete[] in;
        delete[] jmp;
        return 0;
    }
 
    int acwing4296::main(istream &cin, ostream &cout) {
        int n;
        int a;
        int b;
        cin >> n >> a >> b;
        for(int i = 0; a * i <= n; i++) {
            for(int j = 0; a * i + b * j <= n; j++) {
                if(a * i + b * j == n) {
                    cout << "YES" << endl
                         << i << endl
                         << j;
                    return 0;
                }
            }
        }
        cout << "NO";
        return 0;
    }
 
    int acwing4297::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        unsigned int d[200000];
        unsigned long long left[200001];
        unsigned long long right[200001];
        for(int i = 0; i < n; i++) {
            cin >> d[i];
        }
        left[0] = 0;
        auto us = unordered_map<unsigned long long, unsigned int>();
        us.insert(make_pair(0, 0));
        for(int i = 1; i <= n; i++) {
            left[i] = left[i - 1] + d[i - 1];
            us.insert(make_pair(left[i], i));
        }
        right[n]               = 0;
        unsigned long long ans = 0;
        for(int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + d[i];
            if(us.count(right[i]) == 1) {
                if(us[right[i]] <= i) {
                    ans = max(ans, right[i]);
                }
            }
        }
        cout << ans;
        return 0;
    }
 
    int acwing4298::main(istream &cin, ostream &cout) {
        cin >> n;
        a = new int[n];
        memset(a, 0, n * sizeof(int));
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cin >> m;
        b     = new int[m];
        found = new bool[m];
        match = new int[m];
        memset(b, 0, m * sizeof(int));
        memset(found, 0, m * sizeof(bool));
        memset(match, -1, m * sizeof(int));
        for(int i = 0; i < m; i++) {
            cin >> b[i];
        }
        connected = new bool *[n];
        for(int i = 0; i < n; i++) {
            connected[i] = new bool[m];
            for(int j = 0; j < m; j++) {
                if(abs(a[i] - b[j]) <= 1) {
                    connected[i][j] = true;
                } else {
                    connected[i][j] = false;
                }
            }
        }
 
        int ans = 0;
        for(int i = 0; i < n; i++) {
            memset(found, 0, m * sizeof(bool));
            if(find(i)) {
                ans++;
            }
        }
        cout << ans;
        for(int i = 0; i < n; i++) {
            delete[] connected[i];
        }
        delete[] connected;
        delete[] a;
        delete[] b;
        delete[] found;
        delete[] match;
        return 0;
    }
 
    bool acwing4298::find(int i) {
        for(int j = 0; j < m; j++) {
            if(connected[i][j] && !found[j]) {
                //可以配对且女孩未被找到
                found[j] = true;
                if(match[j] == -1 || find(match[j])) {
                    //女孩没有配对的对象或女孩配对的对象可以找到其他对象去配对
                    match[j] = i;//设置女孩j和男孩i配对
                    return true;
                }
            }
        }
        return false;
    }
 
    int acwing749::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(j > i && i + j < 11) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing750::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(i + j > 11 && i > j) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing751::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(i + j < 11 && i > j) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing752::main(istream &cin, ostream &cout) {
        char op;
        cin >> op;
        double sum = 0;
        int count  = 0;
        double m[12][12];
        for(int i = 0; i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                cin >> m[i][j];
                if(i + j > 11 && i < j) {
                    sum += m[i][j];
                    count++;
                }
            }
        }
        if(op == 'M') {
            sum /= count;
        }
        cout << fixed << setprecision(1) << sum;
        return 0;
    }
 
    int acwing1726::main(istream &cin, ostream &cout) {
        int N;
        int M;
        int K;
        cin >> N >> M >> K;
        unordered_set<int> ms;
        auto *const m = new int[M];
        auto *const n = new int[N + 1];
        memset(n, -1, (N + 1) * sizeof(int));
        for(int i = 0; i < M; i++) {
            cin >> m[i];
            ms.insert(m[i]);
        }
        auto cp = unordered_map<int, int>();
        for(int i = 0; i < K; i++) {
            int c;
            int p;
            cin >> c >> p;
            n[p] = c;
            cp.insert(make_pair(c, p));
        }
        if(cp.contains(1)) {
            //固定
            cout << cp[1];
            delete[] n;
            delete[] m;
            return 0;
        }
        if(ms.contains(1)) {
            //在阶级中
            int current = 1;
            for(int i = 0; i < M; i++) {
                //对所有阶级
                if(cp.contains(m[i])) {
                    //是固定的
                    current = cp[m[i]];
                    continue;
                }
                //不是固定的
                while(n[current] != -1) {
                    current++;
                }
                n[current] = m[i];
                if(m[i] == 1) {
                    cout << current;
                    delete[] n;
                    delete[] m;
                    return 0;
                }
            }
        }
        //不在阶级中
        int current = N;
        for(int i = M - 1; i >= 0; i--) {
            if(cp.contains(m[i])) {
                //是固定的
                current = cp[m[i]];
                continue;
            }
            //不是固定的
            while(n[current] != -1) {
                current--;
            }
            n[current] = m[i];
        }
        for(int i = 1; i <= N; i++) {
            if(n[i] == -1) {
                cout << i;
                break;
            }
        }
        delete[] n;
        delete[] m;
        return 0;
    }
 
    int acwing753::main(istream &cin, ostream &cout) {
        int n;
        while(true) {
            cin >> n;
            if(n == 0) {
                break;
            }
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    cout << min(min(i, j), min(n - i - 1, n - j - 1)) + 1 << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
        return 0;
    }
 
    int acwing754::main(istream &cin, ostream &cout) {
        int n;
        while(true) {
            cin >> n;
            if(n == 0) {
                break;
            }
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    cout << abs(j - i) + 1 << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
        return 0;
    }
 
    int acwing1715::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto sb = unordered_map<int, int>();
        auto tb = unordered_map<int, int>();
        for(int i = 0; i < n; i++) {
            int s;
            int t;
            int b;
            cin >> s >> t >> b;
            sb.insert(make_pair(s, b));
            tb.insert(make_pair(t, b));
        }
        int ans     = 0;
        int current = 0;
        for(int i = 1; i <= 1000; i++) {
            if(sb.count(i) == 1) {
                current += sb[i];
            } else if(tb.count(i) == 1) {
                current -= tb[i];
            }
            ans = max(ans, current);
        }
        cout << ans;
        return 0;
    }
 
    int acwing755::main(istream &cin, ostream &cout) {
        int n;
        while(true) {
            cin >> n;
            if(n == 0) {
                break;
            }
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    cout << static_cast<int>(pow(2, i + j)) << " ";
                }
                cout << endl;
            }
            cout << endl;
        }
        return 0;
    }
 
    int acwing756::main(istream &cin, ostream &cout) {
        int n;
        int m;
        int arr[100][100] = {};
        int x             = 0;
        int y             = 0;
        int v             = 1;
        int dir           = 1;//0 上 1 右 2 下 3 左
        cin >> n >> m;
        while(v <= n * m) {
            arr[x][y] = v++;
        move:;
            if(v > m * n) {
                break;
            }
            switch(dir) {
                case 3://左
                {
                    const int next_y = y - 1;
                    if(arr[x][next_y] != 0 || next_y < 0) {
                        //不能向上
                        dir = (dir + 1) % 4;
                        goto move;
                    }
                    y--;
                    break;
                }
                case 2://下
                {
                    const int next_x = x + 1;
                    if(arr[next_x][y] != 0 || next_x >= n) {
                        dir = (dir + 1) % 4;
                        goto move;
                    }
                    x++;
                    break;
                }
                case 1://右
                {
                    const int next_y = y + 1;
                    if(arr[x][next_y] != 0 || next_y >= m) {
                        dir = (dir + 1) % 4;
                        goto move;
                    }
                    y++;
                    break;
                }
                case 0://上
                {
                    const int next_x = x - 1;
                    if(arr[next_x][y] != 0 || next_x < 0) {
                        dir = (dir + 1) % 4;
                        goto move;
                    }
                    x--;
                    break;
                }
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                cout << arr[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }
 
    int acwing1696::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *const p = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> p[i];
        }
        int i = n - 1;
        for(int j = i - 1; j >= 0 && p[j] < p[i]; i--, j--) {}
        cout << i;
        delete[] p;
        return 0;
    }
 
    int acwing760::main(istream &cin, ostream &cout) {
        auto *str = new char[101];
        cin.getline(str, 101);
        for(int i = 0; i < 101; i++) {
            if(str[i] == '\0') {
                cout << i;
                break;
            }
        }
        return 0;
    }
 
    int acwing762::main(istream &cin, ostream &cout) {
        double k;
        string a;
        string b;
        int match = 0;
        cin >> k >> a >> b;
        for(int i = 0; i < a.length(); i++) {
            if(a[i] == b[i]) {
                match++;
            }
        }
        cout << (match >= k * a.length() ? "yes" : "no");
        return 0;
    }
 
    int acwing1684::main(istream &cin, ostream &cout) {
        int n;
        int m;
        cin >> n >> m;
        bitset<151> ns[101] = {};
        bitset<151> ans[4]  = {};
        for(int i = 1; i <= m; i++) {
            int m1;
            int m2;
            cin >> m1 >> m2;
            ns[m1].set(i);
            ns[m2].set(i);
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 4; j++) {
                if((ns[i] & ans[j]) == 0) {
                    cout << j + 1;
                    ans[j] |= ns[i];
                    break;
                }
            }
        }
        return 0;
    }
 
    int acwing761::main(istream &cin, ostream &cout) {
        auto *str = new char[101];
        cin.getline(str, 101);
        unsigned short ans = 0;
        for(unsigned short i = 0; str[i] != '\0'; i++) {
            if(isdigit(str[i]) != 0) {
                ans++;
            }
        }
        cout << ans;
        delete[] str;
        return 0;
    }
 
    int acwing768::main(istream &cin, ostream &cout) {
        auto *a = new char[81];
        auto *b = new char[81];
        cin.getline(a, 81);
        cin.getline(b, 81);
        for(int i = 0;; i++) {
            if(isupper(a[i]) != 0) {
                a[i] = tolower(a[i]);
            }
            if(isupper(b[i]) != 0) {
                b[i] = tolower(b[i]);
            }
            if(a[i] == '\0' && b[i] == '\0') {
                cout << '=';
                break;
            }
            if(a[i] < b[i]) {
                cout << '<';
                break;
            }
            if(a[i] > b[i]) {
                cout << '>';
                break;
            }
        }
        delete[] a;
        delete[] b;
        return 0;
    }
 
    int acwing1471::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *in  = new int[n];
        auto *out = new int[n];
        memset(in, 0, n * sizeof(int));
        memset(out, 0, n * sizeof(int));
        int a;
        int b;
        for(int i = 0; i < n - 1; i++) {
            cin >> a >> b;
            out[a - 1]++;
            in[b - 1]++;
        }
        bool ok = true;
        int ans = -1;
        for(int i = 0; i < n; i++) {
            if(in[i] > 0 && out[i] == 0) {
                if(ans != -1) {
                    ok = false;
                    break;
                }
                ans = i;
            }
            if(in[i] == 0 && out[i] > 1) {
                ok = false;
                break;
            }
        }
        if(ok) {
            cout << ans + 1;
        } else {
            cout << -1;
        }
        delete[] in;
        delete[] out;
        return 0;
    }
 
    int acwing763::main(istream &cin, ostream &cout) {
        int t;
        cin >> t;
        for(int i = 0; i < t; i++) {
            string str1;
            string str2;
            cin >> str1 >> str2;
            if(str1 == str2) {
                cout << "Tie";
            } else if(str1 == "Hunter" && str2 == "Gun" || str1 == "Gun" && str2 == "Bear" || str1 == "Bear" && str2 == "Hunter") {
                cout << "Player1";
            } else {
                cout << "Player2";
            }
            cout << endl;
        }
        return 0;
    }
 
    int acwing766::main(istream &cin, ostream &cout) {
        auto *str = new char[201];
        cin.getline(str, 201);
        bool flag = false;
        for(int i = 0; str[i] != '\0'; i++) {
            if(str[i] != ' ') {
                cout << str[i];
                flag = false;
            } else if(!flag) {
                cout << ' ';
                flag = true;
            }
        }
        return 0;
    }
 
    int acwing1460::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        string str;
        cin >> str;
        for(int k = 1; k <= n; k++) {
            auto us = unordered_set<string>();
            bool ok = true;
            for(int i = 0; i + k <= n; i++) {
                string nstr = str.substr(i, k);
                if(!us.contains(nstr)) {
                    us.insert(nstr);
                } else {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                cout << k;
                break;
            }
        }
        return 0;
    }
 
    int acwing4299::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int pos = 0;
        int neg = 0;
        for(int i = 0; i < n; i++) {
            int x;
            int y;
            cin >> x >> y;
            if(x > 0) {
                pos++;
            } else {
                neg++;
            }
        }
        if(pos <= 1 || neg <= 1) {
            cout << "Yes";
        } else {
            cout << "No";
        }
        return 0;
    }
 
    int acwing4300::main(istream &cin, ostream &cout) {
        int n;
        int m;
        cin >> n >> m;
        auto um  = unordered_set<int>();
        auto que = queue<pair<int, int>>();
        que.push(make_pair(n, 0));
        um.insert(n);
        while(!que.empty()) {
            auto [current, step] = que.front();
            que.pop();
            if(current == m) {
                cout << step;
                return 0;
            }
            int k              = 1;
            const int nexts[2] = {current - 1, current * 2};
            if(current < m) {
                k = 2;
            }
            for(int i = 0; i < k; i++) {
                auto next = nexts[i];
                if(next == m) {
                    cout << step + 1;
                    return 0;
                }
                if(next > 0 && !um.contains(next)) {
                    que.push(make_pair(next, step + 1));
                    um.insert(next);
                }
            }
        }
        return 0;
    }
 
    int acwing4301::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto vec     = vector<int>();
        auto targets = unordered_set<int>();
        int sum      = 0;
        int maximum  = 0;
        char ch;
        vec.resize(n);
        for(int i = 0; i < n; i++) {
            cin >> ch;
            int a  = ch - '0';
            vec[i] = a;
            sum += a;
            maximum = max(maximum, a);
        }
        if(sum == 0) {
            cout << "YES";
            return 0;
        }
        for(int i = maximum; i <= sum / 2; i++) {
            if(sum % i == 0) {
                targets.insert(i);
            }
        }
        for(const auto target: targets) {
            int current = 0;
            bool ok     = true;
            for(int i = 0; i < n; i++) {
                current += vec[i];
                if(current == target) {
                    current = 0;
                } else if(current > target) {
                    ok = false;
                    break;
                }
            }
            if(ok && current == 0) {
                cout << "YES";
                return 0;
            }
        }
        cout << "NO";
        return 0;
    }
 
    int acwing765::main(istream &cin, ostream &cout) {
        auto *str = new char[101];
        cin.getline(str, 101);
        for(int i = 0; str[i] != '\0'; i++) {
            cout << str[i] << " ";
        }
        delete[] str;
        return 0;
    }
 
    int acwing767::main(istream &cin, ostream &cout) {
        auto *str = new char[101];
        cin.getline(str, 101);
        for(int i = 0; str[i] != '\0'; i++) {
            if(isupper(str[i]) != 0) {
                str[i] = (str[i] - 'A' + 1) % 26 + 'A';
            } else if(islower(str[i]) != 0) {
                str[i] = (str[i] - 'a' + 1) % 26 + 'a';
            }
            cout << str[i];
        }
        delete[] str;
        return 0;
    }
 
    int acwing769::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        char ch;
        cin >> ch;
        for(char c: str) {
            if(c == ch) {
                c = '#';
            }
            cout << c;
        }
        return 0;
    }
 
    int acwing764::main(istream &cin, ostream &cout) {
        auto *a = new char[101];
        cin.getline(a, 101);
        const int len = strlen(a);
        for(int i = 1; i <= len; i++) {
            cout << static_cast<char>(a[(i - 1) % len] + a[i % len]);
        }
        delete[] a;
        return 0;
    }
 
    int acwing1443::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *a = new int[n];
        auto *b = new int[n - 1];
        for(int i = 0; i < n - 1; i++) {
            cin >> b[i];
        }
        for(int i = 1; i <= n; i++) {
            auto us   = unordered_set<int>();
            bool flag = true;
            a[0]      = i;
            for(int j = 1; j < n; j++) {
                a[j] = b[j - 1] - a[j - 1];
                if(us.contains(a[j]) || a[j] <= 0) {
                    flag = false;
                    break;
                }
                us.insert(a[j]);
 
                us.insert(a[j]);
            }
            if(flag) {
                for(int j = 0; j < n; j++) {
                    cout << a[j] << " ";
                }
                break;
            }
        }
        delete[] b;
        delete[] a;
        return 0;
    }
 
    int acwing773::main(istream &cin, ostream &cout) {
        string str;
        string substr;
        while(cin >> str) {
            cin >> substr;
            auto oss  = ostringstream();
            int max_i = 0;
            for(int i = 0; i < str.length(); i++) {
                if(str[i] > str[max_i]) {
                    max_i = i;
                }
            }
            oss << str.substr(0, max_i + 1);
            oss << substr;
            oss << str.substr(max_i + 1);
            cout << oss.str() << endl;
        }
        return 0;
    }
 
    int acwing770::main(istream &cin, ostream &cout) {
        auto *str            = new char[101];
        auto *to_be_replaced = new char[101];
        auto *replacement    = new char[101];
        cin.getline(str, 101);
        cin.getline(to_be_replaced, 101);
        cin.getline(replacement, 101);
        for(const char *word = strtok(str, " "); word != nullptr; word = strtok(nullptr, " ")) {
            if(strcmp(word, to_be_replaced) == 0) {
                cout.write(replacement, strlen(replacement));
            } else {
                cout.write(word, strlen(word));
            }
            cout << " ";
        }
        delete[] str;
        delete[] to_be_replaced;
        delete[] replacement;
        return 0;
    }
 
    int acwing1672::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        string a;
        string b;
        cin >> a >> b;
        bool prev_eq = true;
        int ans      = 0;
        for(int i = 0; i < n; i++) {
            if(a[i] == b[i]) {
                if(!prev_eq) {
                    ans++;
                }
                prev_eq = true;
            } else {
                prev_eq = false;
            }
        }
        if(!prev_eq) {
            ans++;
        }
        cout << ans;
        return 0;
    }
 
    int acwing772::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        int charset[26] = {};
        for(const char ch: str) {
            charset[ch - 'a']++;
        }
        for(const char ch: str) {
            if(charset[ch - 'a'] == 1) {
                cout << ch;
                return 0;
            }
        }
        cout << "no";
        return 0;
    }
 
    int acwing771::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            string str;
            cin >> str;
            char ch_max   = str[0];
            int count_max = 1;
            char ch       = str[0];
            int count     = 1;
            for(int j = 1; j < str.length(); j++) {
                if(str[j] == str[j - 1]) {
                    count++;
                } else {
                    if(count > count_max) {
                        count_max = count;
                        ch_max    = ch;
                    }
                    ch    = str[j];
                    count = 1;
                }
            }
            if(count > count_max) {
                count_max = count;
                ch_max    = ch;
            }
            cout << ch_max << " " << count_max << endl;
        }
        return 0;
    }
 
    namespace acwing1660 {
        int acwing1660::main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            auto cows = vector<cow>();
            for(int i = 0; i < n; i++) {
                int x;
                bool infected;
                cin >> x >> infected;
                cows.push_back(cow{x, infected});
            }
            sort(cows.begin(), cows.end());
            int r = 1000000;
            for(int i = 0; i < n; i++) {
                if(i - 1 >= 0 && cows[i].infected != cows[i - 1].infected) {
                    r = min(r, abs(cows[i].x - cows[i - 1].x));
                }
                if(i + 1 < n && cows[i].infected != cows[i + 1].infected) {
                    r = min(r, abs(cows[i].x - cows[i + 1].x));
                }
            }
            for(int i = 0; i + 1 < n; i++) {
                if(cows[i].infected && cows[i + 1].infected && abs(cows[i].x - cows[i + 1].x) < r) {
                    cows[i].infected = false;
                }
            }
            int ans = 0;
            for(int i = 0; i < n; i++) {
                if(cows[i].infected) {
                    ans++;
                }
            }
            cout << ans;
            return 0;
        }
 
        bool cow::operator<(const cow &c) const { return this->x < c.x; }
    }// namespace acwing1660
 
    int acwing774::main(istream &cin, ostream &cout) {
        auto *str = new char[501];
        cin.getline(str, 501);
        str[strlen(str) - 1]     = '\0';
        const char *longest_word = nullptr;
        int max_len              = 0;
        for(const char *word = strtok(str, " "); word != nullptr; word = strtok(nullptr, " ")) {
            if(max_len < strlen(word)) {
                max_len      = strlen(word);
                longest_word = word;
            }
        }
        cout << longest_word;
        delete[] str;
        return 0;
    }
 
    int acwing775::main(istream &cin, ostream &cout) {
        auto *str     = new char[101];
        auto *str_rev = new char *[101];
        int i         = 0;
        cin.getline(str, 101);
        for(char *word = strtok(str, " "); word != nullptr; word = strtok(nullptr, " ")) {
            str_rev[i++] = word;
        }
        for(int j = i - 1; j >= 0; j--) {
            cout << str_rev[j] << " ";
        }
        delete[] str;
        delete[] str_rev;
        return 0;
    }
 
    int acwing3347::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *flowers    = new int[n];
        auto *prefix_sum = new int[n];
        auto location    = unordered_map<int, unordered_set<int>>();
        int sum          = 0;
        for(int i = 0; i < n; i++) {
            cin >> flowers[i];
            sum += flowers[i];
            prefix_sum[i] = sum;
            location[flowers[i]].insert(i);
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                const int len = j - i + 1;
                sum           = prefix_sum[j] - (i - 1 >= 0 ? prefix_sum[i - 1] : 0);
                if(sum % len == 0) {
                    int avg = sum / len;
                    for(const auto flower: location[avg]) {
                        if(i <= flower && flower <= j) {
                            ans++;
                            break;
                        }
                    }
                }
            }
        }
        cout << ans;
        delete[] flowers;
        delete[] prefix_sum;
        return 0;
    }
 
    int acwing777::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        while(str != ".") {
            for(int i = 1; i <= str.length(); i++) {
                if(str.length() % i == 0) {
                    bool ok       = true;
                    string substr = str.substr(0, i);
                    for(int j = i; j < str.length(); j += i) {
                        if(str.substr(j, i) != substr) {
                            ok = false;
                            break;
                        }
                    }
                    if(ok) {
                        cout << str.length() / i << endl;
                        break;
                    }
                }
            }
            cin >> str;
        }
        return 0;
    }
 
    int acwing776::main(istream &cin, ostream &cout) {
        string s1;
        string s2;
        cin >> s1 >> s2;
        const string s11 = s1 + s1;
        const string s22 = s2 + s2;
        cout << boolalpha << (s11.find(s2) != string::npos || s22.find(s1) != string::npos);
        return 0;
    }
 
    int acwing4302::main(istream &cin, ostream &cout) {
        int sum_b = 0;
        int sum_c = 0;
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            int a;
            cin >> a;
            if(a > 0) {
                sum_b += a;
            } else {
                sum_c -= a;
            }
        }
        cout << sum_b + sum_c;
        return 0;
    }
 
    int acwing4303::main(istream &cin, ostream &cout) {
        int q;
        cin >> q;
        auto um = unordered_map<string, vector<string> *>();
        for(int i = 0; i < q; i++) {
            string str1;
            string str2;
            cin >> str1 >> str2;
            if(!um.contains(str1)) {
                auto *vec = new vector<string>();
                vec->push_back(str1);
                vec->push_back(str2);
                um.insert(make_pair(str2, vec));
            } else {
                um[str1]->push_back(str2);
                um[str2] = um[str1];
                um[str1] = nullptr;
            }
        }
        int count = 0;
        for(auto [k, v]: um) {
            if(v != nullptr) {
                count++;
            }
        }
        cout << count << endl;
        for(auto [k, v]: um) {
            if(v != nullptr) {
                cout << *v->begin() << " " << k << endl;
                delete v;
            }
        }
        return 0;
    }
 
    int acwing4304::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto vec = vector<unsigned int>();
        for(int i = 0; i < n; i++) {
            string str;
            cin >> str;
            auto ui   = str2int(str);
            bool flag = false;
            for(int j = 0; j < vec.size(); j++) {
                if((vec[j] & ui) != 0) {
                    vec[j] |= ui;
                    flag = true;
                }
            }
            if(!flag) {
                vec.push_back(ui);
            }
        }
        bool ok = true;
        while(ok) {
            ok = false;
            for(int i = 0; i + 1 < vec.size(); i++) {
                for(int j = i + 1; j < vec.size(); j++) {
                    if((vec[i] & vec[j]) != 0) {
                        vec[i] |= vec[j];
                        vec.erase(vec.begin() + j);
                        ok = true;
                    }
                }
            }
        }
        cout << vec.size();
        return 0;
    }
 
    unsigned int acwing4304::str2int(const string &str) {
        unsigned int ans = 0;
        for(const char ch: str) {
            ans |= 1 << ch - 'a';
        }
        return ans;
    }
 
    int acwing778::main(istream &cin, ostream &cout) {
        auto *input = new char[323];
        auto strs   = vector<string>();
        cin.getline(input, 323);
        for(char *str = strtok(input, ","); str != nullptr; str = strtok(nullptr, ",")) {
            strs.emplace_back(str);
        }
        auto l       = strs[0].find(strs[1]);
        const auto r = strs[0].rfind(strs[2]);
        if(l == string::npos || r == string::npos) {
            cout << -1;
            return 0;
        }
        l += strs[1].length();
        cout << (static_cast<int>(r) < static_cast<int>(l) ? -1 : static_cast<int>(r) - static_cast<int>(l));
        return 0;
    }
 
    int acwing779::main(istream &cin, ostream &cout) {
        while(true) {
            int n;
            cin >> n;
            if(n == 0) {
                break;
            }
            string suffix;
            cin >> suffix;
            for(int i = 1; i < n; i++) {
                string str;
                cin >> str;
                if(!suffix.empty()) {
                    auto ss = stringstream();
                    for(int j = 0; j < min(str.length(), suffix.length()) && suffix[suffix.length() - 1 - j] == str[str.length() - 1 - j]; j++) {
                        ss << suffix[suffix.length() - 1 - j];
                    }
                    string s = ss.str();
                    suffix   = string(s.rbegin(), s.rend());
                }
            }
            cout << suffix << endl;
        }
        return 0;
    }
 
    int acwing804::fact(int n) {
        if(n == 1) {
            return 1;
        }
        return n * fact(n - 1);
    }
 
    int acwing804::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        cout << fact(n);
        return 0;
    }
 
    int acwing810::abs(int n) { return n > 0 ? n : -n; }
 
    int acwing810::main(istream &cin, ostream &cout) {
        int x;
        cin >> x;
        cout << abs(x);
        return 0;
    }
 
    int acwing805::main(istream &cin, ostream &cout) {
        int x;
        int y;
        cin >> x >> y;
        cout << max(x, y);
        return 0;
    }
 
    int acwing805::max(int x, int y) { return x > y ? x : y; }
 
    int acwing806::main(istream &cin, ostream &cout) {
        double x;
        double y;
        cin >> x >> y;
        cout << fixed << setprecision(2) << add(x, y);
        return 0;
    }
 
    double acwing806::add(double x, double y) { return x + y; }
 
    int acwing808::main(istream &cin, ostream &cout) {
        int a;
        int b;
        cin >> a >> b;
        cout << gcd(a, b);
        return 0;
    }
 
    int acwing808::gcd(int a, int b) {
        while(b != 0) {
            const int t = a % b;
            a           = b;
            b           = t;
        }
        return a;
    }
 
    int acwing807::main(istream &cin, ostream &cout) {
        int l;
        int r;
        cin >> l >> r;
        cout << sum(l, r);
        return 0;
    }
 
    int acwing807::sum(int l, int r) {
        int sum = (l + r) * ((r - l + 1) / 2);
        if((r - l + 1) % 2 == 1) {
            sum += (r + l) / 2;
        }
        return sum;
    }
 
    int acwing811::main(istream &cin, ostream &cout) {
        int x;
        int y;
        cin >> x >> y;
        swap(x, y);
        cout << x << " " << y;
        return 0;
    }
 
    void acwing811::swap(int &x, int &y) {
        const int temp = x;
        x              = y;
        y              = temp;
    }
 
    int acwing809::main(istream &cin, ostream &cout) {
        int a;
        int b;
        cin >> a >> b;
        cout << lcm(a, b);
        return 0;
    }
 
    int acwing809::lcm(int a, int b) {
        const int f = acwing808::gcd(a, b);
        return a * b / f;
    }
 
    int acwing812::main(istream &cin, ostream &cout) {
        int n;
        int size;
        cin >> n >> size;
        auto *a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        print(a, size, cout);
        delete[] a;
        return 0;
    }
 
    void acwing812::print(int *a, int size, ostream &cout) {
        for(int i = 0; i < size; i++) {
            cout << a[i] << " ";
        }
    }
 
    int acwing814::main(istream &cin, ostream &cout) {
        int n;
        int m;
        int size;
        cin >> n >> m >> size;
        auto *a = new int[n];
        auto *b = new int[m];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        for(int i = 0; i < m; i++) {
            cin >> b[i];
        }
        copy(a, b, size);
        for(int i = 0; i < m; i++) {
            cout << b[i] << " ";
        }
        return 0;
    }
 
    void acwing814::copy(const int *a, int *b, int size) {
        for(int i = 0; i < size; i++) {
            b[i] = a[i];
        }
    }
 
    void acwing813::print2D(int a[][100], int row, int col, ostream &cout) {
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                cout << a[i][j] << " ";
            }
            cout << endl;
        }
    }
 
    int acwing813::main(istream &cin, ostream &cout) {
        int row;
        int col;
        cin >> row >> col;
        int arr[100][100];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                cin >> arr[i][j];
            }
        }
        print2D(arr, row, col, cout);
        return 0;
    }
 
    int acwing815::main(istream &cin, ostream &cout) {
        auto *str = new char[101];
        cin.getline(str, 101);
        print(str, cout);
        return 0;
    }
 
    void acwing815::print(char *str, ostream &cout) {
        for(int i = 0; str[i] != '\0'; i++) {
            cout << str[i];
        }
    }
 
    int acwing4305::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        char fibb[1001] = {};
        memset(fibb, 'o', sizeof fibb);
        fibb[1]           = 'O';
        unsigned int a    = 1;
        unsigned int b    = 1;
        unsigned int next = a + b;
        while(next <= n) {
            fibb[next] = 'O';
            a          = b;
            b          = next;
            next       = a + b;
        }
        for(int i = 1; i <= n; i++) {
            cout << fibb[i];
        }
        return 0;
    }
 
    int acwing4306::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        int sum      = 0;
        int addition = 0;
        for(int i = 1; i <= n; i++) {
            if(i + addition < a[i - 1]) {
                addition = a[i - 1] - i;
            }
            sum += i + addition - a[i - 1];
        }
        cout << sum;
        return 0;
    }
 
    int acwing4307::main(istream &cin, ostream &cout) {
        string a;
        string b;
        cin >> a >> b;
        auto a_count = unordered_map<int, int>();
        for(const char ch: a) {
            a_count[ch - '0']++;
        }
        if(a.length() == b.length()) {
            cout << dfs(0, false, a_count, b);
        } else {
            for(int i = 9; i >= 0; i--) {
                while(a_count[i] > 0) {
                    cout << i;
                    a_count[i]--;
                }
            }
        }
        return 0;
    }
 
    string acwing4307::dfs(int i, bool free, unordered_map<int, int> um, string &b) {
        auto oss = ostringstream();
        int j    = b[i] - '0';
        if(free) {
            goto B;
        }
        if(um[j] > 0) {
            auto um_cpy = unordered_map(um);
            um_cpy[j]--;
            if(i == b.length() - 1) {
                oss << j;
                return oss.str();
            }
            string ans = dfs(i + 1, false, um_cpy, b);
            if(!ans.empty()) {
                oss << j << ans;
            } else {
                //不可行
                goto B;
            }
        } else {
        B:;
            int k = b[i] - '0' - 1;
            if(free) {
                k = 9;
            }
            for(; k >= 0; k--) {
                if(um[k] > 0) {
                    auto um_cpy = unordered_map(um);
                    um_cpy[k]--;
                    if(i == b.length() - 1) {
                        oss << k;
                        break;
                    }
                    string ans = dfs(i + 1, true, um_cpy, b);
                    if(!ans.empty()) {
                        oss << k << ans;
                        break;
                    }
                }
            }
        }
 
        return oss.str();
    }
 
    int acwing819::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        cout << factorial(n);
        return 0;
    }
 
    int acwing819::factorial(int n) {
        if(n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
 
    int acwing816::main(istream &cin, ostream &cout) {
        int n;
        int size;
        cin >> n >> size;
        auto *a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        reverse(a, size);
        for(int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        delete[] a;
        return 0;
    }
 
    void acwing816::reverse(int a[], int size) {
        for(int i = 0; i < size - 1 - i; i++) {
            const int tmp   = a[i];
            a[i]            = a[size - 1 - i];
            a[size - 1 - i] = tmp;
        }
    }
 
    int acwing820::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        cout << fibb(n);
        return 0;
    }
 
    int acwing820::fibb(int n) {
        if(n <= 2) {
            return 1;
        }
        return fibb(n - 1) + fibb(n - 2);
    }
 
    int acwing817::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << get_unique_count(a, n);
        delete[] a;
        return 0;
    }
 
    int acwing817::get_unique_count(int *a, int n) {
        unordered_set<int> um;
        for(int i = 0; i < n; i++) {
            um.insert(a[i]);
        }
        return um.size();
    }
 
    int acwing818::main(istream &cin, ostream &cout) {
        int n;
        int l;
        int r;
        cin >> n >> l >> r;
        auto *a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a, l, r);
        for(int i = 0; i < n; i++) {
            cout << a[i] << " ";
        }
        delete[] a;
        return 0;
    }
 
    void acwing818::sort(int *a, int l, int r) {
        if(l == r) {
            return;
        }
        if(l + 1 == r) {
            if(a[l] < a[r]) {
                return;
            }
            const int tmp = a[l];
            a[l]          = a[r];
            a[r]          = tmp;
        }
        const int m = a[(l + r) / 2];
        deque<int> dq;
        int cursor = l;
        dq.push_back(m);
        for(int i = l; i <= r; i++) {
            if(i != (l + r) / 2) {
                if(a[i] <= m) {
                    dq.push_front(a[i]);
                    cursor++;
                } else {
                    dq.push_back(a[i]);
                }
            }
        }
        for(int i = l; i <= r; i++) {
            a[i] = dq[i - l];
        }
        if(l <= cursor - 1) {
            sort(a, l, cursor - 1);
        }
        if(r >= cursor + 1) {
            sort(a, cursor + 1, r);
        }
    }
 
    int acwing821::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *dp = new int[n + 1];
        memset(dp, 0, (n + 1) * sizeof(int));
        dp[1] = 1;
        dp[2] = 1;
        for(int i = 1; i <= n; i++) {
            if(i + 1 <= n) {
                dp[i + 1] += dp[i];
            }
            if(i + 2 <= n) {
                dp[i + 2] += dp[i];
            }
        }
        cout << dp[n];
        delete[] dp;
        return 0;
    }
 
    int acwing822::main(istream &cin, ostream &cout) {
        int n;
        int m;
        cin >> n >> m;
        const int sum   = n + m;
        auto *factorial = new unsigned long long[sum + 1];
        factorial[1]    = 1;
        for(int i = 2; i <= sum; i++) {
            factorial[i] = i * factorial[i - 1];
        }
        cout << factorial[sum] / (factorial[n] * factorial[m]);
        delete[] factorial;
        return 0;
    }
 
    int acwing823::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        set<int> s;
        for(int i = 1; i <= n; i++) {
            s.insert(i);
        }
        vector<int> vec;
        dfs(vec, s, cout);
        return 0;
    }
 
    void acwing823::dfs(vector<int> &vec, set<int> &s, ostream &cout) {
        if(s.empty()) {
            for(const int i: vec) {
                cout << i << " ";
            }
            cout << endl;
        } else {
            for(auto i: s) {
                vector vec_cpy = vec;
                set<int> s_cpy = s;
                vec_cpy.push_back(i);
                s_cpy.erase(i);
                dfs(vec_cpy, s_cpy, cout);
            }
        }
    }
 
    int acwing21::Solution::Fibonacci(int n) {
        auto *fibb = new int[n];
        fibb[0]    = 1;
        fibb[1]    = 1;
        for(int i = 2; i < n; i++) {
            fibb[i] = fibb[i - 1] + fibb[i - 2];
        }
        const int ans = fibb[n - 1];
        delete[] fibb;
        return ans;
    }
 
    namespace acwing78 {
        string Solution::leftRotateString(string str, int n) {
            ostringstream oss;
            for(int i = 0; i < str.length(); i++) {
                oss << str[(n + i) % str.length()];
            }
            return oss.str();
        }
    }// namespace acwing78
 
    namespace acwing16 {
        string Solution::replaceSpaces(string &str) {
            ostringstream oss;
            for(const char ch: str) {
                if(ch != ' ') {
                    oss << ch;
                } else {
                    oss << "%20";
                }
            }
            return oss.str();
        }
    }// namespace acwing16
 
    namespace acwing87 {
        int Solution::strToInt(string str) {
            for(int i = 0; i < str.length(); i++) {
                if(str[i] != ' ') {
                    str = str.substr(i);
                    break;
                }
            }
            bool pos = true;
            if(str[0] == '+' || str[0] == '-') {
                pos = str[0] == '+';
                str = str.substr(1);
            }
            unsigned long long ans = 0;
            for(const char ch: str) {
                if(isdigit(ch) != 0) {
                    ans *= 10;
                    ans += ch - '0';
                } else {
                    break;
                }
            }
            return ans > INT_MAX
                           ? (pos ? INT_MAX : INT_MIN)
                   : pos
                           ? ans
                           : -ans;
        }
    }// namespace acwing87
 
    int acwing4308::main(istream &cin, ostream &cout) {
        string s1;
        string s2;
        cin >> s1 >> s2;
        bool flag = true;
        cout << s1[0];
        for(int i = 1; i < s1.length(); i++) {
            const char ch = s1[i];
            if(ch < s2[0]) {
                cout << ch;
            } else {
                break;
            }
        }
        cout << s2[0];
        return 0;
    }
 
    int acwing4309::main(istream &cin, ostream &cout) {
        int n;
        int x0;
        int y0;
        cin >> n >> x0 >> y0;
        bool flag = false;
        unordered_set<double> slopes;
        for(int i = 0; i < n; i++) {
            int xi;
            int yi;
            cin >> xi >> yi;
            if(xi != x0) {
                double slope = static_cast<double>(y0 - yi) / (x0 - xi);
                slopes.insert(slope);
            } else {
                flag = true;
            }
        }
        cout << slopes.size() + (flag ? 1 : 0);
        return 0;
    }
 
    namespace acwing4310 {
        int acwing4310::main(istream &cin, ostream &cout) {
            int n;
            int q;
            cin >> n >> q;
            vector<int> vec;
            for(int i = 1; i <= n; i++) {
                um[i] = new TreeNode(i);
            }
            for(int i = 2; i <= n; i++) {
                int parent;
                cin >> parent;
                um[parent]->nexts[i] = um[i];
            }
            dfs(&vec, um[1]);
            for(int i = 0; i < vec.size(); i++) {
                position[vec[i]] = i;
            }
            for(int i = 0; i < q; i++) {
                int u;
                int k;
                cin >> u >> k;
                if(k > size_tree[u]) {
                    cout << -1;
                } else {
                    cout << vec[position[u] + k - 1];
                }
                cout << endl;
            }
            for(auto [i, v]: um) {
                delete v;
            }
            return 0;
        }
 
        int acwing4310::dfs(vector<int> *vec, TreeNode *node) {
            int sum = 1;
            vec->push_back(node->val);
            for(auto [i, next]: node->nexts) {
                if(next != nullptr) {
                    sum += dfs(vec, next);
                }
            }
            size_tree[node->val] = sum;
            return sum;
        }
    }// namespace acwing4310
 
    namespace acwing84 {
        int Solution::getSum(int n) {
            int ans = (1 + n) * (n / 2);
            if(n % 2 != 0) {
                ans += n / 2;
            }
            return ans;
        }
    }// namespace acwing84
 
    namespace acwing35 {
        ListNode *Solution::reverseList(ListNode *head) {
            if(head == nullptr) {
                return head;
            }
            auto *prev    = head;
            auto *current = head->next;
            while(current != nullptr) {
                auto *next    = current->next;
                current->next = prev;
                prev          = current;
                current       = next;
            }
            head->next = nullptr;
            return prev;
        }
    }// namespace acwing35
 
    namespace acwing28 {
        void Solution::deleteNode(ListNode *node) {
            node->val        = node->next->val;
            const auto *next = node->next;
            delete next;
            node->next = node->next->next;
        }
    }// namespace acwing28
 
    namespace acwing66 {
        ListNode *Solution::findFirstCommonNode(ListNode *headA, ListNode *headB) {
            unordered_set<ListNode *> nodes;
            for(auto *current = headA; current != nullptr; current = current->next) {
                nodes.insert(current);
            }
            for(auto *current = headB; current != nullptr; current = current->next) {
                if(nodes.contains(current)) {
                    return current;
                }
            }
            return nullptr;
        }
    }// namespace acwing66
 
    namespace acwing36 {
        ListNode *Solution::merge(ListNode *l1, ListNode *l2) {
            auto *current        = new ListNode(0);
            const ListNode *head = current;
            while(l1 != nullptr && l2 != nullptr) {
                if(l1->val < l2->val) {
                    current->next = l1;
                    l1            = l1->next;
                } else {
                    current->next = l2;
                    l2            = l2->next;
                }
                current = current->next;
            }
            if(l1 == nullptr) {
                current->next = l2;
            } else {
                current->next = l1;
            }
            return head->next;
        }
    }// namespace acwing36
 
    namespace acwing29 {
        ListNode *Solution::deleteDuplication(ListNode *head) {
            if(head == nullptr) {
                return head;
            }
            while(head != nullptr && head->next != nullptr && head->val == head->next->val) {
                const int val = head->val;
                while(head != nullptr && head->val == val) {
                    head = head->next;
                }
            }
            ListNode *ans = head;
            while(head != nullptr) {
                while(head->next != nullptr && head->next->next != nullptr && head->next->val == head->next->next->val) {
                    const int val    = head->next->val;
                    ListNode *cursor = head->next;
                    while(cursor != nullptr && cursor->val == val) {
                        cursor = cursor->next;
                    }
                    head->next = cursor;
                }
                head = head->next;
            }
            return ans;
        }
    }// namespace acwing29
 
    namespace acwing67 {
        int Solution::getNumberOfK(vector<int> &nums, int k) {
            int ans   = 0;
            bool flag = false;
            for(const auto num: nums) {
                if(num == k) {
                    ans++;
                    flag = true;
                } else if(flag) {
                    break;
                }
            }
            return ans;
        }
    }// namespace acwing67
 
    namespace acwing53 {
        vector<int> Solution::getLeastNumbers_Solution(vector<int> input, int k) {
            sort(input.begin(), input.end());
            return vector(input.begin(), input.begin() + k);
        }
    }// namespace acwing53

    namespace acwing68 {
        int Solution::getMissingNumber(vector<int> &nums) {
            if(nums.empty()) {
                return 0;
            }
            int i = 0;
            while(nums[i] == i) {
                i++;
            }
            return i;
        }
    }// namespace acwing68
 
    namespace acwing75 {
        vector<int> Solution::findNumbersWithSum(vector<int> &nums, int target) {
            vector<int> ans(2);
            set nms(nums.begin(), nums.end());
            for(auto num = nms.begin(); *num <= target / 2 && num != nms.end(); ++num) {
                if(nms.contains(target - *num)) {
                    ans[0] = *num;
                    ans[1] = target - *num;
                    return ans;
                }
            }
            return ans;
        }
    }// namespace acwing75
 
    namespace acwing32 {
        void Solution::reOrderArray(vector<int> &array) {
            int l = 0;
            int r = array.size() - 1;
            while(l < r) {
                while(l < r && array[l] % 2 == 1) {
                    l++;
                }
                while(l < r && array[r] % 2 == 0) {
                    r--;
                }
                if(l < r) {
                    swap(array[l], array[r]);
                }
            }
        }
    }// namespace acwing32
 
    namespace acwing51 {
        vector<vector<int>> Solution::permutation(vector<int> &nums) {
            auto ans = vector<vector<int>>();
            set<vector<int>> s;
            dfs(vector<int>(), nums, s);
            for(const auto &vec: s) {
                ans.push_back(vec);
            }
            return ans;
        }
 
        void Solution::dfs(const vector<int> &vec, vector<int> nums, set<vector<int>> &s) {
            if(nums.empty()) {
                s.insert(vec);
            }
            for(int i = 0; i < nums.size(); i++) {
                auto nums_cpy = vector(nums);
                auto vec_cpy  = vector(vec);
                nums_cpy.erase(nums_cpy.begin() + i);
                vec_cpy.push_back(nums[i]);
                dfs(vec_cpy, nums_cpy, s);
            }
        }
    }// namespace acwing51
 
    namespace acwing17 {
        vector<int> Solution::printListReversingly(ListNode *head) {
            deque<int> deq;
            for(const auto *current = head; current != nullptr; current = current->next) {
                deq.push_front(current->val);
            }
            return vector(deq.begin(), deq.end());
        }
    }// namespace acwing17
 
    namespace acwing26 {
        int Solution::NumberOf1(int n) {
            int ans         = 0;
            unsigned int un = n;
            while(un != 0U) {
                ans += un & 1;
                un >>= 1;
            }
            return ans;
        }
    }// namespace acwing26
 
    namespace acwing20 {
        MyQueue::MyQueue() {
            main = vector<int>();
            tmp  = vector<int>();
        }
 
        void MyQueue::push(int x) { main.push_back(x); }
 
        int MyQueue::pop() {
            while(main.size() != 1) {
                tmp.push_back(main.back());
                main.pop_back();
            }
            const auto ret = main.back();
            main.pop_back();
            while(!tmp.empty()) {
                main.push_back(tmp.back());
                tmp.pop_back();
            }
            return ret;
        }
 
        int MyQueue::peek() {
            while(main.size() != 1) {
                tmp.push_back(main.back());
                main.pop_back();
            }
            const auto ret = main.back();
            while(!tmp.empty()) {
                main.push_back(tmp.back());
                tmp.pop_back();
            }
            return ret;
        }
 
        bool MyQueue::empty() const { return main.empty(); }
    }// namespace acwing20
 
    int acwing862::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto comp = [](tuple<int, float, string> a, tuple<int, float, string> b) {
            auto [ax, ay, az] = std::move(a);
            auto [bx, by, bz] = std::move(b);
            return ax < bx;
        };
        set<tuple<int, float, string>, decltype(comp)> s(comp);
        for(int i = 0; i < n; i++) {
            int x;
            float y;
            string z;
            cin >> x >> y >> z;
            s.insert(make_tuple(x, y, z));
        }
        for(const auto &t: s) {
            auto [x, y, z] = t;
            cout << x << ' ' << fixed << setprecision(2) << y << ' ' << z << endl;
        }
        return 0;
    }
 
    int acwing4311::main(istream &cin, ostream &cout) {
        int n;
        int m;
        cin >> n >> m;
        double maximum = 0;
        for(int i = 0; i < n; i++) {
            int a;
            int b;
            cin >> a >> b;
            maximum = max(maximum, m * a / static_cast<double>(b));
        }
        cout << fixed << setprecision(6) << maximum;
        return 0;
    }
 
    int acwing3412::main(istream &cin, ostream &cout) {
        int n;
        int m;
        int q;
        cin >> n >> m >> q;
        if(m > n) {
            for(int i = 0; i < q; i++) {
                cout << 0 << endl;
            }
            return 0;
        }
        string s;
        string t;
        cin >> s >> t;
        set<int> sub_end;
        set<int> sub_start;
        int sub_count = 0;
        for(int i = 0; i + m <= n; i++) {
            string str = s.substr(i, m);
            if(str == t) {
                sub_count++;
                sub_start.insert(i);
                sub_end.insert(i + m - 1);
            }
        }
        vector sub_end_count(n + 1, 0);
        vector sub_start_count(n + 1, 0);
        int current = 0;
        for(int i = 0; i < n + 1; i++) {
            if(sub_end.contains(i)) {
                current++;
            }
            sub_end_count[i] = current;
        }
        current = 0;
        for(int i = n; i >= 0; i--) {
            if(sub_start.contains(i)) {
                current++;
            }
            sub_start_count[i] = current;
        }
        for(int i = 0; i < q; i++) {
            int l;
            int r;
            cin >> l >> r;
            int ans = sub_end_count[r - 1] - (sub_count - sub_start_count[l - 1]);
            cout << max(ans, 0) << endl;
        }
        return 0;
    }
 
    int acwing3346::main(istream &cin, ostream &cout) {
        vector<int> nums(7);
        vector<int> abc(3);
        for(int i = 0; i < 7; i++) {
            cin >> nums[i];
        }
        sort(nums.begin(), nums.end());
        abc[0] = nums[0];
        abc[1] = nums[1];
        abc[2] = nums[6] - abc[0] - abc[1];
        sort(abc.begin(), abc.end());
        cout << abc[0] << ' ' << abc[1] << ' ' << abc[2];
        return 0;
    }
 
    namespace acwing3358 {
        int main(istream &cin, ostream &cout) {
            int char_pos[26] = {};
            char ch;
            for(int i = 0; i < 26; i++) {
                cin >> ch;
                char_pos[ch - 'a'] = i;
            }
            int ans     = 1;
            int current = -1;
            while(cin >> ch) {
                if(char_pos[ch - 'a'] <= current) {
                    ans++;
                }
                current = char_pos[ch - 'a'];
            }
            cout << ans;
            return 0;
        }
    };// namespace acwing3358
 
    namespace acwing3370 {
        int main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            unordered_map<string, int> zodiacs;
            unordered_map<string, cow *> cows;
            zodiacs["Ox"]      = 0;
            zodiacs["Tiger"]   = 1;
            zodiacs["Rabbit"]  = 2;
            zodiacs["Dragon"]  = 3;
            zodiacs["Snake"]   = 4;
            zodiacs["Horse"]   = 5;
            zodiacs["Goat"]    = 6;
            zodiacs["Monkey"]  = 7;
            zodiacs["Rooster"] = 8;
            zodiacs["Dog"]     = 9;
            zodiacs["Pig"]     = 10;
            zodiacs["Rat"]     = 11;
            cows["Bessie"]     = new cow("Bessie", 0, zodiacs["Ox"]);
            for(int i = 0; i < n; i++) {
                string str;
                string name1;
                string name2;
                cin >> name1 >> str >> str >> str;
                const bool previous = str == "previous";
                cin >> str;
                const int zodiac = zodiacs[str];
                cin >> str >> str >> name2;
                cow *cow1;
                cow *cow2;
                if(!cows.contains(name1)) {
                    cow1        = new cow(name1, -1, zodiac);
                    cows[name1] = cow1;
                } else {
                    cow1         = cows[name1];
                    cow1->zodiac = zodiac;
                }
                if(!cows.contains(name2)) {
                    cow2        = new cow(name2, -1, -1);
                    cows[name2] = cow2;
                } else {
                    cow2 = cows[name2];
                }
                if(previous) {
                    cow2->previous.push_back(cow1);
                    cow1->next.push_back(cow2);
                } else {
                    cow2->next.push_back(cow1);
                    cow1->previous.push_back(cow2);
                }
            }
            cout << abs(dfs(cows["Bessie"]));
            return 0;
        }
 
        int dfs(cow *c) {
            if(c->name == "Elsie") {
                return c->val;
            }
            for(auto *prev: c->previous) {
                if(prev->val == -1) {
                    if(c->zodiac == prev->zodiac) {
                        prev->val = c->val - 12;
                    } else {
                        prev->val = c->val - (c->zodiac + 12 - prev->zodiac) % 12;
                    }
                    const int ret = dfs(prev);
                    if(ret != -1) {
                        return ret;
                    }
                }
            }
            for(auto *nxt: c->next) {
                if(nxt->val == -1) {
                    if(c->zodiac == nxt->zodiac) {
                        nxt->val = c->val + 12;
                    } else {
                        nxt->val = c->val + (nxt->zodiac + 12 - c->zodiac) % 12;
                    }
                    const int ret = dfs(nxt);
                    if(ret != -1) {
                        return ret;
                    }
                }
            }
            return -1;
        }
 
        cow::cow(string name, int val, int zodiac) {
            this->name     = std::move(name);
            this->val      = val;
            this->zodiac   = zodiac;
            this->previous = vector<cow *>();
            this->next     = vector<cow *>();
        }
    }// namespace acwing3370
 
    namespace acwing3745 {
        int main(istream &cin, ostream &cout) {
            int n;
            int l;
            cin >> n >> l;
            vector<int> c(n);
            unordered_map<int, int> count;
            for(int i = 0; i < n; i++) {
                cin >> c[i];
                count[c[i]]++;
            }
            sort(c.rbegin(), c.rend());
            if(*c.begin() == 0) {
                if(l != 0) {
                    *c.begin() = 1;
                    l--;
                } else {
                    cout << 0;
                    return 0;
                }
            }
            int h = 0;
            while(h < n && c[h] >= h + 1) {
                h++;
            }
            if(l == 0) {
                cout << h;
                return 0;
            }
            int k = 0;
            for(int i = h - 1; i >= 0 && c[i] == h; i--) {
                k++;
            }
            if(l >= k + 1 && c[h] == h) {
                cout << h + 1;
            } else {
                cout << h;
            }
            return 0;
        }
    }// namespace acwing3745
 
    namespace acwing1459 {
        int main(istream &cin, ostream &cout) {
            int k;
            int n;
            cin >> k >> n;
            auto hash = [](const pair<int, int> p) -> int { return p.first * 20 + p.second; };
            unordered_set<pair<int, int>, decltype(hash)> pairs;
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(i != j) {
                        pairs.insert(make_pair(i, j));
                    }
                }
            }
            for(int i = 0; i < k; i++) {
                vector<int> vec(n);
                for(int j = 0; j < n; j++) {
                    cin >> vec[j];
                }
                for(int j = 0; j + 1 < n; j++) {
                    for(int l = j + 1; l < n; l++) {
                        pairs.erase(make_pair(vec[j], vec[l]));
                    }
                }
            }
            cout << pairs.size();
            return 0;
        }
    }// namespace acwing1459
 
    namespace acwing1442 {
        int main(istream &cin, ostream &cout) {
            int n;
            int k;
            cin >> n >> k;
            vector<string> vec(n);
            for(int i = 0; i < n; i++) {
                cin >> vec[i];
            }
            ostringstream oss;
            oss << vec[0];
            int current = vec[0].length();
            for(int i = 1; i < n; i++) {
                if(current + vec[i].length() > k) {
                    cout << oss.str() << endl;
                    oss = ostringstream();
                    oss << vec[i];
                    current = vec[i].length();
                } else {
                    oss << ' ';
                    oss << vec[i];
                    current += vec[i].length();
                }
            }
            cout << oss.str();
            return 0;
        }
    }// namespace acwing1442
 
    namespace acwing4314 {
        int main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            int ans = 0;
            for(int a = 1; a <= n; a++) {
                for(int b = a; b <= n; b++) {
                    const int c = a ^ b ^ 0;
                    if(n >= c && c >= b && c < a + b) {
                        ans++;
                    }
                }
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing4314
 
    namespace acwing4315 {
        int main(istream &cin, ostream &cout) {
            long long n;
            long long s;
            cin >> n >> s;
            vector<long long> a(n);
            long long a_sum = 0;
            for(int i = 0; i < n; i++) {
                cin >> a[i];
                a_sum += a[i];
            }
            for(int i = 0; i < n; i++) {
                const long long low  = max(static_cast<long long>(1), s - (a_sum - a[i]));
                const long long high = min(a[i], s - (n - 1));
                if(low <= high) {
                    cout << a[i] - (high - low + 1) << ' ';
                }
            }
            return 0;
        }
    }// namespace acwing4315
 
    namespace acwing1671 {
        int main(istream &cin, ostream &cout) {
            int ans = 0;
            unordered_map<int, set<int>> col;
            unordered_map<int, set<int>> row;
            set<pair<int, int>> us;
            int n;
            cin >> n;
            for(int i = 0; i < n; i++) {
                int x;
                int y;
                cin >> x >> y;
                us.insert(make_pair(x, y));
                row[x].insert(y);
                col[y].insert(x);
            }
            for(auto [x, y]: us) {
                const int max_width  = max(abs(*row[x].begin() - y), abs(*row[x].rbegin() - y));
                const int max_height = max(abs(*col[y].begin() - x), abs(*col[y].rbegin() - x));
                ans                  = max(ans, max_width * max_height);
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1671
 
    namespace acwing1659 {
        int main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            vector<bool> pen(n);
            string str;
            cin >> str;
            bool has1 = false;
            for(int i = 0; i < n; i++) {
                pen[i] = str[i] == '1';
                if(pen[i]) {
                    has1 = true;
                }
            }
            if(!has1) {
                cout << n - 1;
                return 0;
            }
            vector<int> spaces2;
            vector<int> spaces1;
            int current = 0;
            int left    = 0;
            int right   = n - 1;
            while(!pen[left]) {
                left++;
            }
            if(left > 0) {
                spaces1.push_back(left);
            }
            left++;
            while(!pen[right]) {
                right--;
            }
            if(right < n - 1) {
                spaces1.push_back(n - 1 - right);
            }
            for(; left <= right; left++) {
                if(!pen[left]) {
                    current++;
                } else {
                    spaces2.push_back(current);
                    current = 0;
                }
            }
            int minimum = 0;
            int limit   = n;
            sort(spaces2.begin(), spaces2.end());
            sort(spaces1.begin(), spaces1.end());
            if(!spaces2.empty()) {
                limit = *spaces2.begin();
                //两个都在2
                //两个都在2的最大
                const int a = (*spaces2.rbegin() - 2) / 3;
                minimum     = max(minimum, a);
                //两个分别在2的最大和第二大
                if(spaces2.size() > 1) {
                    const int b = (spaces2[spaces2.size() - 2] - 1) / 2;
                    minimum     = max(minimum, b);
                }
                //两个分别在2的最大和1的最大
                if(!spaces1.empty()) {
                    const int a = (*spaces2.rbegin() - 1) / 2;
                    int b       = *spaces1.rbegin() - 1;
                    minimum     = max(minimum, min(a, b));
                    //两个都在1的最大
                    b       = (*spaces1.rbegin() - 2) / 2;
                    minimum = max(minimum, b);
                    //两个分别在1的最大和第二大
                    if(spaces1.size() > 1) {
                        const int a = *spaces1.begin() - 1;
                        minimum     = max(minimum, a);
                    }
                }
            } else {
                //两个分别在1的最大和第二大
                if(spaces1.size() > 1) {
                    const int a = *spaces1.begin() - 1;
                    minimum     = max(minimum, a);
                }
                //两个都在1的最大
                const int b = (*spaces1.rbegin() - 2) / 2;
                minimum     = max(minimum, b);
            }
            minimum = min(limit, minimum);
            cout << minimum + 1;
            return 0;
        }
    }// namespace acwing1659
 
    namespace acwing1714 {
        int main(istream &cin, ostream &cout) {
            unsigned int c[3];
            unsigned int m[3];
            for(int i = 0; i < 3; i++) {
                cin >> c[i] >> m[i];
            }
            for(int i = 0; i < 100; i++) {
                const int a = i % 3;
                const int b = (i + 1) % 3;
                if(m[a] + m[b] <= c[b]) {
                    m[b] += m[a];
                    m[a] = 0;
                } else {
                    m[a] -= c[b] - m[b];
                    m[b] = c[b];
                }
            }
            for(int i = 0; i < 3; i++) {
                cout << m[i] << endl;
            }
            return 0;
        }
    }// namespace acwing1714
 
    namespace acwing1695 {
        int main(istream &cin, ostream &cout) {
            bool nuts[3][3]         = {{true, false, false},
                                       {false, true, false},
                                       {false, false, true}};
            unsigned short score[3] = {0, 0, 0};
            unsigned short ans      = 0;
            unsigned short n;
            cin >> n;
            unsigned short a;
            unsigned short b;
            unsigned short g;
            for(unsigned short i = 0; i < n; i++) {
                cin >> a >> b >> g;
                a--;
                b--;
                g--;
                for(unsigned short j = 0; j < 3; j++) {
                    swap(nuts[j][a], nuts[j][b]);
                    if(nuts[j][g]) {
                        score[j]++;
                    }
                }
            }
            for(unsigned short i = 0; i < 3; i++) {
                ans = max(ans, score[i]);
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1695
 
    namespace acwing1683 {
        int main(istream &cin, ostream &cout) {
            int pos[3];
            int ans1;
            cin >> pos[0] >> pos[1] >> pos[2];
            sort(pos, pos + 3);
            const int g1 = pos[1] - pos[0];
            const int g2 = pos[2] - pos[1];
            if(g1 == 2 || g2 == 2) {
                ans1 = 1;
            } else {
                ans1 = 2;
            }
            int ans2 = max(g1, g2);
            ans2--;
            cout << ans1 << endl
                 << ans2;
            return 0;
        }
    }// namespace acwing1683
 
    namespace acwing4318 {
        int main(istream &cin, ostream &cout) {
            int x = 0;
            int y = 0;
            char op;
            int step = 0;
            set<pair<int, int>> s;
            s.insert(make_pair(0, 0));
            while(cin >> op) {
                step++;
                switch(op) {
                    case 'U':
                        x--;
                        if(s.contains(make_pair(x, y)) ||
                           s.contains(make_pair(x - 1, y)) ||
                           s.contains(make_pair(x, y + 1)) ||
                           s.contains(make_pair(x, y - 1))) {
                            cout << "NO";
                            return 0;
                        }
                        break;
                    case 'D':
                        x++;
                        if(s.contains(make_pair(x, y)) ||
                           s.contains(make_pair(x + 1, y)) ||
                           s.contains(make_pair(x, y + 1)) ||
                           s.contains(make_pair(x, y - 1))) {
                            cout << "NO";
                            return 0;
                        }
                        break;
                    case 'L':
                        y--;
                        if(s.contains(make_pair(x, y)) ||
                           s.contains(make_pair(x, y - 1)) ||
                           s.contains(make_pair(x + 1, y)) ||
                           s.contains(make_pair(x - 1, y))) {
                            cout << "NO";
                            return 0;
                        }
                        break;
                    case 'R':
                        y++;
                        if(s.contains(make_pair(x, y)) ||
                           s.contains(make_pair(x, y + 1)) ||
                           s.contains(make_pair(x + 1, y)) ||
                           s.contains(make_pair(x - 1, y))) {
                            cout << "NO";
                            return 0;
                        }
                        break;
                    default:
                        step--;
                        break;
                }
                s.insert(make_pair(x, y));
            }
            if(step == 1) {
                cout << "YES";
                return 0;
            }
            if(abs(x) <= 1 && y == 0 || x == 0 && abs(y) <= 1) {
                cout << "NO";
            } else {
                cout << "YES";
            }
            return 0;
        }
    }// namespace acwing4318
 
    namespace acwing4319 {
        int main(istream &cin, ostream &cout) {
            unsigned int n;
            unsigned int k;
            cin >> n >> k;
            vector<unsigned int> a(n);
            vector<vector<pair<unsigned int, unsigned int>>> factors(n);
            map<vector<pair<unsigned int, unsigned int>>, unsigned int> factor_status_count;
            for(int i = 0; i < n; i++) {
                cin >> a[i];
                for(unsigned int factor = 2; factor * factor <= a[i]; factor++) {
                    if(a[i] % factor != 0U) {
                        continue;
                    }
                    unsigned int count = 0;
                    while(a[i] % factor == 0) {
                        a[i] /= factor;
                        ++count;
                    }
                    count %= k;
                    if(count != 0) {
                        factors[i].emplace_back(factor, count);
                    }
                }
                if(a[i] != 1) {
                    factors[i].emplace_back(a[i], 1);
                }
            }
            unsigned long long ans = 0;
            for(unsigned int i = 0; i < n; i++) {
                vector<pair<unsigned int, unsigned int>> factor_status;
                for(auto [factor, count]: factors[i]) {
                    factor_status.emplace_back(factor, k - count);
                }
                ans += factor_status_count[factor_status];
                ++factor_status_count[factors[i]];
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing4319
 
    namespace acwing1470 {
        int main(istream &cin, ostream &cout) {
            char farm[10][10] = {};
            pair<int, int> b;
            pair<int, int> l;
            for(int i = 0; i < 10; i++) {
                for(int j = 0; j < 10; j++) {
                    cin >> farm[i][j];
                    if(farm[i][j] == 'B') {
                        b = make_pair(i, j);
                    } else if(farm[i][j] == 'L') {
                        l = make_pair(i, j);
                    }
                }
            }
            priority_queue<status> pq;
            pq.push(status(0, l, b));
            while(!pq.empty()) {
                status s = pq.top();
                pq.pop();
                if(s.current == b) {
                    cout << s.len - 1;
                    return 0;
                }
                pair<int, int> nexts[4] = {make_pair(s.current.first + 1, s.current.second),
                                           make_pair(s.current.first - 1, s.current.second),
                                           make_pair(s.current.first, s.current.second + 1),
                                           make_pair(s.current.first, s.current.second - 1)};
                for(const auto next: nexts) {
                    if(0 <= next.first && next.first < 10 && 0 <= next.second && next.second < 10 && farm[next.first][next.second] != 'R') {
                        pq.push(status(s.len + 1, next, b));
                    }
                }
            }
            return 0;
        }
 
        bool status::operator<(const status &s) const { return this->get_weight() > s.get_weight(); }
 
        int status::get_weight() const { return len + abs(current.first - target.first) + abs(current.second - target.second); }
    }// namespace acwing1470
 
    namespace acwing1761 {
        int main(istream &cin, ostream &cout) {
            int x1[3];
            int y1[3];
            int x2[3];
            int y2[3];
            for(int i = 0; i < 3; i++) {
                cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
            }
            unsigned int area = 0;
            for(int i = 0; i < 2; i++) {
                area += abs(x2[i] - x1[i]) * abs(y2[i] - y1[i]);
                int x_1 = x1[2];
                int x_2 = x2[2];
                int y_1 = y1[2];
                int y_2 = y2[2];
                x_1     = max(x_1, x1[i]);
                x_2     = max(x_2, x1[i]);
                x_1     = min(x_1, x2[i]);
                x_2     = min(x_2, x2[i]);
                y_1     = max(y_1, y1[i]);
                y_2     = max(y_2, y1[i]);
                y_1     = min(y_1, y2[i]);
                y_2     = min(y_2, y2[i]);
                area -= abs(x_2 - x_1) * abs(y_2 - y_1);
            }
            cout << area;
            return 0;
        }
    }// namespace acwing1761
 
    namespace acwing1749 {
        int main(istream &cin, ostream &cout) {
            int x1[2];
            int x2[2];
            int y1[2];
            int y2[2];
            for(int i = 0; i < 2; i++) {
                cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
            }
            const unsigned int area = abs(x2[0] - x1[0]) * abs(y2[0] - y1[0]);
            int x_1                 = x1[1];
            int x_2                 = x2[1];
            int y_1                 = y1[1];
            int y_2                 = y2[1];
            x_1                     = max(x_1, x1[0]);
            x_2                     = max(x_2, x1[0]);
            x_1                     = min(x_1, x2[0]);
            x_2                     = min(x_2, x2[0]);
            y_1                     = max(y_1, y1[0]);
            y_2                     = max(y_2, y1[0]);
            y_1                     = min(y_1, y2[0]);
            y_2                     = min(y_2, y2[0]);
            if(x_2 == x_1 || y_2 == y_1) {
                //没有遮盖
                cout << area;
                return 0;
            }
            if(y_2 == y2[0] && y_1 == y1[0]) {
                //纵向填满
                cout << abs(abs(x2[0] - x1[0]) - abs(x_2 - x_1)) * abs(y_2 - y_1);
                return 0;
            }
            if(x_1 == x1[0] && x_2 == x2[0] && (y_1 == y1[0] || y_2 == y2[0])) {
                //横向填满
                cout << (x_2 - x_1) * max(y2[0] - y_2, y_1 - y1[0]);
                return 0;
            }
            cout << area;
            return 0;
        }
    }// namespace acwing1749
 
    namespace acwing1737 {
        int main(istream &cin, ostream &cout) {
            int a;
            int b;
            int x;
            int y;
            cin >> a >> b >> x >> y;
            const int d1 = abs(b - a);
            const int d2 = abs(a - x) + abs(b - y);
            const int d3 = abs(a - y) + abs(b - x);
            cout << min(d1, min(d2, d3));
            return 0;
        }
    }// namespace acwing1737
 
    namespace acwing1725 {
        int main(istream &cin, ostream &cout) {
            unordered_set<char> row[3];
            unordered_set<char> col[3];
            unordered_set<char> main_diagonal;
            unordered_set<char> leading_diagonal;
            unordered_set<char> win_1;
            auto hash = [](const pair<char, char> &p) {
                vector vec = {p.first, p.second};
                sort(vec.begin(), vec.end());
                unsigned int val = 0;
                for(auto &ch: vec) {
                    ch -= 'A';
                    val *= 26;
                    val += ch;
                }
                return val;
            };
            unordered_set<pair<char, char>, decltype(hash)> win_2;
            char board[3][3];
            for(int i = 0; i < 3; i++) {
                for(int j = 0; j < 3; j++) {
                    cin >> board[i][j];
                    row[i].insert(board[i][j]);
                    col[j].insert(board[i][j]);
                }
            }
            main_diagonal.insert(board[0][0]);
            main_diagonal.insert(board[1][1]);
            main_diagonal.insert(board[2][2]);
            leading_diagonal.insert(board[0][2]);
            leading_diagonal.insert(board[1][1]);
            leading_diagonal.insert(board[2][0]);
            for(int i = 0; i < 3; i++) {
                if(row[i].size() == 1) {
                    win_1.insert(board[i][0]);
                } else if(row[i].size() == 2) {
                    win_2.insert(make_pair(*row[i].begin(), *++row[i].begin()));
                }
                if(col[i].size() == 1) {
                    win_1.insert(board[0][i]);
                } else if(col[i].size() == 2) {
                    win_2.insert(make_pair(*col[i].begin(), *++col[i].begin()));
                }
            }
            if(main_diagonal.size() == 1) {
                win_1.insert(board[1][1]);
            } else if(main_diagonal.size() == 2) {
                win_2.insert(make_pair(*main_diagonal.begin(), *++main_diagonal.begin()));
            }
            if(leading_diagonal.size() == 1) {
                win_1.insert(board[1][1]);
            } else if(leading_diagonal.size() == 2) {
                win_2.insert(make_pair(*leading_diagonal.begin(), *++leading_diagonal.begin()));
            }
            cout << win_1.size() << endl
                 << win_2.size();
            return 0;
        }
    }// namespace acwing1725
 
    namespace acwing4394 {
        int main(istream &cin, ostream &cout) {
            unsigned n;
            unsigned k;
            cin >> n >> k;
            vector<unsigned> vec(n);
            for(unsigned i = 0; i < n; i++) {
                cin >> vec[i];
            }
            unsigned l     = 0;
            unsigned r     = 0;
            unsigned max_l = l;
            unsigned max_r = r;
            vector<unsigned> um(1000001, 0);
            unsigned size = 1;
            um[vec[0]]++;
            while(r < n) {
                while(size <= k) {
                    r++;
                    if(r < n) {
                        if(um[vec[r]] == 0) {
                            size++;
                        }
                        if(size > k) {
                            r--;
                            size--;
                            break;
                        }
                        um[vec[r]]++;
                    } else {
                        cout << max_l + 1 << ' ' << max_r + 1;
                        return 0;
                    }
                    max_r = r;
                }
 
                um[vec[l]]--;
                if(um[vec[l]] == 0) {
                    size--;
                }
                l++;
                r++;
                if(r < n) {
                    if(um[vec[r]] == 0) {
                        size++;
                    }
                    um[vec[r]]++;
                    if(size <= k) {
                        max_l = l;
                        max_r = r;
                    }
                } else {
                    cout << max_l + 1 << ' ' << max_r + 1;
                    return 0;
                }
            }
            cout << max_l + 1 << ' ' << max_r + 1;
            return 0;
        }
    }// namespace acwing4394
 
    namespace acwing1812 {
        int main(istream &cin, ostream &cout) {
            int x[2][2];
            int y[2][2];
            for(int i = 0; i < 2; i++) {
                cin >> x[i][0] >> y[i][0] >> x[i][1] >> y[i][1];
            }
            const int x1   = min(x[0][0], x[1][0]);
            const int x2   = max(x[0][1], x[1][1]);
            const int y1   = min(y[0][0], y[1][0]);
            const int y2   = max(y[0][1], y[1][1]);
            const int edge = max(y2 - y1, x2 - x1);
            cout << edge * edge;
            return 0;
        }
    }// namespace acwing1812
 
    namespace acwing1800 {
        int main(istream &cin, ostream &cout) {
            unordered_map<string, unsigned> um;
            um["Bessie"]    = 0;
            um["Elsie"]     = 0;
            um["Daisy"]     = 0;
            um["Gertie"]    = 0;
            um["Annabelle"] = 0;
            um["Maggie"]    = 0;
            um["Henrietta"] = 0;
            unsigned short n;
            cin >> n;
            string name;
            unsigned amount;
            unsigned minimum = 0;
            while(n-- != 0U) {
                cin >> name >> amount;
                um[name] += amount;
                minimum = max(minimum, um[name]);
            }
            unsigned second_minimum = minimum;
            for(auto &[name, amount]: um) {
                minimum = min(minimum, amount);
            }
            for(auto &[name, amount]: um) {
                if(amount != minimum && amount < second_minimum) {
                    second_minimum = amount;
                }
            }
            string ans;
            for(auto &[name, amount]: um) {
                if(second_minimum == amount) {
                    if(ans.empty()) {
                        ans = name;
                    } else {
                        cout << "Tie";
                        return 0;
                    }
                }
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1800
 
    namespace acwing1788 {
        int main(istream &cin, ostream &cout) {
            int n;
            unordered_map<int, int> um;
            cin >> n;
            int ans = 0;
            while(n-- != 0) {
                int id;
                int side;
                cin >> id >> side;
                if(!um.contains(id)) {
                    um[id] = side;
                } else if(um[id] != side) {
                    ans++;
                    um[id] = side;
                }
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1788
 
    namespace acwing1775 {
        int main(istream &cin, ostream &cout) {
            int x;
            int y;
            cin >> x >> y;
            int step     = 1;
            unsigned ans = 0;
            int current  = x;
            while(current != y) {
                if((y - current) * (y - (x + step)) < 0) {
                    ans += abs(y - current);
                    cout << ans;
                    return 0;
                }
                ans += abs(x + step - current);
                current = x + step;
                step *= -2;
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1775
 
    namespace acwing785 {
        void qs(vector<int> &vec, int l, int r) {
            if(l >= r) {
                return;
            }
            const int x = vec[l + r >> 1];
            int lp      = l - 1;
            int rp      = r + 1;
            while(lp < rp) {
                while(vec[++lp] < x) {}
                while(vec[--rp] > x) {}
                if(lp < rp) {
                    swap(vec[lp], vec[rp]);
                }
            }
            qs(vec, l, rp);
            qs(vec, rp + 1, r);
        }
 
        int main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            vector<int> vec(n);
            for(int i = 0; i < n; i++) {
                cin >> vec[i];
            }
            qs(vec, 0, n - 1);
            for(int i = 0; i < n; i++) {
                cout << vec[i] << ' ';
            }
            return 0;
        }
    }// namespace acwing785

    namespace acwing788 {
        void ms(vector<int> &arr, int l, int r, int *ans) {
            if(l >= r) {
                return;
            }
            const int m = l + r >> 1;
            ms(arr, l, m, ans);
            ms(arr, m + 1, r, ans);
            int i = l;
            int j = m + 1;
            int p = 0;
            vector<int> tmp(r - l + 1);
            while(i <= m && j <= r) {
                if(arr[i] <= arr[j]) {
                    tmp[p++] = arr[i++];
                } else {
                    tmp[p++] = arr[j++];
                    *ans += m - i + 1;
                }
            }
            while(i <= m) {
                tmp[p++] = arr[i++];
            }
            while(j <= r) {
                tmp[p++] = arr[j++];
            }
            for(int i = 0; i < p; i++) {
                arr[l + i] = tmp[i];
            }
        }
 
        int main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            vector<int> vec(n);
            for(int i = 0; i < n; i++) {
                cin >> vec[i];
            }
            int ans = 0;
            ms(vec, 0, n - 1, &ans);
            cout << ans;
            return 0;
        }
    }// namespace acwing788
 
    namespace acwing789 {
 
        long bfl(const vector<long> &vec, long target) {
            int l = 0;
            int r = vec.size() - 1;
            while(l < r) {
                const int m = (l + r + 1) / 2;
                if(vec[m] <= target) {
                    l = m;
                } else {
                    r = m - 1;
                }
            }
            if(vec[l] != target) {
                return -1;
            }
            return l;
        }
 
        long bfr(const vector<long> &vec, long target) {
            int l = 0;
            int r = vec.size() - 1;
            while(l < r) {
                const int m = (l + r) / 2;
                if(vec[m] < target) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            if(vec[l] != target) {
                return -1;
            }
            return l;
        }
 
        int main(istream &cin, ostream &cout) {
            long n;
            long q;
            cin >> n >> q;
            vector<long> vec(n);
            for(long i = 0; i < n; i++) {
                cin >> vec[i];
            }
            for(long i = 0; i < q; i++) {
                long k;
                cin >> k;
                cout << bfr(vec, k) << ' ' << bfl(vec, k) << endl;
            }
            return 0;
        }
    }// namespace acwing789
 
    namespace acwing1866 {
        int main(istream &cin, ostream &cout) {
            int a;
            int b;
            int c;
            int d;
            cin >> a >> b >> c >> d;
            const int ab    = b - a;
            const int cd    = d - c;
            const int dup_d = min(b, max(a, d));
            const int dup_c = min(b, max(a, c));
            const int sum   = ab + cd - (dup_d - dup_c);
            cout << sum;
            return 0;
        }
    }// namespace acwing1866
 
    namespace acwing1854 {
        int main(istream &cin, ostream &cout) {
            int b[4][2];
            for(int i = 0; i < 4; i++) {
                for(int j = 0; j < 2; j++) {
                    cin >> b[i][j];
                }
            }
            int ans[3];
            ans[2] = b[3][1] - b[3][0];
            b[2][0] -= ans[2];
            ans[1] = b[2][1] - b[2][0];
            b[1][0] -= ans[1];
            ans[0] = b[1][1] - b[1][0];
            for(int i = 0; i < 3; i++) {
                cout << ans[i] << endl;
            }
            return 0;
        }
    }// namespace acwing1854
 
    namespace acwing4397 {
        bool cmp(const pair<int, int> &a, const pair<int, int> &b) { return a.first > b.first; }
 
        int main(istream &cin, ostream &cout) {
            int n;
            int k;
            cin >> n >> k;
            vector<int> a(n);
            vector<int> b(n);
            vector<pair<int, int>> a_b(n);
            for(int i = 0; i < n; i++) {
                cin >> a[i];
            }
            for(int i = 0; i < n; i++) {
                cin >> b[i];
                a_b[i] = make_pair(a[i] - b[i], i);
            }
            sort(a_b.begin(), a_b.end(), cmp);
            for(int i = 0; i < k; i++) {
                if(a_b[i].first > 0) {
                    a[a_b[i].second] = b[a_b[i].second];
                } else {
                    break;
                }
            }
            long long ans = 0;
            for(int i = 0; i < n; i++) {
                ans += a[i];
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing4397
 
    namespace acwing4398 {
        void TrieNode::insert(const string &str, int start, string *origin) {
            if(!this->nexts.contains(str[start])) {
                this->nexts[str[start]] = new TrieNode(str[start]);
            }
            if(origin != nullptr) {
                this->nexts[str[start]]->origin.insert(origin);
            }
            if(str.length() - start != 1) {
                this->nexts[str[start]]->insert(str, start + 1, origin);
            }
        }
 
        TrieNode *TrieNode::search(const string &str, int start) {
            this->ch = this->ch;
            if(this->nexts.contains(str[start])) {
                if(start + 1 == str.length()) {
                    return this->nexts[str[start]];
                }
                return this->nexts[str[start]]->search(str, start + 1);
            }
            return nullptr;
        }
 
        TrieNode::~TrieNode() {
            for(const auto [k, v]: this->nexts) {
                delete v;
            }
        }
 
        int main(istream &cin, ostream &cout) {
            int n;
            int q;
            cin >> n;
            TrieNode tn(0);
            vector<string> f(n);
            for(int i = 0; i < n; i++) {
                cin >> f[i];
                for(int j = 0; j < f[i].length(); ++j) {
                    tn.insert(f[i], j, &f[i]);
                }
            }
            cin >> q;
            for(int i = 0; i < q; i++) {
                string s;
                cin >> s;
                const TrieNode *node = tn.search(s, 0);
                if(node == nullptr) {
                    cout << "0 -" << endl;
                } else {
                    cout << node->origin.size() << ' ' << **node->origin.begin() << endl;
                }
            }
            return 0;
        }
    }// namespace acwing4398
 
    namespace acwing1842 {
        int main(istream &cin, ostream &cout) {
            int x;
            int y;
            int m;
            cin >> x >> y >> m;
            int ans = 0;
            for(int i = 0; y * i <= m; ++i) {
                int amount = y * i;
                amount += (m - amount) / x * x;
                ans = max(ans, amount);
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1842
 
    namespace acwing1824 {
        int main(istream &cin, ostream &cout) {
            int n;
            int k;
            cin >> n >> k;
            vector vec(10010, 0);
            unsigned int size;
            for(int i = 0; i < n; i++) {
                cin >> size;
                vec[size]++;
            }
            vector sum(10010, 0);
            for(int i = 1; i < 10010; i++) {
                sum[i] = sum[i - 1] + vec[i];
            }
            int ans = 0;
            for(int i = 1; i + k < 10010; i++) {
                ans = max(ans, sum[i + k] - sum[i - 1]);
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1824
 
    namespace acwing800 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            int x;
            cin >> n >> m >> x;
            vector<int> a(n);
            vector<int> b(m);
            for(int i = 0; i < n; i++) {
                cin >> a[i];
            }
            for(int i = 0; i < m; i++) {
                cin >> b[i];
            }
            int pa = 0;
            int pb = m - 1;
            while(a[pa] + b[pb] < x) {
                ++pa;
            }
            for(; pa < n; pa++) {
                if(a[pa] + b[pb] == x) {
                    cout << pa << ' ' << pb;
                    return 0;
                }
                while(a[pa] + b[pb] > x) {
                    --pb;
                    if(a[pa] + b[pb] == x) {
                        cout << pa << ' ' << pb;
                        return 0;
                    }
                }
            }
            return 0;
        }
    }// namespace acwing800
 
    namespace acwing2816 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            cin >> n >> m;
            vector<int> a(n);
            vector<int> b(m);
            for(int i = 0; i < n; i++) {
                cin >> a[i];
            }
            for(int i = 0; i < m; i++) {
                cin >> b[i];
            }
            int pa = 0;
            int pb = 0;
            for(; pa < n; ++pa) {
                while(pb < m && b[pb] != a[pa]) {
                    ++pb;
                }
                if(pb == m) {
                    cout << "No";
                    return 0;
                }
                ++pb;
            }
            cout << "Yes";
            return 0;
        }
    }// namespace acwing2816
 
    namespace acwing1902 {
        int main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            vector<pair<int, int>> checkpoints(n);
            vector<int> d(n - 1);
            for(int i = 0; i < n; i++) {
                int x;
                int y;
                cin >> x >> y;
                checkpoints[i] = make_pair(x, y);
            }
            int sum = 0;
            for(int i = 0; i < n - 1; i++) {
                const auto &[x1, y1] = checkpoints[i];
                const auto &[x2, y2] = checkpoints[i + 1];
                d[i]                 = abs(x2 - x1) + abs(y2 - y1);
                sum += d[i];
            }
            int max_diff = 0;
            for(int i = 1; i < n - 1; i++) {
                const auto &[x1, y1] = checkpoints[i - 1];
                const auto &[x2, y2] = checkpoints[i + 1];
                const int dist       = abs(x2 - x1) + abs(y2 - y1);
                int diff             = d[i - 1] + d[i] - dist;
                max_diff             = max(max_diff, diff);
            }
            cout << sum - max_diff;
            return 0;
        }
    }// namespace acwing1902
 
    namespace acwing3302 {
        int main(istream &cin, ostream &cout) {
            stack<int> nums;
            stack<char> ops;
            char ch;
            int num;
            while((ch = cin.peek()) > 0) {
                if(isdigit(ch) != 0) {
                    cin >> num;
                    if(!ops.empty() && ops.top() == '*') {
                        num = nums.top() * num;
                        nums.pop();
                        nums.push(num);
                        ops.pop();
                    } else if(!ops.empty() && ops.top() == '/') {
                        num = nums.top() / num;
                        nums.pop();
                        nums.push(num);
                        ops.pop();
                    } else {
                        nums.push(num);
                    }
                } else {
                    cin >> ch;
                    if(ch == ')') {
                        vector<char> vec_op;
                        vector<int> vec_num;
                        vec_num.push_back(nums.top());
                        nums.pop();
                        while(ops.top() != '(') {
                            vec_op.push_back(ops.top());
                            vec_num.push_back(nums.top());
                            ops.pop();
                            nums.pop();
                        }
                        ops.pop();
                        for(int i = vec_op.size() - 1; i >= 0; --i) {
                            if(vec_op[i] == '+') {
                                vec_num.back() += vec_num[i];
                            } else if(vec_op[i] == '-') {
                                vec_num.back() -= vec_num[i];
                            } else {
                                return 1;
                            }
                        }
                        num = vec_num.back();
                        if(!ops.empty() && ops.top() == '*') {
                            num = nums.top() * num;
                            nums.pop();
                            nums.push(num);
                            ops.pop();
                        } else if(!ops.empty() && ops.top() == '/') {
                            num = nums.top() / num;
                            nums.pop();
                            nums.push(num);
                            ops.pop();
                        } else {
                            nums.push(num);
                        }
                    } else {
                        ops.push(ch);
                    }
                }
            }
            vector<char> vec_op;
            vector<int> vec_num;
            vec_num.push_back(nums.top());
            nums.pop();
            while(!ops.empty()) {
                vec_op.push_back(ops.top());
                vec_num.push_back(nums.top());
                ops.pop();
                nums.pop();
            }
            for(int i = vec_op.size() - 1; i >= 0; --i) {
                if(vec_op[i] == '+') {
                    vec_num.back() += vec_num[i];
                } else if(vec_op[i] == '-') {
                    vec_num.back() -= vec_num[i];
                } else {
                    return 1;
                }
            }
            cout << vec_num.back();
            return 0;
        }
    }// namespace acwing3302
 
    namespace acwing831 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            string p;
            string s;
            cin >> n >> p >> m >> s;
            const vector<int> next = get_next(p);
            int ip                 = 0;
            int is                 = 0;
            while(ip < n && is < m) {
                if(p[ip] == s[is]) {
                    if(ip == n - 1) {
                        //整串匹配成功
                        cout << is - n + 1 << ' ';
                        ip = next[ip - 1];
                    } else {
                        //当前匹配成功
                        ip++;
                        is++;
                    }
                } else {
                    if(ip == 0) {
                        //开头就匹配失败
                        is++;
                    } else {
                        //匹配失败，但不在开头
                        ip = next[ip - 1];
                    }
                }
            }
            return 0;
        }
 
        vector<int> get_next(const string &str) {
            const int n = str.length();
            vector next(n, 0);
            int i = 1;
            int j = 0;
            while(i < n && j < n) {
                if(str[i] == str[j]) {
                    //匹配成功
                    next[i] = j + 1;
                    j++;
                    i++;
                } else {
                    if(j == 0) {
                        //开头就匹配失败
                        i++;
                    } else {
                        //匹配失败，但不在开头
                        j = next[j - 1];
                    }
                }
            }
            return next;
        }
    }// namespace acwing831
 
    namespace acwing1892 {
        int main(istream &cin, ostream &cout) {
            int a;
            int b;
            int n;
            cin >> a >> b >> n;
            int ans = 1001;
            for(int i = 0; i < n; i++) {
                int price;
                int num;
                bool flag = false;
                cin >> price >> num;
                int city;
                for(int j = 0; j < num; j++) {
                    cin >> city;
                    if(city == a) {
                        flag = true;
                    } else if(flag && city == b) {
                        ans = min(ans, price);
                    }
                }
            }
            if(ans == 1001) {
                cout << -1;
            } else {
                cout << ans;
            }
            return 0;
        }
    }// namespace acwing1892
 
    namespace acwing1883 {
        int main(istream &cin, ostream &cout) {
            string s;
            string t;
            string res;
            cin >> s >> t;
            const int slen = s.length();
            const int tlen = t.length();
            //一边添加一边判断
            for(int i = 0; i < slen; i++) {
                res += s[i];
                //当添加到长度大于等于t字符串时，开始比较
                //每次从末尾向前匹配
                while(res.length() >= tlen && res.substr(res.length() - tlen, tlen) == t) {
                    //存在t字符串，则删除
                    res.erase(res.begin() + res.length() - tlen, res.end());
                }
            }
            cout << res;
            return 0;
        }
    }// namespace acwing1883
 
    namespace acwing1995 {
        int main(istream &cin, ostream &cout) {
            int b;
            int e;
            cin >> b >> e;
            vector<int> pos_b;
            vector<int> pos_e;
            pos_b.push_back(0);
            pos_e.push_back(0);
            while(b-- != 0) {
                char dir;
                int dist;
                cin >> dist >> dir;
                if(dir == 'L') {
                    for(int i = 0; i < dist; i++) {
                        pos_b.push_back(pos_b.back() - 1);
                    }
                } else {
                    for(int i = 0; i < dist; i++) {
                        pos_b.push_back(pos_b.back() + 1);
                    }
                }
            }
            while(e-- != 0) {
                char dir;
                int dist;
                cin >> dist >> dir;
                if(dir == 'L') {
                    for(int i = 0; i < dist; i++) {
                        pos_e.push_back(pos_e.back() - 1);
                    }
                } else {
                    for(int i = 0; i < dist; i++) {
                        pos_e.push_back(pos_e.back() + 1);
                    }
                }
            }
            const int t = max(pos_e.size(), pos_b.size());
            int ans     = 0;
            bool flag   = true;
            for(int i = 0; i < t; i++) {
                const int pe = i < pos_e.size() ? pos_e[i] : pos_e.back();
                const int pb = i < pos_b.size() ? pos_b[i] : pos_b.back();
                if(pe == pb) {
                    if(!flag) {
                        ans++;
                    }
                    flag = true;
                } else {
                    flag = false;
                }
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing1995
 
    namespace acwing143 {
        int main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            vector<string> vec(n);
            TrieNode tn;
            for(int j = 0; j < n; j++) {
                unsigned a;
                cin >> a;
                ostringstream oss;
                for(int i = 30; i >= 0; i--) {
                    oss << ((a & 1 << i) != 0U ? '1' : '0');
                }
                string str = oss.str();
                vec[j]     = str;
                tn.insert(str, 0);
            }
            unsigned maximum = 0;
            for(const auto &str: vec) {
                const TrieNode *current = &tn;
                unsigned ans            = 0;
                for(int i = 0; i <= 30; i++) {
                    ans <<= 1;
                    if(current->next[str[i] - '0' == 0] != nullptr) {
                        current = current->next[str[i] - '0' == 0];
                        ans += 1;
                    } else {
                        current = current->next[str[i] - '0'];
                    }
                }
                maximum = max(maximum, ans);
            }
            cout << maximum;
            return 0;
        }
 
        void TrieNode::insert(const string &str, int i) {
            if(this->next[str[i] - '0'] == nullptr) {
                this->next[str[i] - '0']      = new TrieNode();
                this->next[str[i] - '0']->val = str[i] - '0';
            }
            if(i + 1 < str.length()) {
                this->next[str[i] - '0']->insert(str, i + 1);
            }
        }
    }// namespace acwing143
 
    namespace acwing837 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            cin >> n >> m;
            UnionFind uf(n);
            while(m-- != 0) {
                string op;
                int a;
                int b;
                cin >> op;
                if(op == "C") {
                    cin >> a >> b;
                    uf.unite(a - 1, b - 1);
                } else if(op == "Q1") {
                    cin >> a >> b;
                    cout << (uf.same(a - 1, b - 1) ? "Yes" : "No") << endl;
                } else {
                    cin >> a;
                    cout << uf.get_size(a - 1) << endl;
                }
            }
            return 0;
        }
    }// namespace acwing837
 
    namespace acwing240 {
        int main(istream &cin, ostream &cout) {
            int n;
            int k;
            cin >> n >> k;
            UnionFind uf(n);
            int ans = 0;
            while(k-- != 0) {
                char d;
                int x;
                int y;
                cin >> d >> x >> y;
                if(x > n || y > n) {
                    ans++;
                    continue;
                }
                x--;
                y--;
                const int px = uf.find(x);
                const int py = uf.find(y);
                if(d == '1') {
                    if(px == py) {
                        if((uf.dist[x] - uf.dist[y]) % 3 != 0) {
                            ans++;
                        }
                    } else {
                        uf.parent[px] = py;
                        uf.dist[px]   = uf.dist[y] - uf.dist[x];
                    }
                } else {
                    if(x == y) {
                        ans++;
                        continue;
                    }
                    if(px == py) {
                        if((uf.dist[x] - uf.dist[y] - 1) % 3 != 0) {
                            ans++;
                        }
                    } else {
                        uf.parent[px] = py;
                        uf.dist[px]   = uf.dist[y] - uf.dist[x] + 1;
                    }
                }
            }
            cout << ans;
            return 0;
        }
 
        UnionFind::UnionFind(int n) {
            parent = vector<int>(n);
            dist   = vector(n, 0);
            for(int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
 
        int UnionFind::find(int x) {
            if(parent[x] != x) {
                const int tmp = find(parent[x]);
                dist[x] += dist[parent[x]];
                parent[x] = tmp;
            }
            return parent[x];
        }
    }// namespace acwing240
 
    namespace acwing845 {
        int main(istream &cin, ostream &cout) {
            array<array<char, 3>, 3> target{};
            array<array<char, 3>, 3> grid{};
            unordered_set<array<array<char, 3>, 3>, hash> us;
            int start_x;
            int start_y;
            for(int i = 0; i < 9; i++) {
                cin >> grid[i / 3][i % 3];
                if(grid[i / 3][i % 3] == 'x') {
                    start_x = i / 3;
                    start_y = i % 3;
                }
                target[i / 3][i % 3] = i + '1';
            }
            target[2][2] = 'x';
            queue<tuple<array<array<char, 3>, 3>, int, int, int>> q;
            q.push(make_tuple(grid, 0, start_x, start_y));
            us.insert(grid);
            while(!q.empty()) {
                auto [g, step, x, y] = q.front();
                q.pop();
                if(g == target) {
                    cout << step;
                    return 0;
                }
                pair<int, int> nexts[4] = {
                        make_pair(x, y + 1),
                        make_pair(x, y - 1),
                        make_pair(x + 1, y),
                        make_pair(x - 1, y)};
                for(auto &[nx, ny]: nexts) {
                    if(nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                        swap(g[nx][ny], g[x][y]);
                        if(!us.contains(g)) {
                            us.insert(g);
                            q.push(make_tuple(g, step + 1, nx, ny));
                        }
                        swap(g[nx][ny], g[x][y]);
                    }
                }
            }
            cout << -1;
            return 0;
        }
 
        unsigned int hash::operator()(const array<array<char, 3>, 3> &g) const {
            unsigned int ret = 0;
            for(int i = 0; i < 9; i++) {
                char v = g[i / 3][i % 3];
                if(v == 'x') {
                    v = '0';
                }
                ret *= 10;
                ret += v - '0';
            }
            return ret;
        }
    }// namespace acwing845
 
    namespace acwing849 {
        bool comp::operator()(const pair<int, int> &p1, const pair<int, int> &p2) const { return p1.second > p2.second; }
 
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            cin >> n >> m;
            vector<unordered_map<int, int>> vec(n + 1);
            unordered_set<int> ed;
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                if(vec[x][y] == 0) {
                    vec[x][y] = z;
                } else {
                    vec[x][y] = min(vec[x][y], z);
                }
            }
            priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
            pq.push(make_pair(1, 0));
            while(!pq.empty()) {
                auto [node, dist] = pq.top();
                pq.pop();
                if(ed.contains(node)) {
                    continue;
                }
                ed.insert(node);
                if(node == n) {
                    cout << dist;
                    return 0;
                }
                for(auto [next_node, d]: vec[node]) {
                    if(!ed.contains(next_node)) {
                        pq.push(make_pair(next_node, dist + d));
                    }
                }
            }
            cout << -1;
            return 0;
        }
    }// namespace acwing849
 
    namespace acwing853 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            int k;
            cin >> n >> m >> k;
            vector<tuple<int, int, int>> vec(m);
            vector shortest(n + 1, 0x3f3f3f);
            shortest[1] = 0;
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                vec[i] = make_tuple(x, y, z);
            }
            for(int i = 0; i < k; i++) {
                vector<int> shortest_cpy = shortest;
                for(auto [x, y, z]: vec) {
                    shortest[y] = min(shortest[y], shortest_cpy[x] + z);
                }
            }
            if(shortest[n] > 0x3f3f3f / 2) {
                cout << "impossible";
            } else {
                cout << shortest[n];
            }
            return 0;
        }
    }// namespace acwing853
 
    namespace acwing851 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            cin >> n >> m;
            vector<unordered_map<int, int>> g(n + 1);
            vector reachable(n + 1, false);
            vector shortest(n + 1, 0x3f3f3f);
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                if(g[x][y] == 0) {
                    g[x][y] = z;
                } else {
                    g[x][y] = min(g[x][y], z);
                }
            }
            queue<int> q;
            unordered_set<int> us;
            us.insert(1);
            q.push(1);
            shortest[1]  = 0;
            reachable[1] = true;
            while(!q.empty()) {
                int node = q.front();
                q.pop();
                us.erase(node);
                for(auto [next_node, d]: g[node]) {
                    reachable[next_node] = true;
                    if(shortest[next_node] > shortest[node] + d) {
                        shortest[next_node] = shortest[node] + d;
                        if(!us.contains(next_node)) {
                            q.push(next_node);
                            us.insert(next_node);
                        }
                    }
                }
            }
            if(!reachable[n]) {
                cout << "impossible";
            } else {
                cout << shortest[n];
            }
            return 0;
        }
    }// namespace acwing851
 
    namespace acwing852 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            cin >> n >> m;
            vector<unordered_map<int, int>> g(n + 1);
            vector cnt(n + 1, 0);
            vector shortest(n + 1, 0x3f3f3f);
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                if(g[x][y] == 0) {
                    g[x][y] = z;
                } else {
                    g[x][y] = min(g[x][y], z);
                }
            }
            for(int i = 1; i <= n; i++) {
                g[0][i] = 0;
            }
            if(spfa(g, m, n)) {
                cout << "Yes";
            } else {
                cout << "No";
            }
            return 0;
        }
 
        bool spfa(const vector<unordered_map<int, int>> &g, int /*m*/, int n) {
            vector cnt(n + 1, 0);
            vector shortest(n + 1, 0x3f3f3f);
            queue<int> q;
            unordered_set<int> us;
            q.push(0);
            us.insert(0);
            shortest[0] = 0;
            while(!q.empty()) {
                int node = q.front();
                q.pop();
                us.erase(node);
                for(auto [next_node, d]: g[node]) {
                    if(shortest[next_node] > shortest[node] + d) {
                        shortest[next_node] = shortest[node] + d;
                        cnt[next_node]      = cnt[node] + 1;
                        if(cnt[next_node] >= n + 1) {
                            return true;
                        }
                        if(!us.contains(next_node)) {
                            q.push(next_node);
                            us.insert(next_node);
                        }
                    }
                }
            }
            return false;
        }
    }// namespace acwing852
 
    namespace acwing854 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            int k;
            cin >> n >> m >> k;
            vector g(n + 1, vector<int>(n + 1, 1e9));
            for(int i = 0; i < m; i++) {
                int x;
                int y;
                int z;
                cin >> x >> y >> z;
                g[x][y] = min(g[x][y], z);
            }
            for(int i = 1; i <= n; i++) {
                g[i][i] = 0;
            }
            for(int l = 1; l <= n; l++) {
                for(int i = 1; i <= n; i++) {
                    for(int j = 1; j <= n; j++) {
                        g[i][j] = min(g[i][j], g[i][l] + g[l][j]);
                    }
                }
            }
            for(int i = 0; i < k; i++) {
                int x;
                int y;
                cin >> x >> y;
                if(g[x][y] > 1e9 / 2) {
                    cout << "impossible" << endl;
                } else {
                    cout << g[x][y] << endl;
                }
            }
            return 0;
        }
    }// namespace acwing854
 
    namespace acwing858 {
        int main(istream &cin, ostream &cout) {
            unsigned n;
            unsigned m;
            cin >> n >> m;
            vector g(n + 1, vector(n + 1, INT_MAX));
            vector dist(n + 1, INT_MAX);
            for(unsigned i = 0; i < m; i++) {
                int u;
                int v;
                int w;
                cin >> u >> v >> w;
                w       = min(w, g[u][v]);
                w       = min(w, g[v][u]);
                g[u][v] = w;
                g[v][u] = w;
            }
            unordered_set<int> us;
            int ans = 0;
            for(int i = 0; i < n; i++) {
                int t = -1;
                for(int j = 1; j <= n; j++) {
                    if(!us.contains(j) && (t == -1 || dist[t] > dist[j])) {
                        t = j;
                    }
                }
                if(i > 0 && dist[t] == INT_MAX) {
                    cout << "impossible";
                    return 0;
                }
                if(i > 0) {
                    ans += dist[t];
                }
                for(int j = 1; j <= n; j++) {
                    dist[j] = min(dist[j], g[t][j]);
                }
                us.insert(t);
            }
            cout << ans;
            return 0;
        }
    }// namespace acwing858
 
    namespace acwing859 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            cin >> n >> m;
            int ans = 0;
            int cnt = 1;
            vector<edge> edges(m);
            for(int i = 0; i < m; i++) {
                int u;
                int v;
                int n;
                cin >> edges[i].u >> edges[i].v >> edges[i].w;
            }
            sort(edges.begin(), edges.end());
            UnionFind uf(n + 1);
            for(const auto &edge: edges) {
                if(!uf.same(edge.u, edge.v)) {
                    cnt++;
                    uf.unite(edge.u, edge.v);
                    ans += edge.w;
                }
            }
            if(cnt < n) {
                cout << "impossible";
            } else {
                cout << ans;
            }
            return 0;
        }
 
        bool edge::operator<(const edge &e) const { return w < e.w; }
    }// namespace acwing859
 
    namespace acwing860 {
        int main(istream &cin, ostream &cout) {
            int n;
            int m;
            cin >> n >> m;
            vector g(n + 1, unordered_set<int>());
            vector color(n + 1, 3);
            for(int i = 0; i < m; i++) {
                int u;
                int v;
                cin >> u >> v;
                g[u].insert(v);
                g[v].insert(u);
            }
            for(int i = 1; i <= n; i++) {
                if(color[i] == 3) {
                    if(!dfs(g, i, color, 0)) {
                        cout << "No";
                        return 0;
                    }
                }
            }
            cout << "Yes";
            return 0;
        }
 
        bool dfs(vector<unordered_set<int>> &g, int node, vector<int> &color, int c) {
            color[node] = c;
            for(const auto sibling: g[node]) {
                if(color[sibling] == 3) {
                    if(!dfs(g, sibling, color, c == 0)) {
                        return false;
                    }
                } else if(color[sibling] == c) {
                    return false;
                }
            }
            return true;
        }
    }// namespace acwing860
 
    namespace acwing861 {
        int main(istream &cin, ostream &cout) {
            int n1;
            int n2;
            int m;
            cin >> n1 >> n2 >> m;
            int ans = 0;
            vector<unordered_set<int>> g(n1 + 1);
            vector match(n2 + 1, 0);
            vector st(n2 + 1, false);
            for(int i = 0; i < m; i++) {
                int u;
                int v;
                cin >> u >> v;
                g[u].insert(v);
            }
            for(int i = 1; i <= n1; i++) {
                st = vector(n2 + 1, false);
                if(find(g, i, st, match)) {
                    ans++;
                }
            }
            cout << ans;
            return 0;
        }
 
        bool find(vector<unordered_set<int>> &g, int x, vector<bool> &st, vector<int> &match) {
            for(const auto y: g[x]) {
                if(!st[y]) {
                    st[y] = true;
                    if(match[y] == 0 || find(g, match[y], st, match)) {
                        match[y] = x;
                        return true;
                    }
                }
            }
            return false;
        }
    }// namespace acwing861
 
    namespace acwing3373 {
        int main(istream &cin, ostream &cout) {
            string input;
            while(cin >> input) {
                if(input == "0") {
                    cout << 0 << endl;
                    continue;
                }
                unsigned short promotion       = 0;
                vector<unsigned short> result  = vector<unsigned short>();
                vector<unsigned short> charvec = vector<unsigned short>(input.length());
                for(auto i = 0; i < input.length(); i++) {
                    charvec[i] = input[i] - '0';
                }
                vector<unsigned short> next = vector<unsigned short>();
                while(!charvec.empty() && !(charvec.size() == 1 && charvec[0] == 0)) {
                    for(unsigned short d: charvec) {
                        unsigned short digit = promotion * 10 + d;
                        if(digit / 2 > 0 || !next.empty()) {
                            next.push_back(digit / 2);
                        }
                        promotion = digit % 2;
                    }
                    result.push_back(promotion);
                    promotion = 0;
                    charvec   = next;
                    next.clear();
                }
                for(auto i = result.rbegin(); i != result.rend(); i++) {
                    cout << *i;
                }
                cout << endl;
            }
            return 0;
        }
    }// namespace acwing3373
}// namespace acwing