class Solution {
public:
    bool squareIsWhite(string coordinates) {
        return (coordinates[0] + coordinates[1]) % 2;
    }
};

class Solution {
    static constexpr int mod = 1e9 + 7;
public:
    int knightDialer(int n) {
        vector<vector<int>> moves = {
            {4, 6},                   //   0
            {6, 8},  {7, 9},  {4, 8},   // 1 2 3
            {3, 9, 0}, {}, {1, 7, 0}, // 4 5 6
            {2, 6},  {1, 3},  {2, 4}    // 7 8 9
        };
        vector<vector<int>> d{vector<int>(10, 0), vector<int>(10, 1)};
        for (int i = 2; i <= n; i++) {
            int x = i & 1;
            for (int j = 0; j < 10; j++) {
                d[x][j] = 0;
                for (int k : moves[j]) {
                    d[x][j] = (d[x][j] + d[x ^ 1][k]) % mod;
                }
            }
        }
        int res = 0;
        for (auto x : d[n % 2]) {
            res = (res + x) % mod;
        }
        return res;
    }
};

class Solution {
public:
    int semiOrderedPermutation(vector<int>& nums) {
        auto [first, last] = minmax_element(nums.begin(), nums.end());
        return first + nums.size() - 1 - last - (last < first);
    }
};

class Solution {
public:
        using ll = long long;
    long long maxSpending(vector<vector<int>>& values) {
        priority_queue<array<ll, 2>, std::vector<array<ll, 2>>, 
                                  greater<array<ll, 2>>>q;
        ll m = values.size(), n = values[0].size();
        vector<ll>idxs(m, n - 1);
        for(ll i = 0; i < m; i++){
            q.push({values[i][idxs[i]], i});
        }
        ll ans = 0, d = 1;
        while(!q.empty()){
            auto [value, i] = q.top();
            ans += d * value;
            d++, q.pop() , idxs[i]--;
            if(idxs[i] >= 0){ q.push({values[i][idxs[i]], i}); }
        }
        return ans;
    }
};

class Solution {
public:
    vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
        if(multiplier == 1){ return nums; }
        int len  = nums.size();
        vector<int>h(len);
        iota(h.begin(), h.end(), 0);
        auto cmp = [&nums](int a, int b){
            return nums[a] > nums[b] || (nums[a] == nums[b] && a > b);
        };
        for (auto _{k}; _--;) {
            make_heap(h.begin(), h.end(), cmp);
            pop_heap(h.begin(), h.end(), cmp);
            nums[h[len - 1]] *= multiplier;
        }
        return nums;
    }
};