luogu.cpp

浏览该文件的文档.

#include "luogu.h"
 
#include <algorithm>
#include <array>
#include <cmath>
#include <cstring>
#include <deque>
#include <iomanip>
#include <numeric>
#include <set>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
using namespace std;
 
namespace luogu {
    int P1001::main(istream &cin, ostream &cout) {
        unsigned int a;
        unsigned int b;
        cin >> a >> b;
        cout << a + b;
        return 0;
    }
 
    int P1000::main(istream & /*cin*/, ostream &cout) {
        cout << "                ********\n"
                "               ************\n"
                "               ####....#.\n"
                "             #..###.....##....\n"
                "             ###.......######              ###            ###\n"
                "                ...........               #...#          #...#\n"
                "               ##*#######                 #.#.#          #.#.#\n"
                "            ####*******######             #.#.#          #.#.#\n"
                "           ...#***.****.*###....          #...#          #...#\n"
                "           ....**********##.....           ###            ###\n"
                "           ....****    *****....\n"
                "             ####        ####\n"
                "           ######        ######\n"
                "##############################################################\n"
                "#...#......#.##...#......#.##...#......#.##------------------#\n"
                "###########################################------------------#\n"
                "#..#....#....##..#....#....##..#....#....#####################\n"
                "##########################################    #----------#\n"
                "#.....#......##.....#......##.....#......#    #----------#\n"
                "##########################################    #----------#\n"
                "#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#\n"
                "##########################################    ############";
        return 0;
    }
 
    int P1008::main(istream & /*cin*/, ostream &cout) {
        for(unsigned short i = 1; i <= 3; i++) {
            for(unsigned short j = 1; j <= 9; j++) {
                if(j == i) {
                    continue;
                }
                for(unsigned short k = 1; k <= 9; k++) {
                    if(k == i || k == j || k * 2 % 10 == j || k * 2 % 10 == i || k * 3 % 10 == j || k * 3 % 10 == i || k == 5) {
                        continue;
                    }
                    const unsigned short num = 100 * i + 10 * j + k;
                    if(num > 333) {
                        continue;
                    }
                    unsigned short num2 = 2 * num;
                    unsigned short num3 = 3 * num;
                    auto um             = unordered_set<unsigned short>();
                    um.insert(i);
                    um.insert(j);
                    um.insert(k);
                    unsigned short n = num2 % 10;
 
                    if(um.contains(n) || n == 0) {
                        continue;
                    }
                    um.insert(n);
                    num2 /= 10;
                    n = num2 % 10;
                    if(um.contains(n) || n == 0) {
                        continue;
                    }
                    um.insert(n);
                    num2 /= 10;
                    n = num2 % 10;
                    if(um.contains(n) || n == 0) {
                        continue;
                    }
                    um.insert(n);
 
                    n = num3 % 10;
                    if(um.contains(n) || n == 0) {
                        continue;
                    }
                    um.insert(n);
                    num3 /= 10;
                    n = num3 % 10;
                    if(um.contains(n) || n == 0) {
                        continue;
                    }
                    um.insert(n);
                    num3 /= 10;
                    n = num3 % 10;
                    if(um.contains(n) || n == 0) {
                        continue;
                    }
                    um.insert(n);
                    cout << num << " " << num * 2 << " " << num * 3 << endl;
                }
            }
        }
        return 0;
    }
 
    int P1002::main(istream &cin, ostream &cout) {
        int n;
        int m;
        int cx;
        int cy;
        cin >> n >> m >> cx >> cy;
        unsigned long long board[21][21] = {};
        board[0][0]                      = 1;
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(abs(cx - i) * abs(cy - j) == 2 || i == cx && j == cy) {
                    board[i][j] = 0;
                    continue;
                }
                if(i - 1 >= 0) {
                    board[i][j] += board[i - 1][j];
                }
                if(j - 1 >= 0) {
                    board[i][j] += board[i][j - 1];
                }
            }
        }
        cout << board[n][m];
        return 0;
    }
 
    int P1003::main(istream &cin, ostream &cout) {
        auto as = vector<unsigned int>();
        auto bs = vector<unsigned int>();
        auto gs = vector<unsigned int>();
        auto ks = vector<unsigned int>();
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            unsigned int a;
            unsigned int b;
            unsigned int g;
            unsigned int k;
            cin >> a >> b >> g >> k;
            as.push_back(a);
            bs.push_back(b);
            gs.push_back(g);
            ks.push_back(k);
        }
        unsigned int x;
        unsigned int y;
        cin >> x >> y;
        for(int i = n - 1; i >= 0; i--) {
            if(as[i] <= x && x <= as[i] + gs[i] && bs[i] <= y && y <= bs[i] + ks[i]) {
                cout << i + 1;
                return 0;
            }
        }
        cout << -1;
        return 0;
    }
 
    int P5703::main(istream &cin, ostream &cout) {
        unsigned long a;
        unsigned long b;
        cin >> a >> b;
        cout << a * b;
        return 0;
    }
 
    int P5704::main(istream &cin, ostream &cout) {
        char ch;
        cin >> ch;
        cout << static_cast<char>(toupper(ch));
        return 0;
    }
 
    int P5705::main(istream &cin, ostream &cout) {
        string s;
        cin >> s;
        for(int i = s.length() - 1; i >= 0; i--) {
            cout << s[i];
        }
        return 0;
    }
 
    int P5706::main(istream &cin, ostream &cout) {
        double t;
        int n;
        cin >> t >> n;
        cout << setiosflags(ios::fixed) << setprecision(3) << t / n << endl
             << n * 2;
        return 0;
    }
 
    int P1425::main(istream &cin, ostream &cout) {
        int a;
        int b;
        int c;
        int d;
        cin >> a >> b >> c >> d;
        const int diff = (c - a) * 60 + d - b;
        cout << diff / 60 << " " << diff % 60;
        return 0;
    }
 
    int P2433::main(istream &cin, ostream &cout) {
        int T;
        cin >> T;
        if(T == 1) {
            cout << "I love Luogu!";
        } else if(T == 2) {
            cout << 2 + 4 << " " << 10 - 2 - 4;
        } else if(T == 3) {
            cout << 14 / 4 << endl
                 << 14 / 4 * 4 << endl
                 << 14 % 4;
        } else if(T == 4) {
            cout << setiosflags(ios::fixed) << setprecision(3) << 500.0 / 3.0;
        } else if(T == 5) {
            cout << (260 + 220) / (12 + 20);
        } else if(T == 6) {
            cout << sqrt(6 * 6 + 9 * 9);
        } else if(T == 7) {
            int deposit = 100;
            deposit += 10;
            cout << deposit << endl;
            deposit -= 20;
            cout << deposit << endl;
            deposit = 0;
            cout << deposit << endl;
        } else if(T == 8) {
            cout << 2 * 5 * 3.141593 << endl;
            cout << 5 * 5 * 3.141593 << endl;
            cout << 4 * 5 * 5 * 5 * 3.141593 / 3 << endl;
        } else if(T == 9) {
            const int peach = 1;
            cout << (((peach + 1) * 2 + 1) * 2 + 1) * 2;
        } else if(T == 10) {
            cout << 90 / 10;
        } else if(T == 11) {
            cout << 100.0 / 3.0;
        } else if(T == 12) {
            cout << 'M' - 'A' + 1 << endl;
            cout << static_cast<char>('A' - 1 + 18);
        } else if(T == 13) {
            const double r1 = 4;
            const double r2 = 10;
            const double v1 = 4 * r1 * r1 * r1 * 3.141593 / 3;
            const double v2 = 4 * r2 * r2 * r2 * 3.141593 / 3;
            cout << static_cast<int>(pow(v1 + v2, 1.0 / 3.0));
        } else if(T == 14) {
            cout << 50;
        }
        return 0;
    }
 
    int P5708::main(istream &cin, ostream &cout) {
        double a;
        double b;
        double c;
        cin >> a >> b >> c;
        const double p = (a + b + c) / 2;
        cout << setiosflags(ios::fixed) << setprecision(1) << sqrt(p * (p - a) * (p - b) * (p - c));
        return 0;
    }
 
    int P1421::main(istream &cin, ostream &cout) {
        int a;
        int b;
        cin >> a >> b;
        cout << (10 * a + b) / 19;
        return 0;
    }
 
    int P5709::main(istream &cin, ostream &cout) {
        int m;
        int t;
        int s;
        cin >> m >> t >> s;
        if(t == 0) {
            cout << 0;
            return 0;
        }
        int eaten = s / t;
        if(t * eaten != s) {
            eaten++;
        }
        cout << max(0, m - eaten);
        return 0;
    }
 
    int P2181::main(istream &cin, ostream &cout) {
        unsigned long long n;
        unsigned long long count = 0;
        cin >> n;
        for(long long i = 1; i <= n - 2; i++) {
            count += i * (n - 2 - i);
        }
        count *= n;
        count /= 4;
        cout << count;
        return 0;
    }
 
    int P5707::main(istream &cin, ostream &cout) {
        unsigned int s;
        unsigned int v;
        cin >> s >> v;
        double t = 8 * 60 - (static_cast<double>(s) / static_cast<double>(v) + 10);
        if(t < 0) {
            t += 24 * 60;
        }
        const int h = static_cast<int>(t / 60);
        const int m = static_cast<int>(t) % 60;
        if(h < 10) {
            cout << 0;
        }
        cout << h << ":";
        if(m < 10) {
            cout << 0;
        }
        cout << m;
        return 0;
    }
 
    int P3954::main(istream &cin, ostream &cout) {
        unsigned short a;
        unsigned short b;
        unsigned short c;
        cin >> a >> b >> c;
        cout << (a * 2 + b * 3 + c * 5) / 10;
        return 0;
    }
 
    int P5710::main(istream &cin, ostream &cout) {
        unsigned short x;
        cin >> x;
        const bool b1 = x % 2 == 0;
        const bool b2 = x > 4 && x <= 12;
        cout << static_cast<int>(b1 && b2) << " " << static_cast<int>(b1 || b2) << " " << (b1 xor b2) << " " << static_cast<int>(!b1 && !b2);
        return 0;
    }
 
    int P5711::main(istream &cin, ostream &cout) {
        unsigned int year;
        cin >> year;
        if(year % 4 == 0) {
            //是4的倍数
            if(year % 100 == 0) {
                //是100的倍数
                if(year % 400 == 0) {
                    //是400的倍数
                    cout << "1";
                    return 0;
                }
                //不是400的倍数
                cout << "0";
                return 0;
            }
            //不是100的倍数
            cout << "1";
            return 0;
        }
        //不是4的倍数
        cout << "0";
        return 0;
    }
 
    int P5712::main(istream &cin, ostream &cout) {
        unsigned short x;
        cin >> x;
        cout << "Today, I ate " << x << " apple";
        if(x > 1) {
            cout << "s";
        }
        cout << ".";
        return 0;
    }
 
    int P5713::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        const unsigned int local = n * 5;
        const unsigned int luogu = 11 + 3 * n;
        if(local < luogu) {
            cout << "Local";
        } else {
            cout << "Luogu";
        }
        return 0;
    }
 
    int P5715::main(istream &cin, ostream &cout) {
        unsigned int abc[3];
        cin >> abc[0] >> abc[1] >> abc[2];
        sort(abc, abc + 3);
        for(const auto i: abc) {
            cout << i << " ";
        }
        return 0;
    }
 
    int P5714::main(istream &cin, ostream &cout) {
        double m;
        double n;
        cin >> m >> n;
        const double bmi = m / (n * n);
        if(bmi < 18.5) {
            cout << "Underweight";
        } else if(bmi >= 18.5 && bmi < 24) {
            cout << "Normal";
        } else {
            cout << bmi << endl
                 << "Overweight";
        }
        return 0;
    }
 
    int P5716::main(istream &cin, ostream &cout) {
        int year;
        int month;
        cin >> year >> month;
        const bool bissextile = year % 400 == 0 || year % 4 == 0 && year % 100 != 0;
        if(month == 4 || month == 6 || month == 9 || month == 11) {
            cout << 30;
        } else if(month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12) {
            cout << 31;
        } else if(bissextile) {
            cout << 29;
        } else {
            cout << 28;
        }
        return 0;
    }
 
    int P1085::main(istream &cin, ostream &cout) {
        unsigned short a;
        unsigned short b;
        unsigned int maximum   = 0;
        unsigned int maximum_i = 0;
        unsigned int i         = 0;
        while(cin >> a && cin >> b) {
            i++;
            if(a + b > 8 && a + b > maximum) {
                maximum_i = i;
                maximum   = a + b;
            }
        }
        cout << maximum_i;
        return 0;
    }
 
    int P1909::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int num;
        int price;
        int minimum = -1;
        for(int i = 0; i < 3; i++) {
            cin >> num >> price;
            int count = n / num;
            if(n % num != 0) {
                count++;
            }
            int sum = count * price;
            minimum = minimum == -1 ? sum : min(minimum, sum);
        }
        cout << minimum;
        return 0;
    }
 
    int P1055::main(istream &cin, ostream &cout) {
        string isbn;
        cin >> isbn;
        const string isbn_prefix = isbn.substr(0, isbn.length() - 1);
        int sum                  = 0;
        int count                = 1;
        for(const char ch: isbn_prefix) {
            if(isdigit(ch) != 0) {
                sum += (ch - '0') * count++;
                sum %= 11;
            }
        }
        sum %= 11;
        int end = *isbn.rbegin() - '0';
        if(end == 'X' - '0') {
            end = 10;
        }
        if(sum == end) {
            cout << "Right";
        } else {
            end = sum;
            if(sum == 10) {
                end = 'X' - '0';
            }
            cout << isbn_prefix << static_cast<char>(end + '0');
        }
        return 0;
    }
 
    int P1422::main(istream &cin, ostream &cout) {
        double fee = 0;
        int power;
        cin >> power;
        cout << setiosflags(ios::fixed) << setprecision(1);
        if(power <= 150) {
            fee = power * 0.4463;
        } else if(power <= 400) {
            fee = 150 * 0.4463 + (power - 150) * 0.4663;
        } else {
            fee = 150 * 0.4463 + (400 - 150) * 0.4663 + (power - 400) * 0.5663;
        }
        cout << floor(fee * 10 + 0.5) / 10;
        return 0;
    }
 
    int P1424::main(istream &cin, ostream &cout) {
        unsigned short x;
        unsigned int n;
        cin >> x >> n;
        x--;
        unsigned int count = n / 7 * 5 * 250;
        n %= 7;
        for(unsigned int i = 0; i < n; i++) {
            if((x + i) % 7 < 5) {
                count += 250;
            }
        }
        cout << count;
        return 0;
    }
 
    int P1888::main(istream &cin, ostream &cout) {
        int a;
        int b;
        int c;
        cin >> a >> b >> c;
        int maximum = a;
        int minimum = a;
        maximum     = max(maximum, b);
        maximum     = max(maximum, c);
        minimum     = min(minimum, b);
        minimum     = min(minimum, c);
        const int g = gcd(maximum, minimum);
        cout << minimum / g << "/" << maximum / g;
        return 0;
    }
 
    int P1888::gcd(int m, int n) {
        int r = m;
        while(r != 0) {
            r = m % n;
            m = n;
            n = r;
        }
        return m;
    }
 
    int P1046::main(istream &cin, ostream &cout) {
        int h[10];
        for(int &i: h) {
            cin >> i;
        }
        int t;
        cin >> t;
        t += 30;
        int count = 0;
        for(const int i: h) {
            if(t >= i) {
                count++;
            }
        }
        cout << count;
        return 0;
    }
 
    int P5717::main(istream &cin, ostream &cout) {
        unsigned int e[3];
        cin >> e[0] >> e[1] >> e[2];
        sort(e, e + 3);
        if(e[0] + e[1] <= e[2]) {
            cout << "Not triangle" << endl;
        } else {
            const unsigned int e02 = e[0] * e[0];
            const unsigned int e12 = e[1] * e[1];
            const unsigned int e22 = e[2] * e[2];
            if(e02 + e12 == e[2] * e[2]) {
                cout << "Right triangle" << endl;
            } else if(e02 + e12 > e22) {
                cout << "Acute triangle" << endl;
            } else if(e02 + e12 < e22) {
                cout << "Obtuse triangle" << endl;
            }
            if(e[0] == e[1]) {
                cout << "Isosceles triangle" << endl;
                if(e[1] == e[2]) {
                    cout << "Equilateral triangle" << endl;
                }
            }
        }
        return 0;
    }
 
    int P4414::main(istream &cin, ostream &cout) {
        unsigned int num[3];
        cin >> num[0] >> num[1] >> num[2];
        unsigned a = 100;
        unsigned b;
        unsigned c = 0;
        for(const unsigned int i: num) {
            if(a > i) {
                a = i;
            }
            if(c < i) {
                c = i;
            }
        }
        for(const unsigned int i: num) {
            if(i != a && i != c) {
                b = i;
            }
        }
        char ch;
        for(int i = 0; i < 3; i++) {
            cin >> ch;
            if(ch == 'A') {
                cout << a << " ";
            } else if(ch == 'B') {
                cout << b << " ";
            } else {
                cout << c << " ";
            }
        }
        return 0;
    }
 
    int P5718::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int minimum = 1000;
        int a;
        for(int i = 0; i < n; i++) {
            cin >> a;
            minimum = min(minimum, a);
        }
        cout << minimum;
        return 0;
    }
 
    int P5719::main(istream &cin, ostream &cout) {
        int n;
        int k;
        cin >> n >> k;
        int sum_a   = 0;
        int count_a = 0;
        int sum_b   = 0;
        int count_b = 0;
        for(int i = 1; i <= n; i++) {
            if(i % k == 0) {
                sum_a += i;
                count_a++;
            } else {
                sum_b += i;
                count_b++;
            }
        }
        cout << fixed << setprecision(1) << static_cast<double>(sum_a) / static_cast<double>(count_a) << " " << static_cast<double>(sum_b) / static_cast<double>(count_b);
        return 0;
    }
 
    int P5720::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int i = 1;
        while(n != 1) {
            n >>= 1;
            i++;
        }
        cout << i;
        return 0;
    }
 
    int P5721::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int count = 1;
        for(int i = n; i >= 1; i--) {
            for(int j = 0; j < i; j++) {
                cout << setw(2) << setfill('0') << right << count++;
            }
            cout << endl;
        }
        return 0;
    }
 
    int P1009::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        const string ans[] = {"", "1", "3", "9", "33", "153", "873", "5913", "46233", "409113", "4037913", "43954713", "522956313", "6749977113", "93928268313", "1401602636313", "22324392524313", "378011820620313", "6780385526348313", "128425485935180313", "2561327494111820313", "53652269665821260313", "1177652997443428940313", "27029669736328405580313", "647478071469567844940313", "16158688114800553828940313", "419450149241406189412940313", "11308319599659758350180940313", "316196664211373618851684940313", "9157958657951075573395300940313", "274410818470142134209703780940313", "8497249472648064951935266660940313", "271628086406341595119153278820940313", "8954945705218228090637347680100940313", "304187744744822368938255957323620940313", "10637335711130967298604907294846820940313", "382630662501032184766604355445682020940313", "14146383753727377231082583937026584420940313", "537169001220328488991089808037100875620940313", "20935051082417771847631371547939998232420940313", "836850334330315506193242641144055892504420940313", "34289376947494122614363304694584807557656420940313", "1439295494700374021157505910939096377494040420940313", "61854558558074209658512637979453093884758552420940313", "2720126133346522977702138448994068984204397080420940313", "122342346998826717539665299944651784048588130840420940313", "5624964506810915667389970728744906677010239883800420940313", "264248206017979096310354325882356886646207872272920420940313", "12678163798554051767172643373255731925167694226950680420940313", "620960027832821612639424806694551108812720525606160920420940313", "31035053229546199656252032972759319953190362094566672920420940313"};
        cout << ans[n];
        return 0;
    }
 
    int P1980::main(istream &cin, ostream &cout) {
        int n;
        char x;
        cin >> n >> x;
        auto oss = ostringstream();
        for(int i = 1; i <= n; i++) {
            oss << i;
        }
        const string str = oss.str();
        int ans          = 0;
        for(const char ch: str) {
            if(ch == x) {
                ans++;
            }
        }
        cout << ans;
        return 0;
    }
 
    int P1035::main(istream &cin, ostream &cout) {
        int k;
        cin >> k;
        int n    = 1;
        double s = 0;
        while(s <= k) {
            s += 1.0 / static_cast<double>(n++);
        }
        cout << n - 1;
        return 0;
    }
 
    int P2669::main(istream &cin, ostream &cout) {
        unsigned int k;
        unsigned int coin = 0;
        unsigned current  = 1;
        unsigned rest     = 1;
        cin >> k;
        for(unsigned int i = 0; i < k; i++) {
            if(rest == 0) {
                current++;
                rest = current;
            }
            coin += current;
            rest--;
        }
        cout << coin;
        return 0;
    }
 
    int P5722::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        unsigned int ans = 0;
        for(unsigned int i = 1; i <= n; i++) {
            ans += i;
        }
        cout << ans;
        return 0;
    }
 
    int P5723::main(istream &cin, ostream &cout) {
        unsigned int l;
        unsigned int sum = 0;
        int count        = 0;
        cin >> l;
        for(unsigned int i = 2; i <= l; i++) {
            bool is_prime = true;
            for(unsigned int j = 2; j <= sqrt(i); j++) {
                if(i % j == 0) {
                    is_prime = false;
                    break;
                }
            }
            if(is_prime) {
                sum += i;
                if(sum <= l) {
                    cout << i << endl;
                    count++;
                } else {
                    break;
                }
            }
        }
        cout << count << endl;
        return 0;
    }
 
    int P1217::main(istream &cin, ostream &cout) {
        unsigned int a;
        unsigned int b;
        cin >> a >> b;
        auto palindromes = set<unsigned int>();
        if(a <= 2 && 2 <= b) {
            palindromes.insert(2);
        }
        if(a <= 10 && b >= 0) {
            for(unsigned int d1 = 3; d1 <= 9; d1 += 2) {
                //1 [0,10]
                unsigned int palindrome = d1;
                if(a <= palindrome && palindrome <= b) {
                    palindromes.insert(palindrome);
                }
            }
        }
        if(a <= 100 && b >= 10) {
            for(unsigned int d1 = 1; d1 <= 9; d1 += 2) {
                //2 [10,100]
                unsigned int palindrome = d1 * 10 + d1;
                if(a <= palindrome && palindrome <= b) {
                    palindromes.insert(palindrome);
                }
            }
        }
        if(a <= 1000 && b >= 100) {
            for(unsigned int d1 = 1; d1 <= 9; d1 += 2) {
                //3 [100,1000]
                for(unsigned int d2 = 0; d2 <= 9; d2++) {
                    unsigned int palindrome = d1 * 100 + d2 * 10 + d1;
                    if(a <= palindrome && palindrome <= b) {
                        palindromes.insert(palindrome);
                    }
                }
            }
        }
        if(a <= 10000 && b >= 1000) {
            for(unsigned int d1 = 1; d1 <= 9; d1 += 2) {
                //4 [1000,10000]
                for(unsigned int d2 = 0; d2 <= 9; d2++) {
                    unsigned int palindrome = d1 * 1000 + d2 * 100 + d2 * 10 + d1;
                    if(a <= palindrome && palindrome <= b) {
                        palindromes.insert(palindrome);
                    }
                }
            }
        }
        if(a <= 100000 && b >= 10000) {
            for(unsigned int d1 = 1; d1 <= 9; d1 += 2) {
                //5 [10000,100000]
                for(unsigned int d2 = 0; d2 <= 9; d2++) {
                    for(unsigned int d3 = 0; d3 <= 9; d3++) {
                        unsigned int palindrome = d1 * 10000 + 1000 * d2 + 100 * d3 + 10 * d2 + d1;
                        if(a <= palindrome && palindrome <= b) {
                            palindromes.insert(palindrome);
                        }
                    }
                }
            }
        }
        if(a <= 1000000 && b >= 100000) {
            for(unsigned int d1 = 1; d1 <= 9; d1 += 2) {
                //6 [100000,1000000]
                for(unsigned int d2 = 0; d2 <= 9; d2++) {
                    for(unsigned int d3 = 0; d3 <= 9; d3++) {
                        unsigned int palindrome = d1 * 100000 + d2 * 10000 + d3 * 1000 + d3 * 100 + d2 * 10 + d1;
                        if(a <= palindrome && palindrome <= b) {
                            palindromes.insert(palindrome);
                        }
                    }
                }
            }
        }
        if(a <= 10000000 && b >= 1000000) {
            for(unsigned int d1 = 1; d1 <= 9; d1 += 2) {
                //7 [1000000,10000000]
                for(unsigned int d2 = 0; d2 <= 9; d2++) {
                    for(unsigned int d3 = 0; d3 <= 9; d3++) {
                        for(unsigned int d4 = 0; d4 <= 9; d4++) {
                            unsigned int palindrome = d1 * 1000000 + d2 * 100000 + d3 * 10000 + d4 * 1000 + d3 * 100 + d2 * 10 + d1;
                            if(a <= palindrome && palindrome <= b) {
                                palindromes.insert(palindrome);
                            }
                        }
                    }
                }
            }
        }
        if(a <= 100000000 && b >= 10000000) {
            for(unsigned int d1 = 1; d1 <= 9; d1 += 2) {
                //8 [10000000,100000000]
                for(unsigned int d2 = 0; d2 <= 9; d2++) {
                    for(unsigned int d3 = 0; d3 <= 9; d3++) {
                        for(unsigned int d4 = 0; d4 <= 9; d4++) {
                            unsigned int palindrome = d1 * 10000000 + d2 * 1000000 + d3 * 100000 + d4 * 10000 + d4 * 1000 + d3 * 100 + d2 * 10 + d1;
                            if(a <= palindrome && palindrome <= b) {
                                palindromes.insert(palindrome);
                            }
                        }
                    }
                }
            }
        }
        for(const auto palindrome: palindromes) {
            bool is_prime = true;
            for(unsigned int i = 3; i <= sqrt(palindrome); i++) {
                if(palindrome % i == 0) {
                    is_prime = false;
                    break;
                }
            }
            if(is_prime) {
                cout << palindrome << endl;
            }
        }
        return 0;
    }
 
    int P1423::main(istream &cin, ostream &cout) {
        double x;
        cin >> x;
        double sn = 2;
        for(int i = 1; sn < x; i++) {
            sn = 100 * (1 - pow(0.98, i));
            if(sn >= x) {
                cout << i;
                return 0;
            }
        }
        return 0;
    }
 
    int P1307::main(istream &cin, ostream &cout) {
        bool negative = false;
        int n;
        int ans = 0;
        cin >> n;
        if(n < 0) {
            n        = -n;
            negative = true;
        }
        while(n != 0) {
            ans *= 10;
            ans += n % 10;
            n /= 10;
        }
        if(negative) {
            ans = -ans;
        }
        cout << ans;
        return 0;
    }
 
    int P1720::main(istream &cin, ostream &cout) {
        double n;
        cin >> n;
        cout << fixed << setprecision(2) << (pow((1 + sqrt(5)) / 2, n) - pow((1 - sqrt(5)) / 2, n)) / sqrt(5);
        return 0;
    }
 
    int P5724::main(istream &cin, ostream &cout) {
        unsigned short n;
        cin >> n;
        unsigned int a;
        unsigned int maximum = 0;
        unsigned int minimum = 1000;
        for(unsigned short i = 0; i < n; i++) {
            cin >> a;
            maximum = max(maximum, a);
            minimum = min(minimum, a);
        }
        cout << maximum - minimum;
        return 0;
    }
 
    int P1420::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        unsigned int prev;
        cin >> prev;
        unsigned int a;
        unsigned int len = 1;
        unsigned int ans = 1;
        for(unsigned int i = 1; i < n; i++, prev = a, ans = max(ans, len)) {
            cin >> a;
            if(a == prev + 1) {
                len++;
            } else {
                len = 1;
            }
        }
        cout << ans;
        return 0;
    }
 
    int P1075::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for(int i = 2; i <= sqrt(n); i++) {
            if(n % i == 0) {
                cout << n / i;
                return 0;
            }
        }
        return 0;
    }
 
    int P5725::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cout << setw(2) << setfill('0') << right << i * n + j + 1;
            }
            cout << endl;
        }
        int count = 1;
        cout << endl;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n - i - 1; j++) {
                cout << "  ";
            }
            for(int j = 0; j < i + 1; j++) {
                cout << setw(2) << setfill('0') << right << count++;
            }
            cout << endl;
        }
        return 0;
    }
 
    int P4956::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for(int k = 1; 1092 * k <= n; k++) {
            if((n - 1092 * k) % 364 == 0) {
                const int x = (n - 1092 * k) / 364;
                if(x < 1 || 100 < x) {
                    continue;
                }
                cout << x << endl
                     << k;
                break;
            }
        }
        return 0;
    }
 
    int P5726::main(istream &cin, ostream &cout) {
        int n;
        int maximum = 0;
        int minimum = 10;
        int sum     = 0;
        cin >> n;
        int score;
        for(int i = 0; i < n; i++) {
            cin >> score;
            sum += score;
            maximum = max(maximum, score);
            minimum = min(minimum, score);
        }
        sum -= maximum;
        sum -= minimum;
        cout << fixed << setprecision(2) << static_cast<double>(sum) / (n - 2);
        return 0;
    }
 
    int P1089::main(istream &cin, ostream &cout) {
        int budget;
        int saving  = 0;
        int current = 0;
        for(int i = 0; i < 12; i++) {
            current += 300;
            cin >> budget;
            if(current < budget) {
                cout << -(i + 1);
                return 0;
            }
            current -= budget;
            saving += current / 100 * 100;
            current %= 100;
        }
        cout << current + saving / 5 * 6;
        return 0;
    }
 
 
    int P1428::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *fish = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> fish[i];
        }
        for(int i = 0; i < n; i++) {
            int count = 0;
            for(int j = 0; j < i; j++) {
                if(fish[j] < fish[i]) {
                    count++;
                }
            }
            cout << count << " ";
        }
        delete[] fish;
        return 0;
    }
 
    int P1427::main(istream &cin, ostream &cout) {
        unsigned int n;
        auto vec = vector<unsigned int>();
        while(true) {
            cin >> n;
            if(n == 0) {
                break;
            }
            vec.push_back(n);
        }
        for(auto i = vec.rbegin(); i != vec.rend(); ++i) {
            cout << *i << " ";
        }
        return 0;
    }
 
    int P5727::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto vec = vector<int>();
        while(n != 1) {
            vec.push_back(n);
            if(n % 2 != 0) {
                n = n * 3 + 1;
            } else {
                n /= 2;
            }
        }
        vec.push_back(n);
        for(auto i = vec.rbegin(); i != vec.rend(); ++i) {
            cout << *i << " ";
        }
        return 0;
    }
 
    int P1047::main(istream &cin, ostream &cout) {
        int l;
        int m;
        cin >> l >> m;
        auto *tree = new bool[l + 1];
        memset(tree, 1, (l + 1) * sizeof(bool));
        for(int i = 0; i < m; i++) {
            int u;
            int v;
            cin >> u >> v;
            for(int j = u; j <= v; j++) {
                tree[j] = false;
            }
        }
        int ans = 0;
        for(int i = 0; i <= l; i++) {
            if(tree[i]) {
                ans++;
            }
        }
        cout << ans;
        delete[] tree;
        return 0;
    }
 
    int P5728::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *students = new int *[n];
        for(int i = 0; i < n; i++) {
            students[i] = new int[3];
            cin >> students[i][0] >> students[i][1] >> students[i][2];
        }
        int ans = 0;
        for(int i = 0; i + 1 < n; i++) {
            int sum_i = 0;
            for(int k = 0; k < 3; k++) {
                sum_i += students[i][k];
            }
            for(int j = i + 1; j < n; j++) {
                bool flag = true;
                int sum_j = 0;
                for(int k = 0; k < 3; k++) {
                    sum_j += students[j][k];
                    if(abs(students[i][k] - students[j][k]) > 5) {
                        flag = false;
                        break;
                    }
                }
                if(flag && abs(sum_i - sum_j) <= 10) {
                    ans++;
                }
            }
        }
        cout << ans;
        for(int i = 0; i < n; i++) {
            delete[] students[i];
        }
        delete[] students;
        return 0;
    }
 
    int P5729::main(istream &cin, ostream &cout) {
        int w;
        int x;
        int h;
        cin >> w >> x >> h;
        bool block[21][21][21] = {};
        memset(block, 1, sizeof block);
        int q;
        cin >> q;
        while(q-- != 0) {
            int x1;
            int y1;
            int z1;
            int x2;
            int y2;
            int z2;
            cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
            for(int i = x1; i <= x2; i++) {
                for(int j = y1; j <= y2; j++) {
                    for(int k = z1; k <= z2; k++) {
                        block[i][j][k] = false;
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= w; i++) {
            for(int j = 1; j <= x; j++) {
                for(int k = 1; k <= h; k++) {
                    if(block[i][j][k]) {
                        ans++;
                    }
                }
            }
        }
        cout << ans;
        return 0;
    }
 
    int P2550::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        bool winning_numbers[34];
        memset(winning_numbers, 0, sizeof winning_numbers);
        int prize_numbers[7];
        memset(prize_numbers, 0, sizeof prize_numbers);
        for(int i = 0; i < 7; i++) {
            int winning_number;
            cin >> winning_number;
            winning_numbers[winning_number] = true;
        }
        for(int i = 0; i < n; i++) {
            int prize_number = 7;
            for(int j = 0; j < 7; j++) {
                int lottery_number;
                cin >> lottery_number;
                if(winning_numbers[lottery_number]) {
                    prize_number--;
                }
            }
            prize_numbers[prize_number]++;
        }
        for(int i = 0; i < 7; i++) {
            cout << prize_numbers[i] << " ";
        }
        return 0;
    }
 
    int P2615::main(istream &cin, ostream &cout) {
        int n;
        int square[40][40];
        memset(square, 0, sizeof square);
        auto um = unordered_map<int, pair<int, int>>();
        cin >> n;
        square[0][n / 2] = 1;
        um[1]            = make_pair(0, n / 2);
        for(int k = 2; k <= n * n; k++) {
            auto [prev_x, prev_y] = um[k - 1];
            if(prev_x == 0 && prev_y != n - 1) {
                //若 (K−1) 在第一行但不在最后一列，则将 K 填在最后一行， (K−1) 所在列的右一列；
                square[n - 1][prev_y + 1] = k;
                um[k]                     = make_pair(n - 1, prev_y + 1);
            } else if(prev_y == n - 1 && prev_x != 0) {
                //若 (K−1) 在最后一列但不在第一行，则将 K 填在第一列， (K−1) 所在行的上一行；
                square[prev_x - 1][0] = k;
                um[k]                 = make_pair(prev_x - 1, 0);
            } else if(prev_x == 0 && prev_y == n - 1) {
                //若 (K−1) 在第一行最后一列，则将 K 填在 (K−1) 的正下方；
                square[1][prev_y] = k;
                um[k]             = make_pair(1, prev_y);
            } else if(prev_x != 0 && prev_y != n - 1) {
                //若 (K−1) 既不在第一行，也不在最后一列，如果 (K−1) 的右上方还未填数，则将 K 填在 (K−1) 的右上方，否则将 K 填在 (K−1) 的正下方。
                if(square[prev_x - 1][prev_y + 1] == 0) {
                    square[prev_x - 1][prev_y + 1] = k;
                    um[k]                          = make_pair(prev_x - 1, prev_y + 1);
                } else {
                    square[prev_x + 1][prev_y] = k;
                    um[k]                      = make_pair(prev_x + 1, prev_y);
                }
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cout << square[i][j] << " ";
            }
            cout << endl;
        }
        return 0;
    }
 
    int P5730::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        char screen[5][400];
        memset(screen, '.', sizeof screen);
        const char nums[10][5][3] = {
                {{'X', 'X', 'X'},
                 {'X', '.', 'X'},
                 {'X', '.', 'X'},
                 {'X', '.', 'X'},
                 {'X', 'X', 'X'}},
                {{'.', '.', 'X'},
                 {'.', '.', 'X'},
                 {'.', '.', 'X'},
                 {'.', '.', 'X'},
                 {'.', '.', 'X'}},
                {{'X', 'X', 'X'},
                 {'.', '.', 'X'},
                 {'X', 'X', 'X'},
                 {'X', '.', '.'},
                 {'X', 'X', 'X'}},
                {{'X', 'X', 'X'},
                 {'.', '.', 'X'},
                 {'X', 'X', 'X'},
                 {'.', '.', 'X'},
                 {'X', 'X', 'X'}},
                {{'X', '.', 'X'},
                 {'X', '.', 'X'},
                 {'X', 'X', 'X'},
                 {'.', '.', 'X'},
                 {'.', '.', 'X'}},
                {{'X', 'X', 'X'},
                 {'X', '.', '.'},
                 {'X', 'X', 'X'},
                 {'.', '.', 'X'},
                 {'X', 'X', 'X'}},
                {{'X', 'X', 'X'},
                 {'X', '.', '.'},
                 {'X', 'X', 'X'},
                 {'X', '.', 'X'},
                 {'X', 'X', 'X'}},
                {{'X', 'X', 'X'},
                 {'.', '.', 'X'},
                 {'.', '.', 'X'},
                 {'.', '.', 'X'},
                 {'.', '.', 'X'}},
                {{'X', 'X', 'X'},
                 {'X', '.', 'X'},
                 {'X', 'X', 'X'},
                 {'X', '.', 'X'},
                 {'X', 'X', 'X'}},
                {{'X', 'X', 'X'},
                 {'X', '.', 'X'},
                 {'X', 'X', 'X'},
                 {'.', '.', 'X'},
                 {'X', 'X', 'X'}}};
        for(int i = 0; i < n; i++) {
            char num;
            cin >> num;
            num -= '0';
            for(int j = 0; j < 5; j++) {
                for(int k = 0; k < 3; k++) {
                    screen[j][k + i * 4] = nums[num][j][k];
                }
            }
        }
        for(int i = 0; i < 5; i++) {
            for(int j = 0; j < 4 * n - 1; j++) {
                cout << screen[i][j];
            }
            cout << endl;
        }
        return 0;
    }
 
    int P1554::main(istream &cin, ostream &cout) {
        int nums[10] = {};
        int m;
        int n;
        cin >> m >> n;
        auto ss = stringstream();
        for(int i = m; i <= n; i++) {
            ss << i;
        }
        char ch;
        while(ss >> ch) {
            nums[ch - '0']++;
        }
        for(int i = 0; i < 10; i++) {
            cout << nums[i] << " ";
        }
        return 0;
    }
 
    int P2141::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto s = set<int>();
        for(int i = 0; i < n; i++) {
            int num;
            cin >> num;
            s.insert(num);
        }
        int ans = 0;
        for(auto i = s.begin(); i != s.end(); ++i) {
            for(auto j = s.begin(); j != i; ++j) {
                int sub = *i - *j;
                if(sub != *j && s.contains(sub)) {
                    ans++;
                    break;
                }
            }
        }
        cout << ans;
        return 0;
    }
 
    int P1614::main(istream &cin, ostream &cout) {
        int n;
        int m;
        cin >> n >> m;
        auto *a = new int[n];
        for(int i = 0; i < n; i++) {
            cin >> a[i];
        }
        int ans = 100 * m;
        for(int i = 0; i + m <= n; i++) {
            int sum = 0;
            for(int j = i; j < i + m; j++) {
                sum += a[j];
            }
            ans = min(ans, sum);
        }
        cout << ans;
        delete[] a;
        return 0;
    }
 
    int P2911::main(istream &cin, ostream &cout) {
        int s1;
        int s2;
        int s3;
        cin >> s1 >> s2 >> s3;
        const int n = s1 + s2 + s3 + 1;
        auto *sum   = new int[n];
        memset(sum, 0, n * sizeof(int));
        for(int i = 1; i <= s1; i++) {
            for(int j = 1; j <= s2; j++) {
                for(int k = 1; k <= s3; k++) {
                    sum[i + j + k]++;
                }
            }
        }
        int maximum = 0;
        int ans     = 0;
        for(int i = 3; i < n; i++) {
            if(maximum < sum[i]) {
                maximum = sum[i];
                ans     = i;
            }
        }
        cout << ans;
        delete[] sum;
        return 0;
    }
 
    int P1161::main(istream &cin, ostream &cout) {
        int n;
        auto *lamp = new bool[2000001];
        memset(lamp, 0, 2000001 * sizeof(bool));
        cin >> n;
        for(int i = 0; i < n; i++) {
            double a;
            int t;
            cin >> a >> t;
            for(int j = 1; j <= t; j++) {
                const int at = a * j;
                lamp[at]     = !lamp[at];
            }
        }
        for(int i = 0; i < 2000001; i++) {
            if(lamp[i]) {
                cout << i;
                break;
            }
        }
        delete[] lamp;
        return 0;
    }
 
    int P5731::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int square[9][9] = {};
        int dir          = 0;
        int current_x    = 0;
        int current_y    = 0;
        for(int i = 1; i <= n * n; i++) {
            square[current_x][current_y] = i;
            auto [next_x, next_y]        = move_forward(dir, current_x, current_y);
            if(next_x < 0 || next_x >= n || next_y < 0 || next_y >= n || square[next_x][next_y] != 0) {
                dir = (dir + 1) % 4;
            }
            const auto next = move_forward(dir, current_x, current_y);
            current_x       = next.first;
            current_y       = next.second;
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cout << setw(3) << right << setfill(' ') << square[i][j];
            }
            cout << endl;
        }
        return 0;
    }
 
    pair<int, int> P5731::move_forward(int dir, int current_x, int current_y) {
        int next_x = current_x;
        int next_y = current_y;
        switch(dir) {
            case 0:
                next_y++;
                break;
            case 1:
                next_x++;
                break;
            case 2:
                next_y--;
                break;
            case 3:
                next_x--;
                break;
        }
        return make_pair(next_x, next_y);
    }
 
    int P5732::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        auto *triangle = new int *[n];
        for(int i = 0; i < n; i++) {
            triangle[i] = new int[i + 1];
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    triangle[i][j] = 1;
                } else {
                    triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
                }
                cout << triangle[i][j] << " ";
            }
            cout << endl;
        }
        for(int i = 0; i < n; i++) {
            delete[] triangle[i];
        }
        delete[] triangle;
        return 0;
    }
 
    int P1789::main(istream &cin, ostream &cout) {
        int n;
        int m;
        int k;
        cin >> n >> m >> k;
        bool space[101][101] = {};
        memset(space, 0, sizeof space);
        for(int i = 0; i < m; i++) {
            int x;
            int y;
            cin >> x >> y;
            pair<int, int> lights[13] = {
                    make_pair(x - 2, y),
                    make_pair(x - 1, y - 1),
                    make_pair(x - 1, y),
                    make_pair(x - 1, y + 1),
                    make_pair(x, y - 2),
                    make_pair(x, y - 1),
                    make_pair(x, y),
                    make_pair(x, y + 1),
                    make_pair(x, y + 2),
                    make_pair(x + 1, y - 1),
                    make_pair(x + 1, y),
                    make_pair(x + 1, y + 1),
                    make_pair(x + 2, y),
            };
            for(auto [light_x, light_y]: lights) {
                if(0 < light_x && light_x <= n && 0 < light_y && light_y <= n) {
                    space[light_x][light_y] = true;
                }
            }
        }
        for(int i = 0; i < k; i++) {
            int o;
            int p;
            cin >> o >> p;
            for(int light_x = o - 2; light_x <= o + 2; light_x++) {
                for(int light_y = p - 2; light_y <= p + 2; light_y++) {
                    if(0 < light_x && light_x <= n && 0 < light_y && light_y <= n) {
                        space[light_x][light_y] = true;
                    }
                }
            }
        }
        int ans = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(!space[i][j]) {
                    ans++;
                }
            }
        }
        cout << ans;
        return 0;
    }
 
    int P1319::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        bool zero = false;
        int count = 0;
        for(int i = 0; i < n * n; i++) {
            while(count == 0) {
                cin >> count;
                zero = !zero;
            }
            if(zero) {
                cout << 0;
            } else {
                cout << 1;
            }
            count--;
            if((i + 1) % n == 0) {
                cout << endl;
            }
        }
        return 0;
    }
 
    int P1320::main(istream &cin, ostream &cout) {
        char ch;
        int current = 0;
        int count   = 0;
        vector<int> ans;
        int n = 0;
        while(cin >> ch) {
            if(isdigit(ch) == 0) {
                continue;
            }
            n++;
            if(ch - '0' == current) {
                count++;
            } else {
                ans.push_back(count);
                current = (current + 1) % 2;
                count   = 1;
            }
        }
        ans.push_back(count);
        cout << static_cast<int>(sqrt(n)) << " ";
        for(const auto i: ans) {
            cout << i << " ";
        }
        return 0;
    }
 
    int P1205::main(istream &cin, ostream &cout) {
        int ans = -1;
        int n;
        cin >> n;
        auto *start = new char *[n];
        auto *end   = new char *[n];
        for(int i = 0; i < n; i++) {
            start[i] = new char[n];
            for(int j = 0; j < n; j++) {
                cin >> start[i][j];
            }
        }
        for(int i = 0; i < n; i++) {
            end[i] = new char[n];
            for(int j = 0; j < n; j++) {
                cin >> end[i][j];
            }
        }
        auto *const r90   = rorate90(n, start);
        auto *const r180  = rorate180(n, start);
        auto *const r270  = rorate270(n, start);
        auto *const r     = reflect(n, start);
        auto *const rr90  = reflect(n, r90);
        auto *const rr180 = reflect(n, r180);
        auto *const rr270 = reflect(n, r270);
        if(equal(n, r90, end)) {
            ans = 1;
        } else if(equal(n, r180, end)) {
            ans = 2;
        } else if(equal(n, r270, end)) {
            ans = 3;
        } else if(equal(n, r, end)) {
            ans = 4;
        } else if(equal(n, rr90, end)) {
            ans = 5;
        } else if(equal(n, rr180, end)) {
            ans = 5;
        } else if(equal(n, rr270, end)) {
            ans = 5;
        } else if(equal(n, start, end)) {
            ans = 6;
        } else {
            ans = 7;
        }
        cout << ans;
        for(int i = 0; i < n; i++) {
            delete[] start[i];
            delete[] end[i];
            delete[] r90[i];
            delete[] r180[i];
            delete[] r270[i];
            delete[] r[i];
            delete[] rr90[i];
            delete[] rr180[i];
            delete[] rr270[i];
        }
        delete[] start;
        delete[] end;
        delete[] r90;
        delete[] r180;
        delete[] r270;
        delete[] r;
        delete[] rr90;
        delete[] rr180;
        delete[] rr270;
        return 0;
    }
 
    char **P1205::rorate90(int n, char **start) {
        auto *const cpy = new char *[n];
        for(int i = 0; i < n; i++) {
            cpy[i] = new char[n];
        }
        for(int i1 = 0, j2 = 0; i1 < n && j2 < n; i1++, j2++) {
            for(int j1 = 0, i2 = n - 1; j1 < n && i2 >= 0; j1++, i2--) {
                cpy[i1][j1] = start[i2][j2];
            }
        }
        return cpy;
    }
 
    char **P1205::rorate180(int n, char **start) {
        auto *const cpy = new char *[n];
        for(int i = 0; i < n; i++) {
            cpy[i] = new char[n];
        }
        for(int i1 = 0, i2 = n - 1; i1 < n && i2 >= 0; i1++, i2--) {
            for(int j1 = 0, j2 = n - 1; j1 < n && j2 >= 0; j1++, j2--) {
                cpy[i1][j1] = start[i2][j2];
            }
        }
        return cpy;
    }
 
    char **P1205::rorate270(int n, char **start) {
        auto *const cpy = new char *[n];
        for(int i = 0; i < n; i++) {
            cpy[i] = new char[n];
        }
        for(int i1 = 0, j2 = n - 1; i1 < n && j2 >= 0; i1++, j2--) {
            for(int j1 = 0, i2 = 0; j1 < n && i2 < n; j1++, i2++) {
                cpy[i1][j1] = start[i2][j2];
            }
        }
        return cpy;
    }
 
    char **P1205::reflect(int n, char **start) {
        auto *const cpy = new char *[n];
        for(int i = 0; i < n; i++) {
            cpy[i] = new char[n];
        }
        for(int i1 = 0, i2 = 0; i1 < n && i2 < n; i1++, i2++) {
            for(int j1 = 0, j2 = n - 1; j1 < n && j2 >= 0; j1++, j2--) {
                cpy[i1][j1] = start[i2][j2];
            }
        }
        return cpy;
    }
 
    bool P1205::equal(int n, char **start, char **end) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(start[i][j] != end[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
 
    int P5733::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        for(const char ch: str) {
            if(islower(ch) != 0) {
                cout << static_cast<char>(toupper(ch));
            } else {
                cout << ch;
            }
        }
        return 0;
    }
 
    int P1914::main(istream &cin, ostream &cout) {
        string str;
        int n;
        cin >> n >> str;
        for(const char ch: str) {
            cout << static_cast<char>((ch - 'a' + n) % 26 + 'a');
        }
        return 0;
    }
 
    int P1125::main(istream &cin, ostream &cout) {
        string str;
        cin >> str;
        int freq[26] = {};
        int maxn     = 0;
        int minn     = 100;
        for(const char ch: str) {
            freq[ch - 'a']++;
        }
        for(int i = 0; i < 26; i++) {
            if(freq[i] > 0) {
                maxn = max(maxn, freq[i]);
                minn = min(minn, freq[i]);
            }
        }
        bool is_prime = true;
        for(int i = 2; i <= sqrt(maxn - minn); i++) {
            if((maxn - minn) % i == 0) {
                is_prime = false;
                break;
            }
        }
        if(maxn - minn < 2) {
            is_prime = false;
        }
        if(is_prime) {
            cout << "Lucky Word" << endl
                 << maxn - minn;
        } else {
            cout << "No Answer" << endl
                 << 0;
            return 0;
        }
        return 0;
    }
 
    int P1957::main(istream &cin, ostream &cout) {
        int i;
        cin >> i;
        char op;
        for(int _ = 0; _ < i; _++) {
            int num1;
            int num2;
            string pos1;
            cin >> pos1;
            if(isalpha(pos1[0]) != 0) {
                op = pos1[0];
                cin >> num1 >> num2;
            } else {
                auto ss = stringstream();
                ss << pos1;
                ss >> num1;
                cin >> num2;
            }
            auto oss = ostringstream();
            switch(op) {
                case 'a':
                    oss << num1 << '+' << num2 << '=' << num1 + num2;
                    break;
                case 'b':
                    oss << num1 << '-' << num2 << '=' << num1 - num2;
                    break;
                case 'c':
                    oss << num1 << '*' << num2 << '=' << num1 * num2;
                    break;
                default:
                    cerr << "Unknown Op:\t" << op;
                    return 1;
            }
            string str = oss.str();
            cout << str << endl
                 << str.length() << endl;
        }
        return 0;
    }
 
    int P5015::main(istream &cin, ostream &cout) {
        int ans = 0;
        char ch;
        while((ch = cin.get()) != EOF) {
            if(isalnum(ch) != 0) {
                ans++;
            }
        }
        cout << ans;
        return 0;
    }
 
    int P5734::main(istream &cin, ostream &cout) {
        string doc;
        int n;
        cin >> n >> doc;
        int op;
        for(int i = 0; i < n; i++) {
            cin >> op;
            switch(op) {
                case 1: {
                    string str;
                    cin >> str;
                    doc.insert(doc.end(), str.begin(), str.end());
                    cout << doc << endl;
                    break;
                }
                case 2: {
                    int a;
                    int b;
                    cin >> a >> b;
                    doc = doc.substr(a, b);
                    cout << doc << endl;
                    break;
                }
                case 3: {
                    int a;
                    string str;
                    cin >> a >> str;
                    doc.insert(doc.begin() + a, str.begin(), str.end());
                    cout << doc << endl;
                    break;
                }
                case 4: {
                    string str;
                    cin >> str;
                    const auto ans = doc.find(str);
                    if(ans == string::npos) {
                        cout << -1 << endl;
                    } else {
                        cout << ans << endl;
                    }
                    break;
                }
            }
        }
        return 0;
    }
 
    int P1308::main(istream &cin, ostream &cout) {
        int sum       = 0;
        int pos       = -1;
        auto *target  = new char[11];
        auto *article = new char[1000001];
        cin.getline(target, 11);
        for(int i = 0; i < strlen(target); i++) {
            target[i] = tolower(target[i]);
        }
        cin.getline(article, 1000001);
 
        for(int i = 0; i + strlen(target) <= strlen(article); i++) {
            if(!((i == 0 || article[i - 1] == ' ') && (i + strlen(target) == strlen(article) || article[i + strlen(target)] == ' '))) {
                continue;
            }
            bool ok = true;
            for(int j = 0; j < strlen(target); j++) {
                if(target[j] != tolower(article[i + j])) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                sum++;
                if(pos == -1) {
                    pos = i;
                }
            }
        }
        if(sum == 0) {
            cout << -1;
        } else {
            cout << sum << " " << pos;
        }
        delete[] target;
        delete[] article;
        return 0;
    }
 
    int P1765::main(istream &cin, ostream &cout) {
        int ans            = 0;
        const int nums[26] = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 4};
        char ch;
        while((ch = cin.get()) != EOF) {
            if(ch == ' ') {
                ans++;
            } else if(isalpha(ch) != 0) {
                ans += nums[ch - 'a'];
            }
        }
        cout << ans;
        return 0;
    }
 
    int P3741::main(istream &cin, ostream &cout) {
        int n;
        bool flag = false;
        int ans   = 0;
        cin >> n;
        string str;
        cin >> str;
        for(int i = 0; i < n - 1; i++) {
            if(str[i] == 'V') {
                if(str[i + 1] == 'K') {
                    ans++;
                } else if(i + 2 == n || i + 2 < n && str[i + 2] != 'K') {
                    flag = true;
                }
            } else if(str[i + 1] == 'K' && (i - 1 >= 0 && str[i - 1] != 'V' || i == 0)) {
                flag = true;
            }
        }
        if(flag) {
            ans++;
        }
        cout << ans;
        return 0;
    }
 
    int P1321::main(istream &cin, ostream &cout) {
        string str;
        string boygirl[] = {"boy", "girl"};
        cin >> str;
        for(auto word: boygirl) {
            int count = 0;
            for(int i = 0; i + word.length() - 1 < str.length(); i++) {
                for(int j = 0; j < word.length(); j++) {
                    if(word[j] == str[i + j]) {
                        count++;
                        break;
                    }
                }
            }
            cout << count << endl;
        }
        return 0;
    }
 
    int P1553::main(istream &cin, ostream &cout) {
        deque<char> dq[2];
        stringstream ss[2];
        int current = 0;
        int limit   = 1;
        char op     = 'N';
        char ch;
        while(cin >> ch) {
            if(isdigit(ch) != 0) {
                bool flag = false;
                dq[current].push_front(ch);
            } else {
                op = ch;
                current++;
            }
        }
        if(op == '.' || op == '/') {
            limit = 2;
        }
        for(int i = 0; i < limit; i++) {
            while(dq[i].size() > 1 && dq[i].front() == '0') {
                dq[i].pop_front();
            }
            if(op == '.' && i == 1) {
                while(dq[i].size() > 1 && dq[i].back() == '0') {
                    dq[i].pop_back();
                }
            }
            while(!dq[i].empty()) {
                ss[i] << dq[i].front();
                dq[i].pop_front();
            }
        }
        cout << ss[0].str();
        if(op != 'N') {
            cout << op;
            if(op != '%') {
                cout << ss[1].str();
            }
        }
        return 0;
    }
 
    int P1603::main(istream &cin, ostream &cout) {
        unordered_map<string, int> um;
        um["one"]       = 1;
        um["two"]       = 2;
        um["three"]     = 3;
        um["four"]      = 4;
        um["five"]      = 5;
        um["six"]       = 6;
        um["seven"]     = 7;
        um["eight"]     = 8;
        um["nine"]      = 9;
        um["ten"]       = 10;
        um["eleven"]    = 11;
        um["twelve"]    = 12;
        um["thirteen"]  = 13;
        um["fourteen"]  = 14;
        um["fifteen"]   = 15;
        um["sixteen"]   = 16;
        um["seventeen"] = 17;
        um["eighteen"]  = 18;
        um["nineteen"]  = 19;
        um["twenty"]    = 20;
        um["a"]         = 1;
        um["both"]      = 2;
        um["another"]   = 1;
        um["first"]     = 1;
        um["second"]    = 2;
        um["third"]     = 3;
        multiset<int> ms;
        string word;
        for(int i = 0; i < 6; i++) {
            cin >> word;
            if(um.contains(word)) {
                ms.insert(um[word] * um[word] % 100);
            }
        }
        if(ms.empty()) {
            cout << 0;
            return 0;
        }
        stringstream ss;
        for(const auto i: ms) {
            if(i < 10) {
                ss << '0';
            }
            ss << i;
        }
        unsigned long long ans;
        ss >> ans;
        cout << ans;
        return 0;
    }
 
    int P1200::main(istream &cin, ostream &cout) {
        string comet;
        string team;
        cin >> comet >> team;
        unsigned int comet_int = 1;
        unsigned int team_int  = 1;
        for(const char ch: comet) {
            comet_int *= ch - 'A' + 1;
            comet_int %= 47;
        }
        for(const char ch: team) {
            team_int *= ch - 'A' + 1;
            team_int %= 47;
        }
        cout << (comet_int == team_int ? "GO" : "STAY");
        return 0;
    }
 
    int P1597::main(istream &cin, ostream &cout) {
        int a = 0;
        int b = 0;
        int c = 0;
        while(true) {
            char var;
            int *p = nullptr;
            int val;
            char ref;
            if(!(cin >> var) || isalpha(var) == 0) {
                break;
            }
            switch(var) {
                case 'a':
                    p = &a;
                    break;
                case 'b':
                    p = &b;
                    break;
                case 'c':
                    p = &c;
                    break;
            }
            cin.get();
            cin.get();
            if(isdigit(cin.peek()) != 0) {
                cin >> val;
                *p = val;
            } else {
                cin >> ref;
                switch(ref) {
                    case 'a':
                        *p = a;
                        break;
                    case 'b':
                        *p = b;
                        break;
                    case 'c':
                        *p = c;
                        break;
                    default: break;
                }
            }
            cin.get();
        }
        cout << a << " " << b << " " << c;
        return 0;
    }
 
    int P1598::main(istream &cin, ostream &cout) {
        char ch;
        int count[26] = {};
        int maximum   = 0;
        while(cin >> ch) {
            if(isupper(ch) != 0) {
                count[ch - 'A']++;
                maximum = max(maximum, count[ch - 'A']);
            }
        }
        for(int i = maximum; i > 0; i--) {
            for(int j = 0; j < 26; j++) {
                if(count[j] >= i) {
                    cout << '*';
                } else {
                    cout << ' ';
                }
                cout << ' ';
            }
            cout << endl;
        }
        for(char ch = 'A'; ch <= 'Z'; ch++) {
            cout << ch << ' ';
        }
        return 0;
    }
 
    int P5735::main(istream &cin, ostream &cout) {
        double x1;
        double y1;
        double x2;
        double y2;
        double x3;
        double y3;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        const double d12 = sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
        const double d23 = sqrt(pow(x3 - x2, 2) + pow(y3 - y2, 2));
        const double d13 = sqrt(pow(x3 - x1, 2) + pow(y3 - y1, 2));
        cout << fixed << setprecision(2) << d12 + d23 + d13;
        return 0;
    }
 
    int P5736::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        bool notprime[100001];
        memset(notprime, 1, sizeof notprime);
        notprime[0] = false;
        notprime[1] = false;
        notprime[2] = true;
        for(unsigned int i = 2; i <= 50000; i++) {
            for(unsigned int j = 2; i * j <= 100000; j++) {
                notprime[i * j] = false;
            }
        }
        unsigned int num;
        for(int _ = 0; _ < n; _++) {
            cin >> num;
            if(notprime[num]) {
                cout << num << " ";
            }
        }
        return 0;
    }
 
    int P5737::main(istream &cin, ostream &cout) {
        int x;
        int y;
        cin >> x >> y;
        ostringstream oss;
        int sum = 0;
        for(int year = x; year <= y; year++) {
            if(year % 4 == 0 && year % 100 != 0 || year % 400 == 0) {
                oss << year << ' ';
                sum++;
            }
        }
        cout << sum << endl
             << oss.str();
        return 0;
    }
 
    int P5738::main(istream &cin, ostream &cout) {
        int n;
        int m;
        cin >> n >> m;
        double ans = 0;
        for(int i = 0; i < n; i++) {
            vector<int> vec(m);
            for(int j = 0; j < m; j++) {
                cin >> vec[j];
            }
            sort(vec.begin(), vec.end());
            ans = max(ans, static_cast<double>(accumulate(vec.begin() + 1, vec.end() - 1, 0)) / (m - 2));
        }
        cout << fixed << setprecision(2) << ans;
        return 0;
    }
 
    int P5739::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        unsigned int ans = 1;
        for(unsigned int i = 1; i <= n; i++) {
            ans *= i;
        }
        cout << ans;
        return 0;
    }
 
    int P5461::main(istream &cin, ostream &cout) {
        unsigned int n;
        cin >> n;
        n                  = 1 << n;
        auto *const matrix = new bool *[n];
        for(int i = 0; i < n; i++) {
            matrix[i] = new bool[n];
            memset(matrix[i], 1, n * sizeof(bool));
        }
        pardon(matrix, 0, 0, n);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                cout << matrix[i][j] << " ";
            }
            cout << endl;
            delete[] matrix[i];
        }
        delete[] matrix;
        return 0;
    }
 
    void P5461::pardon(bool **matrix, int x0, int y0, int n) {
        if(n == 2) {
            matrix[x0][y0] = false;
            return;
        }
        for(int i = 0; i < n / 2; i++) {
            for(int j = 0; j < n / 2; j++) {
                matrix[x0 + i][y0 + j] = false;
            }
        }
        pardon(matrix, x0, y0 + n / 2, n / 2);
        pardon(matrix, x0 + n / 2, y0, n / 2);
        pardon(matrix, x0 + n / 2, y0 + n / 2, n / 2);
    }
 
    int P5740::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        string max_name;
        int max_1   = 0;
        int max_2   = 0;
        int max_3   = 0;
        int max_sum = -1;
        for(int i = 0; i < n; i++) {
            string name;
            int grade1;
            int grade2;
            int grade3;
            cin >> name >> grade1 >> grade2 >> grade3;
            const int sum = grade1 + grade2 + grade3;
            if(max_sum < sum) {
                max_sum  = sum;
                max_name = name;
                max_1    = grade1;
                max_2    = grade2;
                max_3    = grade3;
            }
        }
        cout << max_name << ' ' << max_1 << ' ' << max_2 << ' ' << max_3;
        return 0;
    }
 
    int P5741::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        vector<pair<string, array<int, 3>>> vec(n);
        for(int i = 0; i < n; i++) {
            string name;
            array<int, 3> grade = {};
            cin >> name >> grade[0] >> grade[1] >> grade[2];
            vec[i] = make_pair(name, grade);
        }
        for(int i = 0; i + 1 < n; i++) {
            const int sum_i = vec[i].second[0] + vec[i].second[1] + vec[i].second[2];
            for(int j = i + 1; j < n; j++) {
                const int sum_j = vec[j].second[0] + vec[j].second[1] + vec[j].second[2];
                if(abs(sum_i - sum_j) <= 10) {
                    bool flag = true;
                    for(int k = 0; k < 3; k++) {
                        if(abs(vec[i].second[k] - vec[j].second[k]) > 5) {
                            flag = false;
                            break;
                        }
                    }
                    if(flag) {
                        cout << vec[i].first << ' ' << vec[j].first << endl;
                    }
                }
            }
        }
        return 0;
    }
 
    namespace P5742 {
        int P5742::main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            for(int i = 0; i < n; i++) {
                int number;
                int grade;
                int extra_grade;
                cin >> number;
                cin >> grade;
                cin >> extra_grade;
                auto s = Student(number, grade, extra_grade);
                cout << (s.excellent() ? "Excellent" : "Not excellent") << endl;
            }
            return 0;
        }
 
        bool Student::excellent() const { return sum > 140 && composite >= 80; }
    }// namespace P5742
 
    int P1304::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        set<int> primes;
        for(int i = 2; i <= n; i++) {
            primes.insert(i);
        }
        for(int i = 2; i <= n; i++) {
            for(int j = 2; i * j <= n; j++) {
                primes.erase(i * j);
            }
        }
        for(int i = 4; i <= n; i += 2) {
            for(auto prime = primes.begin(); *prime <= i / 2 && prime != primes.end(); ++prime) {
                if(primes.contains(i - *prime)) {
                    cout << i << '=' << *prime << '+' << i - *prime << endl;
                    break;
                }
            }
        }
        return 0;
    }
 
    int P2415::main(istream &cin, ostream &cout) {
        vector<int> vec;
        int num;
        while(cin >> num) {
            vec.push_back(num);
        }
        const int n                   = vec.size();
        const unsigned long long base = static_cast<unsigned long long>(1) << n - 1;
        unsigned long long sum        = 0;
        for(const auto num: vec) {
            sum += num * base;
        }
        cout << sum;
        return 0;
    }
 
    int P5743::main(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        int count = 1;
        for(int i = 0; i < n - 1; i++) {
            count++;
            count *= 2;
        }
        cout << count;
        return 0;
    }
 
    namespace P5744 {
        int P5744::main(istream &cin, ostream &cout) {
            int n;
            cin >> n;
            for(int i = 0; i < n; i++) {
                auto stu = Student();
                cin >> stu.name;
                cin >> stu.age;
                cin >> stu.grade;
                stu.train();
                cout << stu.name << ' ' << stu.age << ' ' << stu.grade << endl;
            }
            return 0;
        }
 
        void Student::train() {
            age++;
            grade = grade / 5 * 6;
            grade = min(grade, 600);
        }
    }// namespace P5744
}// namespace luogu