class Solution {
public:
    int numberOfSubstrings(string s)
    {
        // To store the count of valid substrings
        // Vector to store prefix sums of '1's

        // Compute prefix sums for the number of '1's
        // Initialize the first element based on the first character
        // Compute prefix sums for the rest of the array

        // Iterate over each possible starting index of the substring
        for ()
        {
            // Iterate over each possible ending index of the substring
            for ()
            {
                // Calculate the number of '1's and '0's in the current substring s[i..j]

                // CASE 1: Substring is not dominant
                if ()
                {
                    // Adjust the end pointer j to skip over non-dominant substrings
                }

                // CASE 2: Substring is exactly dominant
                else if ()
                {
                    // Count this substring as valid
                }
                // CASE 3: Substring is more dominant
                else if ()
                {
                    // Count this substring as valid
                    // Calculate how many more substrings are valid by skipping forward
                    // Determine the next position to skip to

                    // If skipping exceeds the string length, count all remaining substrings
                    if ()
                    {
                    }
                    else
                    {
                        // Otherwise, count substrings within bounds
                    }

                    // Update j to the next valid position
                }
            }
        }
        // Return the total count of valid substrings
    }
};

class Solution {
public:
    int numberOfSubstrings(string s)
    {
        int n = s.size(); // Length of the input string
        int res = 0; // To store the count of valid substrings
        vector<int> prefix(n, 0); // Vector to store prefix sums of '1's

        // Compute prefix sums for the number of '1's
        prefix[0] = (int)(s[0] - '0'); // Initialize the first element based on the first character
        for (int i = 1; i < n; i++)
        {
            prefix[i] = prefix[i - 1] + (int)(s[i] - '0'); // Compute prefix sums for the rest of the array
        }

        // Iterate over each possible starting index of the substring
        for (int i = 0; i < n; i++)
        {
            // Iterate over each possible ending index of the substring
            for (int j = i; j < n; j++)
            {
                // Calculate the number of '1's and '0's in the current substring s[i..j]
                int ones = prefix[j] - (i == 0 ? 0 : prefix[i - 1]);
                int zeros = (j - i + 1) - ones;

                // CASE 1: Substring is not dominant
                if (zeros * zeros > ones)
                {
                    // Adjust the end pointer j to skip over non-dominant substrings
                    j += (zeros * zeros - ones - 1);
                }
                // CASE 2: Substring is exactly dominant
                else if (zeros * zeros == ones)
                {
                    ++res; // Count this substring as valid
                }
                // CASE 3: Substring is more dominant
                else if (zeros * zeros < ones)
                {
                    ++res; // Count this substring as valid
                    // Calculate how many more substrings are valid by skipping forward
                    int diff = (int) sqrt(ones) - zeros;
                    int nextj = j + diff; // Determine the next position to skip to

                    // If skipping exceeds the string length, count all remaining substrings
                    if (nextj >= n)
                    {
                        res += (n - j - 1);
                    }
                    else
                    {
                        res += diff; // Otherwise, count substrings within bounds
                    }
                    // Update j to the next valid position
                    j = nextj;
                }
            }
        }
        return res; // Return the total count of valid substrings
    }
};

class Solution {
public:
    int nonSpecialCount(int l, int r)
    {
        // Calculate the upper limit for prime number checking (sqrt(r))

        // Vector to mark prime numbers using the Sieve of Eratosthenes
        // 0 and 1 are not prime numbers

        // Sieve of Eratosthenes to mark non-prime numbers
        for ()
        {
            if ()
            {
                for ()
                {
                    // Mark multiples of i as non-prime
                }
            }
        }

        // Count the number of squares of primes within the range [l, r]
        for ()
        {
            if ()
            {
                // Calculate the square of the prime number
                if ()
                {
                    // Increment count if the square is within the range
                }
            }
        }

        // Calculate the total number of numbers in the range [l, r]

        // Return the number of non-special numbers
    }
};

class Solution {
public:
    int nonSpecialCount(int l, int r)
    {
        int limit = (int)(sqrt(r));

        vector<bool> isPrime(limit + 1, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= limit; i++)
        {
            if (isPrime[i])
            {
                for (int j = i * i; j <= limit; j += i)
                {
                    isPrime[j] = false;
                }
            }
        }

        int cnt = 0;
        for (int i = 2; i <= limit; i++)
        {
            if (isPrime[i])
            {
                int square = i * i;
                if (l <= square && square <= r)
                {
                    cnt++;
                }
            }
        }

        int total = r - l + 1;

        return total - cnt;
    }
};

class Solution {
public:
    bool canAliceWin(vector<int>& nums)
    {
        int a = 0;
        int b = 0;
        for (auto num : nums)
        {
            int carry = num / 10;
            if (0 < carry && carry < 10) a += num;
            else b += num;
        }
        return a == b ? false : true;
    }
};

class Solution {
public:
    int maxOperations(string s)
    {
        // Initialize the result variable to store the maximum number of operations.
        // Initialize the counter to count consecutive '1's.

        // Iterate over each character in the string.
        for ()
        {
            // If the current character is '1', increment the counter.
            // If the current character is '0' and the previous character was '1',
            // add the count of '1's to the result.
        }
        // Return the result which is the maximum number of operations.
    }
};

class Solution {
public:
    int maxOperations(string s)
    {
        int res = 0, cnt = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == '1') ++cnt;
            else if (i > 0 && s[i - 1] == '1') res += cnt;
        }
        return res;
    }
};

class Solution {
public:
    bool doesAliceWin(string s)
    {
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') return true;
        }
        return false;
    }
};

class Solution {
public:
    int minChanges(int n, int k)
    {
        if (n == k) return 0;

        string n1 = bitset<32>(n).to_string();
        string k1 = bitset<32>(k).to_string();

        int cnt = 0;
        for (int i = 0; i < 32; i++)
        {
            if (n1[i] != k1[i] && n1[i] == '0') return -1;
            else if (n1[i] != k1[i] && n1[i] == '1') ++cnt;
        }
        return cnt;
    }
};

class Solution {
public:
    int minimumLength(string s)
    {
        // Initialize n to the size of the input string s
        // Initialize a frequency vector for the 26 lowercase English letters

        // Iterate over each character in the string
        for ()
        {
            // Increment the frequency count for the current character
            // If the frequency of the current character reaches 3
                // Reduce the frequency count by 2 (essentially removing 2 instances)
                // Decrease the length of the string by 2
        }
        // Return the adjusted length of the string
    }
};

class Solution {
public:
    int minimumLength(string s)
    {
        int n = s.size();
        vector<int> freq(26);
        for (char c : s)
        {
            ++freq[c - 'a'];
            if (freq[c - 'a'] == 3)
            {
                freq[c - 'a'] -= 2;
                n -= 2;
            }
        }
        return n;
    }
};

class Solution {
public:
    string losingPlayer(int x, int y)
    {
        int cnt = 0;
        while (x > 0 && y > 3)
        {
            x -= 1;
            y -= 4;
            ++cnt;
        }
        return cnt % 2 == 1 ? "Alice" : "Bob";
    }
};

class Solution {
public:
    int minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        // Sorting the cuts in descending order to start from the largest piece

        // Counters for horizontal and vertical pieces
        // Variable to accumulate the minimum cost

        // Loop until we have processed all possible cuts
        while ()
        {
            // Compare the current largest horizontal cut with the current largest vertical cut
            if ()
            {
                // Add the cost of the horizontal cut multiplied by the number of vertical pieces + 1
            }
            else
            {
                // Add the cost of the vertical cut multiplied by the number of horizontal pieces + 1
            }
        }

        // If there are remaining horizontal cuts, add their costs
        while ()
        {

        }

        // If there are remaining vertical cuts, add their costs
        while ()
        {

        }

        // Return the accumulated minimum cost
    }
};

#define ll long long
class Solution {
public:
    long long minimumCost(int m, int n, vector<int>& horizontalCut, vector<int>& verticalCut)
    {
        // 因為會越切越多塊，所以 cost 要由大往小排
        sort(horizontalCut.begin(), horizontalCut.end(), greater<int>());
        sort(verticalCut.begin(), verticalCut.end(), greater<int>());

        int hPieces = 0, vPieces = 0;
        ll minCost = 0;

        while (hPieces < m - 1 && vPieces < n - 1)
        {
            if (horizontalCut[hPieces] > verticalCut[vPieces])
            {
                minCost += horizontalCut[hPieces++] * (vPieces + 1);
            }
            else
            {
                minCost += verticalCut[vPieces++] * (hPieces + 1);
            }
        }

        while (hPieces < m - 1)
        {
            minCost += horizontalCut[hPieces++] * (vPieces + 1);
        }

        while (vPieces < n - 1)
        {
            minCost += verticalCut[vPieces++] * (hPieces + 1);
        }
        return minCost;
    }
};