/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        helper(root, result);
        return result;
    }

    void helper(TreeNode* root, vector<int>& result) {
        if (root != nullptr) {
            helper(root->left, result);
            result.push_back(root->val);
            helper(root->right, result);
        }
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        helper(root, result);
        return result;
    }

    void helper(TreeNode* root, vector<int>& result) {
        if (root != nullptr) {
            helper(root->left, result);
            result.push_back(root->val);
            helper(root->right, result);
        }
    }
};

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>> result(col, vector<int>(row, 0));
        
        for (int i = 0; i < col; ++i) {
            for (int j = 0; j < row; ++j) {
                result[i][j] = matrix[j][i];
            }
        }
        
        return result;
    }
};

class Solution {
public:
    string tree2str(TreeNode* root) {
        string str = "";
         check(root, str);
         return str;
    }
    void check(TreeNode* root, string &str) {
        if (root == NULL) {
            return;
        }
        str += to_string(root->val);
        if (root->left || root->right) {
            str += '(';
            check(root->left, str);
            str += ')';
        }
        if (root->right) {
            str += '(';
            check(root->right, str);
            str += ')';
        }
        
    }
    
};

class Solution {
public:
    string largestOddNumber(string num) {
        size_t length {num.size()};
        for (int i = length - 1; i >= 0; --i) {
            if ((num[i] - '0') % 2 != 0) {
                return num.substr(0, i + 1);
            }
        }
        return "";
    }
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow {head};
        ListNode* fast {head};
        ListNode* next;
        ListNode* prev {new ListNode()};

        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next; 

            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
    
        if (fast) {
            slow = slow->next;
        }
        head = prev;

        while (slow) {
            if (head->val != slow->val) {
                return false;
            }
            head = head->next;
            slow = slow->next;
        }
        return true;
    }
};

class Solution {
public:
    int totalMoney(int n) {
        int ans {0};
        int monday {1};
        
        while (n > 0) {
            for (int day {0}; day < min(n, 7); ++day) {
                ans += monday + day;
            }
            n -= 7;
            ++monday;
        }
        
        return ans;
    }
};

class Solution {
public:
    int numberOfMatches(int n) {
        int ans = 0;
        while (n > 1) {
            if (n % 2 == 0) {
                int matches {n / 2};
                ans += matches;
                n = matches;
            } else {
                int matches {(n - 1) / 2};
                ans += matches;
                n = matches + 1;
            }
        }
        
        return ans;
    }
};

class Solution {
public:
    string largestGoodInteger(string num) {
        int cur {-1};
        int max {-1};
        int count {0};
        for (const char& ch : num) {
            int i {ch - '0'};
            if (i == cur) {
                ++count;
            } else {
                cur = i;
                count = 1; 
            }
            if (count == 3) {
                max = std::max(i, max);
            }
        }
        if (max == -1) {
            return "";
        }
        std::string ans {std::to_string(max)};
        return ans + ans + ans;
    }
};

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int ans = 0;
        for (int i = 0; i < points.size() - 1; i++) {
            int currX = points[i][0];
            int currY = points[i][1];
            int targetX = points[i + 1][0];
            int targetY = points[i + 1][1];
            ans += max(abs(targetX - currX), abs(targetY - currY));
        }
        
        return ans;
    }
};

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        std::vector<int> count {};
        int ans {};
        count.resize(26);
        for (const char& ch : chars) {
            ++count[ch - 'a'];
        }
        for (const string& word : words) {
            std::vector<int> wordCount {};
            wordCount.resize(26);
            bool failure {false};
            for (const char& ch : word) {
                int i {ch - 'a'};
                int cur {++wordCount[i]};
                if (cur > count[i]) {
                    failure = true;
                    break;
                }
            }
            if (!failure) {
                ans += word.length();
            }
        }
        return ans;
    }
};

class Solution {
public:
    bool arrayStringsAreEqual(vector<string>& word1, vector<string>& word2) {
        string s1 = "";
        string s2 = "";

        for(const string& s : word1) {
            s1 += s;
        }
        for(const string& s : word2) {
            s2 += s;
        }
        return s1==s2;
    }
};

class Solution {
public:
    int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }
        
        int k = 0;
        int curr = 1;
        while (curr * 2 <= n) {
            curr *= 2;
            k++;
        }
        
        return (1 << (k + 1)) - 1 - minimumOneBitOperations(n ^ curr);
    }
};

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans {};
        while (n) {
            if (n & 1) {
                ++ans;
            }
            n >>= 1;
        }
        return ans;
    }
};

class Solution {
public:
    // Store 1000000007 in a variable for convenience
    const int MOD = 1e9 + 7;
    
    // Count the number of ways to divide from "index" to the last index
    // with "seats" number of "S" in the current section
    int count(int index, int seats, string& corridor, int cache[][3]) {
        // If we have reached the end of the corridor, then
        // the current section is valid only if "seats" is 2
        if (index == corridor.length()) {
            return seats == 2 ? 1 : 0;
        }

        // If we have already computed the result of this sub-problem,
        // then return the cached result
        if (cache[index][seats] != -1) {
            return cache[index][seats];
        }

        // Result of the sub-problem
        int result = 0;

        // If the current section has exactly 2 "S"
        if (seats == 2) {
            // If the current element is "S", then we have to close the
            // section and start a new section from this index. Next index
            // will have one "S" in the current section
            if (corridor[index] == 'S') {
                result = count(index + 1, 1, corridor, cache);
            } else {
                // If the current element is "P", then we have two options
                // 1. Close the section and start a new section from this index
                // 2. Keep growing the section
                result = (count(index + 1, 0, corridor, cache) + count(index + 1, 2, corridor, cache)) % MOD;  
            }
        } else {
            // Keep growing the section. Increment "seats" if present
            // element is "S"
            if (corridor[index] == 'S') {
                result = count(index + 1, seats + 1, corridor, cache);
            } else {
                result = count(index + 1, seats, corridor, cache);
            }
        }

        // Memoize the result, and return it
        cache[index][seats] = result;
        return cache[index][seats];
    }

    int numberOfWays(string corridor) {
        // Cache the result of each sub-problem
        int cache[corridor.length()][3];
        memset(cache, -1, sizeof(cache));

        // Call the count function
        return count(0, 0, corridor, cache);
    }
};

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int ans = 0;
        
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (matrix[row][col] != 0 && row > 0) {
                    matrix[row][col] += matrix[row - 1][col];
                }
            }
            
            vector<int> currRow = matrix[row];
            sort(currRow.begin(), currRow.end(), greater());
            for (int i = 0; i < n; i++) {
                ans = max(ans, currRow[i] * (i + 1));
            }
        }
        
        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> memo;
    int n;
    int MOD = 1e9 + 7;
    vector<vector<int>> jumps = {
        {4, 6},
        {6, 8},
        {7, 9},
        {4, 8},
        {3, 9, 0},
        {},
        {1, 7, 0},
        {2, 6},
        {1, 3},
        {2, 4}
    };
    
    int dp(int remain, int square) {
        if (remain == 0) {
            return 1;
        }
        
        if (memo[remain][square] != 0) {
            return memo[remain][square];
        }
        
        int ans = 0;
        for (int nextSquare : jumps[square]) {
            ans = (ans + dp(remain - 1, nextSquare)) % MOD;
        }
        
        memo[remain][square] = ans;
        return ans;
    }
    
    int knightDialer(int n) {
        this->n = n;
        memo = vector(n + 1, vector(10, 0));
        int ans = 0;
        for (int square = 0; square < 10; square++) {
            ans = (ans + dp(n - 1, square)) % MOD;
        }
        
        return ans;
    }
};

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        
        int leftSum = 0;
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int rightSum = totalSum - leftSum - nums[i];
            
            int leftCount = i;
            int rightCount = n - 1 - i;
            
            int leftTotal = leftCount * nums[i] - leftSum;
            int rightTotal = rightSum - rightCount * nums[i];
            
            ans.push_back(leftTotal + rightTotal);
            leftSum += nums[i];
        }
        
        return ans;
    }
};

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix = {nums[0]};
        for (int i = 1; i < n; i++) {
            prefix.push_back(prefix[i - 1] + nums[i]);
        }
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            int leftSum = prefix[i] - nums[i];
            int rightSum = prefix[n - 1] - prefix[i];
            
            int leftCount = i;
            int rightCount = n - 1 - i;
            
            int leftTotal = leftCount * nums[i] - leftSum;
            int rightTotal = rightSum - rightCount * nums[i];
            
            ans.push_back(leftTotal + rightTotal);
        }
        return ans;
    }
};

class Solution {
public:
    std::vector<bool> kidsWithCandies(std::vector<int>& candies, int extraCandies) {
        size_t length {candies.size()};        
        std::vector<bool> ans {};
        ans.resize(length);
        const int maxCandy {*std::max_element(candies.begin(), candies.end())};
        for (size_t i = 0; i < length; ++i) {
            ans[i] = (candies[i] + extraCandies) >= maxCandy;
        }
        return ans;
    }
};

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 == str2 + str1) {
            return str1.substr(0, std::gcd(str1.size(), str2.size()));
        }
        return "";
    }
};

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1) {
            return "";
        }
        unsigned long gcdLength {std::gcd(str1.size(), str2.size())};
        return str1.substr(0, gcdLength);
    }
};

class Solution {
public:
    bool valid(string str1, string str2, size_t k) {
        size_t len1 {str1.size()}, len2 {str2.size()};
        if (len1 % k != 0 || len2 % k != 0) {
            return false;
        }
        string base = str1.substr(0, k);
        size_t n1 {len1 / k}, n2 {len2 / k};
        if (n1 == n2) {
            return str1 == str2 && joinWords(base, n1) == str1;
        }
        return str1 == joinWords(base, n1) && str2 == joinWords(base, n2);
    }

    string joinWords(string str, size_t k) {
        string ans = "";
        for (size_t i = 0; i < k; ++i) {
            ans += str;
        }
        return ans;
    }
    
    
    string gcdOfStrings(string str1, string str2) {
        for (size_t i = min(str1.size(), str2.size()); i > 0; --i) {
            if (valid(str1, str2, i)) {
                return str1.substr(0, i);
            }
        }
        return "";
    }
};

class Solution {
public:
    int maxCoins(vector<int>& piles) {
        std::sort(piles.begin(), piles.end());
        size_t length {piles.size()};
        size_t picks {length / 3};
        int count {};
        for (size_t i {length - 2}; picks > 0; i -= 2, --picks) {
            count += piles[i];
        }
        return count;
    }
};

class Solution {
public:
    bool check(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        int diff = arr[1] - arr[0];
        
        for (int i = 2; i < arr.size(); i++) {
            if (arr[i] - arr[i - 1] != diff) {
                return false;
            }
        }
        
        return true;
    }
    
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {
        vector<bool> ans;
        for (int i = 0; i < l.size(); i++) {
            vector<int> arr(begin(nums) + l[i], begin(nums) + r[i] + 1);
            ans.push_back(check(arr));
        }
        
        return ans;
    }
};

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        unordered_map<int, vector<int>> groups;
        for (int row = nums.size() - 1; row >= 0; row--) {
            for (int col = 0; col < nums[row].size(); col++) {
                int diagonal = row + col;
                groups[diagonal].push_back(nums[row][col]);
            }
        }
        
        vector<int> ans;
        int curr = 0;
        
        while (groups.find(curr) != groups.end()) {
            for (int num : groups[curr]) {
                ans.push_back(num);
            }
            
            curr++;
        }
        
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> ans;
        dfs(*root, ans, "");
        return ans;
    }

    void dfs(TreeNode& root, vector<string> &ans, string path){
        path += (path.size() ? "->" : "") + std::to_string(root.val);
        if(!root.left && !root.right) {
            ans.push_back(path);
            return;
        }
        if(root.left) {
            dfs(*root.left, ans, path);
        }
        if(root.right) {
            dfs(*root.right, ans, path);
        }
    }
};

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        std::unordered_map<int, int> diffs{};
        int ans{};
        double mod{1e9 + 7};
        for (const int& num : nums) {
            int revNum{};
            int tempNum{num};
            while(tempNum) {
                revNum = (revNum * 10) + (tempNum % 10);
                tempNum /= 10;
            }
            int diff{num-revNum};
            if (diffs.contains(diff)) {
                ans = std::fmod(ans + diffs[diff], mod);
            }
            ++diffs[diff];
        }
        return ans;
    }

};

class Solution {
public:
    int countNicePairs(vector<int>& nums) {
        std::unordered_map<int, int> diffs{};
        for (const int& num : nums) {
            int revNum{};
            int tempNum{num};
            while(tempNum) {
                revNum = (revNum * 10) + (tempNum % 10);
                tempNum /= 10;
            }
            ++diffs[num - revNum];
        }
        int ans{};
        double mod{std::pow(10, 9) + 7};
        for (const auto& [num, count] : diffs) {
            long pairs{(1L * count * count - count) / 2};
            ans = std::fmod(ans + pairs, mod);
        }
        return ans;
    }

};

class Solution {
public:
    int titleToNumber(string columnTitle) {
        int ans{0};
        for (const char& ch : columnTitle) {
            ans = (ans * 26) + (ch - 'A') + 1;
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        std::vector<int> ans{};
        addNodes(*root, ans);
        return ans;
    }

    void addNodes(TreeNode& node, std::vector<int>& ans) {
        if (node.left != nullptr) {
            addNodes(*node.left, ans);
        }
        if (node.right != nullptr) {
            addNodes(*node.right, ans);
        }
        ans.push_back(node.val);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        std::vector<int> ans{};
        addNodes(root, ans);
        return ans;
    }

    void addNodes(TreeNode* node, std::vector<int>& ans) {
        auto left{node->left}, right{node->right};
        if (left != nullptr) {
            addNodes(left, ans);
        }
        if (right != nullptr) {
            addNodes(right, ans);
        }
        ans.push_back(node->val);
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        std::vector<int> ans{};
        std::vector<TreeNode*> q{root};
        while (q.size() != 0) {
            auto node = q.back();
            auto left{node->left}, right{node->right};
            q.pop_back();
            ans.push_back(node->val);
            if (right != nullptr) {
                q.push_back(right);
            }
            if (left != nullptr) {
                q.push_back(left);
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        std::vector<int> ans{};
        std::deque<TreeNode*> q{root};
        while (q.size() != 0) {
            auto node = q.front();
            auto left{node->left}, right{node->right};
            q.pop_front();
            ans.push_back(node->val);
            if (right != nullptr) {
                q.push_front(right);
            }
            if (left != nullptr) {
                q.push_front(left);
            }
        }
        return ans;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> ans{};
        std::deque<TreeNode*> q{root};
        while (q.size() != 0) {
            auto node = q.front();
            q.pop_front();
            if (node == nullptr) {
                continue;
            }
            ans.push_back(node->val);
            q.push_front(node->right);
            q.push_front(node->left);
        }
        return ans;
    }
};

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        vector<int> prefixSum(travel.size() + 1, 0);
        prefixSum[1] = travel[0];
        for (int i = 1; i < travel.size(); i++) {
            prefixSum[i + 1] = prefixSum[i] + travel[i];
        }
        unordered_map<char, int> garbageLastPos;
        unordered_map<char, int> garbageCount;
        for (int i = 0; i < garbage.size(); i++) {
            for (char c : garbage[i]) {
                garbageLastPos[c] = i;
                garbageCount[c]++;
            }
        }
        char garbageTypes[3] = {'M', 'P', 'G'};
        int ans = 0;
        for (char c : garbageTypes) {
            if (garbageCount[c]) {
                ans += prefixSum[garbageLastPos[c]] + garbageCount[c];
            }
        }
        return ans;
    }
};

class Solution {
public:
    int reductionOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        int up = 0;
        auto length {nums.size()};
        for (int i = 1; i < length; ++i) {
            if (nums[i] != nums[i - 1]) {
                ++up;
            }
            ans += up;
        }
        return ans;
    }
};

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int left = 0;
        int ans = 0;
        long curr = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            long target = nums[right];
            curr += target;
            
            while ((right - left + 1) * target - curr > k) {
                curr -= nums[left];
                left++;
            }
            
            ans = max(ans, right - left + 1);
        }
        
        return ans;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(!head || !head->next || !head->next->next) {
            return head;
        } 
        
        ListNode* odd {head};
        ListNode* even {head->next};
        ListNode* even_start {head->next};
        
        while(odd->next && even->next) {
            ListNode* next {even->next}; 
            odd->next = next;
            even->next = next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = even_start;
        return head; 
    }
};

class Solution {
public:
    string predictPartyVictory(string senate) {
        std::queue<int> rad, dir;
        unsigned long length {senate.size()};
        for (int i = 0; i < length; ++i){
            if (senate[i] == 'R'){
                rad.push(i);
            } else {
                dir.push(i);
            }
        }
        while (!rad.empty() && !dir.empty()) {
            if (rad.front() < dir.front()) {
                rad.push(length);
            } else {
                dir.push(length);
            }
            ++length;
            rad.pop();
            dir.pop();
        }
        return rad.empty() ? "Dire" : "Radiant";
    }
};

class Solution {
public:
    string decodeString(string s) {
        return std::get<1>(decode(0, s));
    }
    
    std::tuple<int, string> decode(int pos, string s) {
        int num {0};
        string word {""};
        unsigned long length {s.size()};
        for(; pos < length; ++pos) {
            char c = s[pos];
            if(c == '[') {
                auto [newPos, repeat] {decode(++pos, s)};
                for(; num > 0; --num) {
                    word += repeat;
                }
                pos = newPos;
            } else if (c >= '0' && c <='9') {
                num = num * 10 + (c - '0');
            } else if (c == ']') {
                return {pos, word};
            } else {
                word += c;
            }
        }
        return {pos, word};
    }
};

class Solution {
public:
    string decodeString(string s) {
        int pos = 0;
        return decode(pos, s);
    }
    
    string decode(int& pos, string s) {
        int num {0};
        string word {""};
        unsigned long length {s.size()};
        for(; pos < length; ++pos) {
            char c = s[pos];
            if(c == '[') {
                string repeat {decode(++pos, s)};
                for(; num > 0; --num) {
                    word += repeat;
                }
            } else if (c >= '0' && c <='9') {
                num = num * 10 + (c - '0');
            } else if (c == ']') {
                return word;
            } else {
                word += c;
            }
        }
        return word;
    }
};

class Solution {
public:
    string removeStars(string s) {
        std::string ans;
        int remove {0};
        for (int i = s.size() - 1; i >= 0; --i) {
            char c = s[i];
            if (c == '*') {
                ++remove;
            } else if (remove == 0) {
                ans += c;
            } else {
                --remove;
            }
        }
        std::reverse(ans.begin(), ans.end());
        return ans;
    }
};

class Solution {
public:
    string removeStars(string s) {
        std::string ans;
        unsigned long length {s.size()};
        int remove {0};
        for (int i = length - 1; i >= 0; --i) {
            char c = s[i];
            if (c == '*') {
                ++remove;
                continue;
            }
            if (remove == 0) {
                ans += c;
            } else {
                --remove;
            }
        }
        std::reverse(ans.begin(), ans.end());
        return ans;
    }
};

class Solution {
public:
    int minPairSum(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        unsigned long length {nums.size()};
        int maxSum {0};
        for (int i = 0; i < length / 2; ++i) {
            maxSum = max(maxSum, nums[i] + nums[length - i - 1]);
        }
        return maxSum;
    }
};

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        std::unordered_map<int, int> counts;
        std::unordered_set<int> encountered;
        for (int num : arr) {
            counts[num] += 1;
        }
        for (const auto [num, count] : counts) {
            if (encountered.find(count) == encountered.end()) {
                encountered.insert(count);
            } else {
                return false;
            }
        }
        return true;
    }
};

class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int num1 {0}, num2 {1}, num3 {1};
        for (int i = 3; i <= n; ++i) {
            int newNum3 = num1 + num2 + num3; 
            num1 = num2;
            num2 = num3;
            num3 = newNum3;
        }
        return num3;
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        std::sort(nums.begin(), nums.end(), std::greater<int>());
        return nums[k-1];
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while (root != nullptr) {
            if (root->val == val) {
                return root;
            }
            if (root->val > val) {
                root = root->left;
            } else {
                root = root->right;
            }
        }
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr || root->val == val) {
            return root;
        }
        if (val > root->val) {
            return searchBST(root->right, val);
        }
        return searchBST(root->left, val);
    }
};

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int left {0}, right {std::accumulate(nums.begin() + 1, nums.end(), 0)};
        unsigned long length {nums.size()};
        if (right == 0) {
            return 0;
        }
        for (int i = 1; i < length; ++i) {
            left += nums[i-1];
            right -= nums[i];
            if (left == right) {
                return i;
            }
        }
        return -1;
    }
};

class Solution {
public:
    int largestAltitude(vector<int>& gain) {
        int att {0}, maxAtt {0};
        for (int num : gain) {
            att += num;
            maxAtt = max(maxAtt, att);
        }
        return maxAtt;
    }
};

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        unordered_set<int> integers;
        for (string num : nums) {
            integers.insert(stoi(num, 0, 2));
        }

        int n = nums.size();
        string ans;
        for (int num = 0; num <= n; num++) {
            if (integers.find(num) == integers.end()) {
                ans = bitset<16>(num).to_string();
                break;
            }
        }
        return ans.substr(16 - n);
    }
};

class Solution {
public:
    vector<int> getElementsOnlyInFirstList(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> onlyInNums1;
        for (int num : nums1) {
            bool existInNums2 = false;
            for (int x : nums2) {
                if (x == num) {
                    existInNums2 = true;
                    break;
                }
            }
            if (!existInNums2) {
                onlyInNums1.insert(num);
            }
        }
        return vector<int> (onlyInNums1.begin(), onlyInNums1.end());
    }
    
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        return {getElementsOnlyInFirstList(nums1, nums2), getElementsOnlyInFirstList(nums2, nums1)};
    }
};

class Solution {
public:
    bool increasingTriplet(vector<int>& nums) {
        auto length{nums.size()};
        int num1{INT_MAX}, num2{INT_MAX}; 
        for (int num : nums) {
            if (num <= num1) {
                num1 = num;
            } else if (num <= num2) {
                num2 = num;
            } else {
                return true;
            }
        }
        return false;
    }
};

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        std::sort(arr.begin(), arr.end());
        auto length{arr.size()};
        int prev{1};
        for (int i = 1; i < length; ++i) {
            if (arr[i] != prev) {
                ++prev;
            }
        }
        return prev;
    }
};

class Solution {
public:
    int maximumElementAfterDecrementingAndRearranging(vector<int>& arr) {
        std::sort(arr.begin(), arr.end());
        auto length{arr.size()};
        int prev{1};
        for (int i = 1; i < length; ++i) {
            if (arr[i] == prev) {
                continue;
            }
            ++prev;
        }
        return prev;
    }
};

class Solution {
public:
    int countPalindromicSubsequence(string s) {
        unordered_set<char> letters;
        for (char c : s) {
            letters.insert(c);
        }
        int ans = 0;
        for (char letter : letters) {
            int i = -1;
            int j = 0;
            for (int k = 0; k < s.size(); k++) {
                if (s[k] == letter) {
                    if (i == -1) {
                        i = k;
                    }
                    
                    j = k;
                }
            }
            unordered_set<char> between;
            for (int k = i + 1; k < j; k++) {
                between.insert(s[k]);
            }
            
            ans += between.size();
        }
        return ans;
    }
};

class Solution {
public:
    bool isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' ||
               ch == 'A' || ch == 'E' || ch == 'I' || ch == 'O' || ch == 'U';
    }

    string reverseVowels(string s) {
        unsigned long length{s.size()};
        unsigned long left{0}, right{length-1};
        while (left < right) {
            char chLeft{s[left]};
            char chRight{s[right]};
            if (!isVowel(chLeft)) {
                ++left;
            } else if (!isVowel(chRight)) {
                --right;
            } else {
                s[left] = chRight;
                s[right] = chLeft;
                ++left;
                --right;
            }
        }
        return s;
    }
};

class Solution {
public:
    // Returns true if the character is a vowel.
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'o'|| c == 'u'|| c == 'i' 
            || c == 'A' || c == 'E' || c == 'O'|| c == 'U'|| c == 'I';
    }
    
    string sortVowels(string s) {
        unordered_map<char, int> count;

        // Store the frequencies for each character.
        for (char c : s) {
            if (isVowel(c)) {
                count[c]++;
            }
        }

        // Sorted string having all the vowels.
        string sortedVowel = "AEIOUaeiou";
        string ans;
        int j = 0;
        for (int i = 0; i < s.size(); i++) {
            if (!isVowel(s[i])) {
                ans += s[i];
            } else {
                // Skip to the character which is having remaining count.
                while (count[sortedVowel[j]] == 0) {
                    j++;
                }

                ans += sortedVowel[j];
                count[sortedVowel[j]]--;
            }
        }
        return ans;
    }
};

class Solution {
public:
    string sortVowels(string s) {
        std::map<char, int> vowels{
            {'A', 0}, {'E', 0}, {'I', 0}, {'O', 0}, {'U', 0},
            {'a', 0}, {'e', 0}, {'i', 0}, {'o', 0}, {'u', 0}
        };
        unsigned long length{ s.size() };
        for (char ch : s) {
            if (vowels.contains(ch)) {
                ++vowels[ch];
            }
        }
        for (int i = 0; i < length; ++i) {
            const char ch = s[i];
            if (!vowels.contains(ch)) {
                continue;
            }
            for (const auto& [orderChar, count] : vowels) {
                if (count > 0) {
                    s[i] = orderChar;
                    --vowels[orderChar];
                    break;
                }
            }
        }
        return s;
    }
};

class Solution {
public:
    string sortVowels(string s) {
        std::map<char, int> vowels{
            {'A', 0}, {'E', 0}, {'I', 0}, {'O', 0}, {'U', 0},
            {'a', 0}, {'e', 0}, {'i', 0}, {'o', 0}, {'u', 0}
        };
        const char order[10]{ 'A', 'E', 'I', 'O', 'U', 'a', 'e', 'i', 'o', 'u' };
        unsigned long length{ s.size() };
        for (char ch : s) {
            if (vowels.contains(ch)) {
                ++vowels[ch];
            }
        }
        for (int i = 0; i < length; ++i) {
            const char ch = s[i];
            if (!vowels.contains(ch)) {
                continue;
            }
            for (char orderChar : order) {
                if (vowels[orderChar] > 0) {
                    s[i] = orderChar;
                    --vowels[orderChar];
                    break;
                }
            }
        }
        return s;
    }
};

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int length = nums.size();
        double sum = std::accumulate(nums.begin(), nums.begin() + k , 0);
        double maxSum = sum;
        for (int i = k; i < length; ++i) {
            sum += nums[i] - nums[i-k];
            maxSum = max(sum, maxSum);
        }
        return maxSum / k;
    }
};

class Solution {
public:
    int compress(vector<char>& chars) {
        int i = 0, res = 0;
        int length = chars.size();
        while (i < length) {
            int groupLength = 1;
            while (i + groupLength < length && chars[i + groupLength] == chars[i]) {
                groupLength++;
            }
            chars[res++] = chars[i];
            if (groupLength > 1) {
                for (char c : to_string(groupLength)) {
                    chars[res++] = c;
                }
            }
            i += groupLength;
        }
        return res;
    }
};

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int curZeros = flowerbed[0] == 0 ? 2 : 0;
        int length = flowerbed.size();
        int ans = 0;
        for (int i = 1; i < length; ++i) { 
            if (flowerbed[i] == 0) {
                curZeros += 1;
                continue;
            }
            ans += (curZeros - 1) / 2;
            curZeros = 0;
            if (ans >= n) {
                return true;
            }
        }
        ans += curZeros / 2;
        return ans >= n;
    }
};

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int curZeros = 0, length = flowerbed.size();
        if (flowerbed[0] == 0) {
            curZeros = 2;
        }
        int ans = 0;
        for (int i = 1; i < length; ++i) {
            bool isFlower = flowerbed[i] == 1; 
            if (!isFlower) {
                curZeros += 1;
                continue;
            }
            ans += (curZeros - 1) / 2;
            curZeros = 0;
            if (ans >= n) {
                return true;
            }
        }
        ans += curZeros / 2;
        return ans >= n;
    }
};

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) {
            return 0;
        }

        unordered_map<int, vector<int>> adjList;
        // Create a map from the bus stop to all the routes that include this stop.
        for (int route = 0; route < routes.size(); route++) {
            for (auto stop : routes[route]) {
                // Add all the routes that have this stop.
                adjList[stop].push_back(route);
            }
        }

        queue<int> q;
        unordered_set<int> vis;
        // Insert all the routes in the queue that have the source stop.
        for (auto route : adjList[source]){
            q.push(route);
            vis.insert(route);
        }

        int busCount = 1;
        while (q.size()) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                int route = q.front(); q.pop();

                // Iterate over the stops in the current route.
                for (auto stop: routes[route]) {
                    // Return the current count if the target is found.
                    if (stop == target) {
                        return busCount;
                    }

                    // Iterate over the next possible routes from the current stop.
                    for (auto nextRoute : adjList[stop]) {
                        if (!vis.count(nextRoute)) {
                            vis.insert(nextRoute);
                            q.push(nextRoute);
                        }
                    }
                }
            }
            busCount++;
        }
        return -1;
    }
};

class Solution {
public:
    int fib(int n) {
        if (n < 2) {
            return n;
        }
        int cur = 1, prev = 0;
        for (int i = 2; i <= n; ++i) {
            int newVal = cur + prev;
            prev = cur;
            cur = newVal;
        }
        return cur;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        head = new ListNode(-1, head);
        auto ans = head;
        while (head) {
            auto next = head->next;
            if (next && next->val == val) {
                head->next = next->next;
            } else {
                head = next;
            }
        }
        return ans->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        head = new ListNode(-1, head);
        auto ans = head;
        while (head) {
            auto next = head->next;
            if (next && next->val == val) {
                head->next = next->next;
            } else {
                head = head->next;
            }
        }
        return ans->next;
    }
};

class Solution {
public:
    bool isValid(string s) {
        std::vector<char> stack;
        for (const auto& ch : s) {
            switch (ch){
                case '[':
                case '{':
                case '(':
                    stack.push_back(ch);
                    break;
                case ')':
                    if (stack.empty() || stack.back() != '(') {
                        return false;
                    }
                    stack.pop_back();
                    break;
                case '}':
                    if (stack.empty() || stack.back() != '{') {
                        return false;
                    }
                    stack.pop_back();
                    break;
                case ']':
                    if (stack.empty() || stack.back() != '[') {
                        return false;
                    }
                    stack.pop_back();
                    break;
            }
        }
        return stack.size() == 0;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::map<int, int> numToIndex;
        int length = nums.size();
        std::vector<int> ans;
        for (int i = 0; i < length; ++i) {
            int num = nums[i];
            int diff = target - num;
            if (numToIndex.contains(diff)) {
                ans = {numToIndex[diff], i};
                break;
            }
            numToIndex[num] = i;
        }
        return ans;
    }
};

class Solution {
public:
    string reverseWords(string s) {
        string ans = "";
        string temp = "";
        int length = s.length();
        int j = 0;
        for (j = 0; s[j] == ' ' && j < length; ++j) { }
        for (int i = length - 1; i >= j; --i) {
            if(s[i] == ' '){
                if(temp != ""){                  
                    ans = ans + temp + ' ';
                    temp = "";
                }
                continue;
            }
            else{
                temp = s[i] + temp;
            }
        }
        return ans + temp;
    }
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        ListNode* curr = head;
        while(curr != NULL){
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int length = nums.size();
        int lastNonZeroFoundAt = 0;
        for (int i = 0; i < length; ++i) {
            if (nums[i] != 0) {
                swap(nums[lastNonZeroFoundAt], nums[i]);
                lastNonZeroFoundAt += 1;
            }
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
    int lastNonZeroFoundAt = 0;
    int length = nums.size();
    for (int i = 0; i < length; ++i) {
        int num = nums[i];
        if (num == 0) {
            continue;
        }
        if (i != lastNonZeroFoundAt) {
            nums[lastNonZeroFoundAt] = num;
        }
        lastNonZeroFoundAt += 1;
    }
 	for (int i = lastNonZeroFoundAt; i < length; i++) {
        nums[i] = 0;
    }
}
};

class Graph {
public:
    vector<vector<pair<int, int>>> adjList;
    Graph(int n, vector<vector<int>>& edges) {
        adjList.resize(n);
        for (auto& e: edges)
            adjList[e[0]].push_back(make_pair(e[1], e[2]));
    }

    void addEdge(vector<int> edge) {
        adjList[edge[0]].push_back(make_pair(edge[1], edge[2]));
    }

    int shortestPath(int node1, int node2) {
        int n = adjList.size();
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
        vector<int> costForNode(n, INT_MAX);
        costForNode[node1] = 0;
        pq.push({0, node1});

        while (!pq.empty()) {
            int currCost = pq.top()[0];
            int currNode = pq.top()[1];
            pq.pop();

            if (currCost > costForNode[currNode]) {
                continue;
            }
            if (currNode == node2) {
                return currCost;
            }
            for (auto& neighbor : adjList[currNode]) {
                int neighborNode = neighbor.first;
                int cost = neighbor.second;
                int newCost = currCost + cost;

                if (newCost < costForNode[neighborNode]) {
                    costForNode[neighborNode] = newCost;
                    pq.push({newCost, neighborNode});
                }
            }
        }
        return -1;
    }
};

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        string result = "";

        for (int i = 0; i < max(m, n); i++) {
            if (i < m) {
                result.push_back(word1[i]);
            }
            if (i < n) {
                result.push_back(word2[i]);
            }
        }

        return result;
    }
};

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int l1 = word1.size(), l2 = word2.size();
        string result = "";
        int i = 0, j = 0;
        while (i < l1 || j < l2) {
            if (i < l1) {
                result.push_back(word1[i++]);
            }
            if (j < l2) {
                result.push_back(word2[j++]);
            }
        }
        return result;
    }
};

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        std::stringstream ans;
        int l1 = word1.size(), l2 = word2.size();
        int lMax = max(l1, l2);
        for (int i = 0; i < lMax; ++i) {
            if (i < l1) {
                ans << word1[i];
            } else {
                ans << word2.substr(i);
                break;
            }
            if (i < l2) {
                ans << word2[i];
            } else {
                ans << word1.substr(i + 1);
                break;
            }
        }
        return ans.str();
    }
};