HW #9

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;


#define int long long
#define double long double
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
const int mod = 1e9 + 7; // 998244353


bool cmp(pair<pair<string , int> , int > a , pair<pair<string , int> , int> b){
    if(a.F.F != b.F.F)
        return a.F.F < b.F.F;
    return a.F.S > b.F.S;
}

signed main()
{
    _FastIO;
    /*
    // A
    int a , b;
    cin >> a >> b;
    if(a == 1 || b == 1)
        cout << 1;
    else
        cout << (a * b + 1) / 2 << '\n';
    */
    // B
    /*
    string s;
    cin >> s;
    map<char , int> cnt;
    for(char i : s)
        cnt[i]++;


    for(char i = 'a'; i <= 'z'; i++){
        if(!cnt[i]){
            cout << i << '\n';
            return 0;
        } // !cnt.count(i)
    }

    cout << "None" << '\n';
    */
    /*
    // C
    string a , b;
    cin >> a >> b;
    int n = a.size() , m = b.size();
    if(a == b)
        cout << "EQUAL\n";
    else if(n < m)
        cout << "LESS\n";
    else if(n > m)
        cout << "GREATER\n";
    else if(a < b)
        cout << "LESS\n";
    else
        cout << "GREATER\n";
    */
    /*
    // D
    int a , b;
    cin >> a >> b;
    if(a <= 0 && 0 <= b){
        cout << "Zero";
        return 0;
    } // a <= 0 <= b

    if(a > 0 && b > 0){
        cout << "Positive";
        return 0;
    }
    if(abs(a - b) % 2 == 0)
        cout << "Negative";
    else
        cout << "Positive";
    */
    /*
    // E
    int a , b , c , x;
    cin >> a >> b >> c >> x;
    int cnt = 0;
    for(int i = 0; i <= a; i++){ // 500
        for(int j = 0; j <= b; j++){ // 100
            int sum = i * 500 + j * 100;
            if(sum > x)
                continue;
            int qaliq = x - sum;
            if(qaliq % 50)
                continue;
            int k = qaliq / 50;
            if(k <= c)
                cnt++;
        }
    }
    cout << cnt << '\n';
    */
    /*
    /// F
    string s;
    cin >> s;
    int n = s.size();
    if(s[0] != 'A'){
        cout << "WA";
        return 0;
    }
    int c = 0;
    for(int i = 2; i <= n - 2; i++){
        c += s[i] == 'C';
    }
    if(c != 1){
        cout << "WA";
        return 0;
    }
    bool wa = 0;
    for(char i : s){
        if(i != 'A' && i != 'C'){
            if(!islower(i))
                wa = 1;
        }
    }
    if(wa){
        cout << "WA";
    }else{
        cout << "AC";
    }
    // AbCA
    */

    /*
    tokyo
    otoky
    yotok
    kyoto
    okyot

    */
    /*
    // G
    string s , t;
    cin >> s >> t;
    int n = s.size();
    s += s;
    string ans = "No";
    for(int i = 0; i < n; i++){
        s = s.back() + s;
        s.pop_back();
        if(s.substr(i , n) == t)
            ans = "Yes";
    }

    cout << ans << '\n';
    */
    /*
    // H
    int n;
    cin >> n;
    int f = 1;
    for(int i = 1; i <= n; i++){
        f *= i;
        f %= mod;
    }
    // (10 - 8) % 3 = ((10 % 3) - (8  % 3)) % mod = 1 - 2 = -1
    cout << f % mod;
    */

    // 1 <= T <= 1e5
    // 1 <= N <= 1e5

    // online queries
    // offline queries
    /*
    const int N = 1e5 + 5;
    int f[N];
    f[0] = 1;
    for(int i = 1; i <= 1e5; i++){
        f[i] = f[i - 1] * i % mod;
    }
    int t , n;
    vector<int> v;
    cin >> t;
    while(t--){
        cin >> n;
        cout << f[n];
    }
*//*
    int n;
    cin >> n;
    int ans = 1;
    bool overflow = 0 , zero = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        if(x == 0){
            zero = 1;
            continue;
        }
        if(ans > (int)1e18 / x){
            overflow = 1;
        }
        ans *= x;

    }
    if(zero)
        cout << 0;
    else if(overflow)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
    */
    /*
    // J
    int n;
    cin >> n;
    vector<pair<pair<string , int> , int> > v;
    for(int i = 1; i <= n; i++){
        string s;
        int score;
        cin >> s >> score;
        v.push_back({{s , score} , i});
    }
    sort(v.begin() , v.end() , cmp);
    for(auto i : v)
        cout << i.second << '\n';
    */
}