class Solution {
    public String reverseVowels(String s) {
        String vowels = "aeiouAEIOU";
        char[] chars = s.toCharArray();

        int left = 0, right = s.length() - 1;
        while (left < right) {
            // Move left pointer to find the next vowel
            while (left < right && vowels.indexOf(chars[left]) == -1) {
                left++;
            }

            // Move right pointer to find the previous vowel
            while (left < right && vowels.indexOf(chars[right]) == -1) {
                right--;
            }

            // Swap vowels
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            ;
            right--;
        }

        return new String(chars);
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;

        // Iterate while left pointer is before right pointer
        while (left < right) {
            int currentSum = numbers[left] + numbers[right];

            // Check if the current sum matches the target
            if (currentSum == target) {
                break;
            }

            // Adjust the pointers to move towards the target sum
            if (currentSum < target) { 
                left++; // Increase sum by moving left pointer right
            } else { 
                right--; // Decrease sum by moving right pointer left
            }
        }

        // Return 1-indexed result
        return new int[] { left + 1, right + 1 }; 
    }
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int left = 0, right = nums.length - 1;
        int[] squares = new int[n];

        // Traverse the array from both ends to calculate squares in descending order
        while (left <= right) {
            if (Math.abs(nums[left]) <= Math.abs(nums[right])) {
                // Place the square of the right element at the current position
                squares[--n] = nums[right] * nums[right];
                right--;
            } else {
                // Place the square of the left element at current position
                squares[--n] = nums[left] * nums[left];
                left++;
            }
        }

        return squares;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[k];
                nums[k++] = temp;
            }
        }       
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;

        // Traverse the array to move the elements that are not equal to the 'val' to the front
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                // If the current element is not equal to the 'val', place it at the next available position
                nums[k++] = nums[i];
            }
        }

        // Return the length of the array after removing all elements
        return k;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {
        // Track the position for the next unique element
        int nextUnique = 1;
        for (int i = 1; i < nums.length; i++) {
            // If the current element is different from the previous unique element
            if (nums[nextUnique - 1] != nums[i]) {
                // Move the current element to the next unique position
                nums[nextUnique++] = nums[i];
            }
        }

        return nextUnique;
    }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1;
        int k = m + n - 1;

        // Merge nums1 and nums2 from the end
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        // If there are remaining elements in nums2, copy them to nums1
        while (j >= 0) {
            nums1[k--] = nums2[j--];
    }

        // If there are remaining elements in nums1 (i >= 0), they are already sorted
    }
}

class Solution {
    public List threeSum(int[] nums) {
        List triplets = new ArrayList<>();

        // Sort the array to enable the two-pointer approach
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicates for 'i' to ensure unique triplets
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            // Find pairs that sum up to the negative of the current number
            findTwoSum(nums, -nums[i], i + 1, nums.length - 1, triplets);
        }

        return triplets;
    }

    private static void findTwoSum(int[] nums, int target, int left, int right, List triplets) {
        while (left < right) {
            int currentSum = nums[left] + nums[right];
            if (target == currentSum) {
                triplets.add(Arrays.asList(-target, nums[left], nums[right]));
                left++;
                right--;

                // Skip duplicates for 'left' and 'right' to avoid duplicate triplets
                while (left < right && nums[left] == nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right + 1]) {
                    right--;
                }
            } else if (currentSum < target) {
                // Move 'left' pointer to the right to increase the sum
                left++;
            } else {
                // Move 'right' pointer to the left to decrease the sum
                right--;
            }
        }
    }
}

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;

        int maxVolume = 0;

        while (left < right) {
            // Calculate the width and height of the current container
            int width = right - left;
            int heightOfContainer = Math.min(height[left], height[right]);

            // Update the maximum volume if the current one is larger
            maxVolume = Math.max(maxVolume, width * heightOfContainer);

            // Move the pointer pointing to the shorter height to find a potentially larger height
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxVolume;
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int left = 0, right = nums.length - 1;
        int i = 0;
        while (i <= right) {
            if (nums[i] == 0) {
                // Swap 0 to the left side and move both 'left' and 'i' pointer
                swap(nums, i, left);
                left++;
                i++;
            } else if (nums[i] == 1) {
                i++;
            } else {
                // Swap 2 to the right side and move the 'right' pointer
                swap(nums, i, right);
                right--;
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        // Initialize slow and fast pointers at the head of the list
        ListNode slow = head, fast = head;

        // Traverse the list with fast and slow pointers
        while (fast != null && fast.next != null) {
            // Move slow pointer by one step and fast pointer by two steps
            slow = slow.next;
            fast = fast.next.next;

            // If the two pointers meet, a cycle is detected
            if (slow == fast) {
                return true;
            }
        }

        // If fast pointer reaches the end, there's no cycle
        return false;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        // Initialize slow and fast pointers at the head of the list
        ListNode slow = head, fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;          // Move slow pointer by one step
            fast = fast.next.next;     // Move fast pointer by two steps
        }

        // When fast pointer reaches the end, slow pointer will be at the middle
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Create a dummy node to handle edge cases (e.g., removing the head)
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // Initialize slow and fast pointers at the dummy node
        ListNode slow = dummy, fast = dummy;

        // Move the fast pointer n+1 steps ahead from the dummy node
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // Move both slow and fast pointers one step at a time until fast reaches the
        // end
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // Remove the nth node from the end by skipping it
        slow.next = slow.next.next;

        // Return the updated head
        return dummy.next;
    }
}

public class Solution {
    public int findMaxSumSubArray(int k, int[] arr) {
        int windowStart = 0;
        int windowSum = 0, maxSum = Integer.MIN_VALUE;
        for (int windowEnd = 0; windowEnd < arr.length; windowEnd++) {
            windowSum += arr[windowEnd]; // Update the window sum

            // Iterate the array to expand the window
            if (windowEnd >= k - 1) {
                maxSum = Math.max(windowSum, maxSum); // Update the maximum sum
                windowSum -= arr[windowStart]; // Remove the element going out of the window
                windowStart++; // Shink the window
            }
        }

        return maxSum;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println("Maximum sum of a subarray of size K: "
                + sol.findMaxSumSubArray(3, new int[]{2, 1, 5, 1, 3, 2}));
        System.out.println("Maximum sum of a subarray of size K: "
                + sol.findMaxSumSubArray(2, new int[]{2, 3, 4, 1, 5}));
    }
}

Maximum sum of a subarray of size K: 9
Maximum sum of a subarray of size K: 7

class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
        int totalSatisfied = 0;
        // Calculate initially satisfied customers
        for (int i = 0; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                totalSatisfied += customers[i];
            }
        }

        int windowStart = 0;
        int maxAdditionalSatisfied = 0;
        int windowSatisfied = 0;
        for (int windowEnd = 0; windowEnd < customers.length; windowEnd++) {
            // Add the new element to the sliding window if the bookstore owner is grumpy
            if (grumpy[windowEnd] == 1) {
                windowSatisfied += customers[windowEnd];
            }

            // Matain a window of size 'minutes'
            if (windowEnd - windowStart + 1 > minutes) {
                if (grumpy[windowStart] == 1) {
                    windowSatisfied -= customers[windowStart];
                }
                windowStart++;
            }

            maxAdditionalSatisfied = Math.max(maxAdditionalSatisfied, windowSatisfied);
        }

        return totalSatisfied + maxAdditionalSatisfied;
    }
}

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findLength(String str, int k) {
        Map<Character, Integer> charFrequencyMap = new HashMap<>();
        int windowStart = 0;
        int maxLength = 0;

        // Iterate the char sequence to expand the window
        for (int windowEnd = 0; windowEnd < str.length(); windowEnd++) {
            char endChar = str.charAt(windowEnd);
            charFrequencyMap.put(endChar, charFrequencyMap.getOrDefault(endChar, 0) + 1);

            // Shrink the window if there are more than 'k' distinct characters
            while (charFrequencyMap.size() > k) {
                char startChar = str.charAt(windowStart);
                charFrequencyMap.put(startChar, charFrequencyMap.get(startChar) - 1);
                if (charFrequencyMap.get(startChar) == 0) {
                    charFrequencyMap.remove(startChar);
                }
                windowStart++; // Shrink the window
            }

            // Update the maximum length of the valid substring found
            maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println("Length of the longest substring: "
                + sol.findLength("araaci", 2));
        System.out.println("Length of the longest substring: "
                + sol.findLength("araaci", 1));
        System.out.println("Length of the longest substring: "
                + sol.findLength("cbbebi", 3));
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> windowSet = new HashSet<>();

        int windowStart = 0, maxLength = 0;
        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char endChar = s.charAt(windowEnd);
            
            // If encounter a duplicate, shrink the window
            while (windowSet.contains(endChar)) {
                windowSet.remove(s.charAt(windowStart));
                windowStart++;
            }

            // Add the current character to the window set
            windowSet.add(endChar);
            
            // Update the maximum length
            maxLength = Math.max(maxLength, windowSet.size());
        }

        return maxLength;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int windowStart = 0, minLength = Integer.MAX_VALUE;
        int windowSum = 0;
        for (int windowEnd = 0; windowEnd < nums.length; windowEnd++) {
            // Expand the window by adding the current element
            windowSum += nums[windowEnd];

            // Shrink the window while the window sum at least the target
            while (windowSum >= target) {
                // Update the minimum length
                minLength = Math.min(minLength, windowEnd - windowStart + 1);
                // Remove the leftmost element
                windowSum -= nums[windowStart];
                // Shrink the window by incrementing window start pointer
                windowStart++;
            }

        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }

        Map<Character, Integer> freqMap = new HashMap<>();
        // Populate the frequency of characters in 't'
        for (char c : t.toCharArray()) {
            freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
        }


        int windowStart = 0, subStart = 0;
        int matched = 0; // Count of characters matched with 't'
        int minLength = s.length() + 1;
        for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
            char endChar = s.charAt(windowEnd);

            if (freqMap.containsKey(endChar)) {
                freqMap.put(endChar, freqMap.get(endChar) - 1);

                // Count a valid match only if the character's frequency in the window does not exceed its need
                if (freqMap.get(endChar) >= 0) {
                    matched++;
                }
            }

            // Shrink the window as soon as possible when all characters in 't' are matched
            while (matched == t.length()) {
                if (minLength > windowEnd - windowStart + 1) {
                    minLength = windowEnd - windowStart + 1;
                    subStart = windowStart;
                }

                char startChar = s.charAt(windowStart++);

                if (freqMap.containsKey(startChar)) {
                    // Decrease 'matched' if a character fully removed
                    if (freqMap.get(startChar) == 0) {
                        matched--;
                    }
                    freqMap.put(startChar, freqMap.get(startChar) + 1);
                }
            }
        }

        return minLength > s.length() ? "" : s.substring(subStart, subStart + minLength);
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        // Sort intervals by their start point
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // List to store merged intervals
        List<int[]> mergedIntervals = new ArrayList<>();

        // Initialize the first interval as the current interval
        mergedIntervals.add(intervals[0]);

        // Iterate through the intervals
        for (int i = 1; i < intervals.length; i++) {
            int[] currentInterval = mergedIntervals.get(mergedIntervals.size() - 1);
            int[] nextInterval = intervals[i];

            // If the next interval overlaps with the current interval
            if (nextInterval[0] <= currentInterval[1]) {
                // Merge by updating the end point of the current interval
                currentInterval[1] = Math.max(currentInterval[1], nextInterval[1]);
            } else {
                // No overlap, add the next interval as a new interval
                mergedIntervals.add(nextInterval);
            }
        }

        // Convert the list to a 2D array and return
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> mergedIntervals = new ArrayList<>();

        int i = 0;
        // Add all intervals that ends before the new interval starts
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            mergedIntervals.add(intervals[i]);
            i++;
        }

        // Merge the overlapping intervals with the new interval
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }

        // Add the merged new interval to the result list
        mergedIntervals.add(newInterval);

        // Add all intervals that don't overlap with the new interval to the result list
        while (i < intervals.length) {
            mergedIntervals.add(intervals[i]);
            i++;
        }

        // Convert the list to a 2-D array and return
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }
}

class Solution {
    public int[][] intervalIntersection(int[][] arr1, int[][] arr2) {
        List<int[]> intersections = new ArrayList<>();
        int i = 0, j = 0;

        // Iterate over both interval lists to find all intersections
        while (i < arr1.length && j < arr2.length) {
            // Check if both intervals are overlapped
            if ((arr1[i][0] >= arr2[j][0] && arr1[i][0] <= arr2[j][1])
                    || (arr2[j][0] >= arr1[i][0] && arr2[j][0] <= arr1[i][1])) {
                
                // Store the intersection part
                intersections.add(new int[]{Math.max(arr1[i][0], arr2[j][0]),
                        Math.min(arr1[i][1], arr2[j][1])});
            }

            // Move the pointer of the interval that ends first
            if (arr1[i][1] < arr2[j][1]) {
                i++;
            } else {
                j++;
            }
        }

        // Return the intersections as a 2D array
        return intersections.toArray(new int[intersections.size()][]);
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; // Tracks the previous node
        ListNode current = head; // Tracks the current node

        // Traverse and reverse the list
        while (current != null) {
            ListNode next = current.next; // Save the next node
            current.next = prev; // Reverse the link
            prev = current; // Move prev forward
            current = next; // Move current forward
        }

        return prev; // New head of the reversed list
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode prev = null, current = head;
        
        // Skip the first left - 1 node to reach the node at position left
        for (int i = 1; i < left && current != null; i++) {
            prev = current;
            current = current.next;
        }

        // Save the node at position left - 1 to reconnect the reversed sublist
        ListNode lastNodeOfFirstPart = prev;
        // After reversing, the left node will become the last node of the reversed sublist
        ListNode lastNodeOfReversedList = current;

        // Reverse the node from left to right
        ListNode next = null;
        for (int i = 1; i <= right - left + 1 && current != null; i++) {
            next = current.next; // Save the next node
            current.next = prev; // Reverse the link
            prev = current; // Move the 'prev' node forward
            current = next; // Move the 'current' node forward
        }

        // Reconnect the reversed sublist with the rest of the list
        if (lastNodeOfFirstPart != null) {
            // Connect with the new head of the sublist
            lastNodeOfFirstPart.next = prev;
        } else { // left == 1 in this case
            head = prev;
        }

        // Connect the tail of the reversed sublist to the remaining list
        lastNodeOfReversedList.next = current;

        return head;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // Return the original list if the list is empty or k is 1
        if (head == null || k == 1) {
            return head;
        }

        // Count the total number of the list
        ListNode temp = head;
        int count = 0;
        while (temp != null) {
            count++;
            temp = temp.next;
        }

        ListNode prev = null, current = head, next = null;
        while (current != null && count >= k) {
            ListNode lastNodeOfPrevGroup = prev;
            // After reversing, the current node will become the last node of the reversed list
            ListNode lastNodeOfReversedList = current;

            // Reverse the list in groups of size k
            for (int i = 0; i < k; i++) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
                count--;
            }

            // Connect the last node of the reversed sublist to the start node of the
            // remaining list
            lastNodeOfReversedList.next = current;

            // Connect with the previous group
            if (lastNodeOfPrevGroup != null) {
                // After reversing, the prev node is the head node of the sublist
                lastNodeOfPrevGroup.next = prev;
            } else {
                // When previous group is null, the prev node becomes the head of the original list
                head = prev;
            }

            // Break the loop when current is null or count is less than k
            if (current == null || count < k) {
                break;
            }

            // Update the prev node for next iteration
            prev = lastNodeOfReversedList;
        }

        return head;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        // for (int i = 0; i < nums.length; i++) {
        for (int i = 0; ; i++) {
            int complement = target - nums[i];

            // If the complement exists in the map
            if (frequencyMap.containsKey(complement)) {
                return new int[]{frequencyMap.get(complement), i};
            }

            // Store the current element's index for future reference
            frequencyMap.put(nums[i], i);
        }

        // return new int[]{};
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        // Store the frequency of each character
        Map<Character, Integer> freqMap = new HashMap<>();

        // Iterate through both strings to build the frequency map
        for (int i = 0; i < s.length(); i++) {
            // Increment the frequency of the character from string s
            freqMap.put(s.charAt(i), freqMap.getOrDefault(s.charAt(i), 0) + 1);
            // Decrement the frequency of the character from string t
            freqMap.put(t.charAt(i), freqMap.getOrDefault(t.charAt(i), 0) - 1);
        }

        for (int v: freqMap.values()) {
            // If any characters' frequency is non-zero, the strings are not anagram
            if (v != 0) {
                return false;
            }
        }
        
        // If all characters' frequency is zero, the strings are anagram
        return true;
    }
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> result = new ArrayList<>();
        Map<Integer, Integer> freqMap = new HashMap<>();

        for (int i = 0; i < nums1.length; i++) {
            freqMap.put(nums1[i], freqMap.getOrDefault(nums1[i], 0) + 1);
        }

        for (int i = 0; i < nums2.length; i++) {
            if (freqMap.getOrDefault(nums2[i], 0) != 0) {
                result.add(nums2[i]);
                freqMap.put(nums2[i], 0);
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

class Solution {
    public int firstUniqChar(String s) {
        // Use a HashMap to store the frequency of each character
        Map<Character, Integer> charFrequencyMap = new HashMap<>();

        // Populate the map with the frequency of each character
        for (char c : s.toCharArray()) {
            charFrequencyMap.put(c, charFrequencyMap.getOrDefault(c, 0) + 1);
        }

        // Iterate over the string to find the index of the first unique character
        for (int i = 0; i < s.length(); i++) {
            if (charFrequencyMap.get(s.charAt(i)) == 1) {
                return i; // Return the index of the first unique character
            }
        }

        // No unique character found, return -1
        return -1;
    }
}

class Solution {
    public int maxNumberOfBalloons(String text) {
        // Define the required frequencies of characters to form 'balloon'
        Map<Character, Integer> requiredCharMap = Map.of(
                'b', 1,
                'a', 1,
                'l', 2,
                'o', 2,
                'n', 1);

        // Calculate the frequencies of characters that are part of 'balloon'
        Map<Character, Integer> availableCharMap = new HashMap<>();
        for (char c : text.toCharArray()) {
            if (requiredCharMap.containsKey(c)) {
                availableCharMap.put(c, availableCharMap.getOrDefault(c, 0) + 1);
            }
        }
        
        // Calculate the maximum available count of the word 'balloon'
        int maxCount = Integer.MAX_VALUE;
        if (availableCharMap.size() == requiredCharMap.size()) {
            for (char c : availableCharMap.keySet()) {
                int requiredCount = requiredCharMap.get(c);
                int availableCount = availableCharMap.get(c);
                maxCount = Math.min(maxCount, availableCount / requiredCount);
            }
        }

        return (maxCount == Integer.MAX_VALUE) ? 0 : maxCount;
    }
}

class Solution {
    public int longestPalindrome(String s) {
        // Calculate the frequency of each character in the string
        Map<Character, Integer> frequencyMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
        }

        // Flag to track if any character has an odd frequency
        boolean oddFound = false;
        int maxLength = 0;

        // Calculate the maximum possible length of the palindrome
        for (int count : frequencyMap.values()) {
            if (count % 2 == 0) {
                // Add even counts directly to the length of the palindorme
                maxLength += count;
            } else {
                maxLength += count - 1; // Add the even parts of odd counts
                oddFound = true; // Mark an odd frequency character exists
            }
        }

        // For characters has an odd count, one can be placed in the middle of the palindrome
        return oddFound ? maxLength + 1 : maxLength;
    }
}

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // A map stores the element with its most recent index;
        Map<Integer, Integer> map= new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }

            // Update the map with the current index of the element
            map.put(nums[i], i);
        }

        return false;
    }
}

class Solution {
    public int findMiddleIndex(int[] nums) {
        // Calculate the total sum of the array
        int totalSum = Arrays.stream(nums).sum();

        int leftSum = 0;
        // Iterate through the array to find the middle index
        for (int i = 0; i < nums.length; i++) {
            // Calculate the right sum
            int rightSum = totalSum - leftSum - nums[i];

            // Found the middle index if left sum equals to right sum
            if (leftSum == rightSum) {
                return i;
            }

            // Update the left sum for next iteration
            leftSum += nums[i];
        }

        // Return -1 if middle index is found
        return -1;
    }
}

class Solution {
    public int[] leftRightDifference(int[] nums) {
        int n = nums.length;

        // Calculate the total sum of nums
        int totalSum = Arrays.stream(nums).sum();

        // Construct prefix sum array based on nums
        int[] prefix = new int[n];
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++) {
            prefix[i] = nums[i] + prefix[i - 1];
        }

        int[] answer = new int[n];
        // Iterate over nums to calculate the absolute difference between left and right
        // sums for each index
        for (int i = 0; i < n; i++) {
            int leftSum = prefix[i] - nums[i];
            int rightSum = totalSum - prefix[i];

            answer[i] = Math.abs(leftSum - rightSum);
        }

        return answer;
    }
}

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        // Store frequency of prefix sum modulo k
        Map<Integer, Integer> prefixSumModCount = new HashMap<>();
        
        // Initialize with mod 0 having a frequency of 1 
        // (for the case where the prefix sum itself is divisible by k)
        prefixSumModCount.put(0, 1);

        // Initialize the prefix sum and the count of valid subarrays
        int prefixSum = 0, count = 0;
        for (int num : nums) {
            // Update the current prefix sum
            prefixSum += num;
            
            // Ensure the modulo is always positive
            int mod = ((prefixSum % k) + k) % k;

            // If the same mod has been seen before, 
            // it means there are subarrays whose sum is divisible by k
            count += prefixSumModCount.getOrDefault(mod, 0);

            // Update frequency of current mod
            prefixSumModCount.put(mod, prefixSumModCount.getOrDefault(mod, 0) + 1);
        }

        return count;
    }
}

class Solution {
    public boolean isValid(String s) {
        // Track opening parenthses
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (isOpenParenthesis(c)) {
                stack.push(c); // Push opening parenthesis onto the stack
            } else {
                // If stack is empty or the top of stack doesn't match the closing parenthesis, return false
                if (stack.isEmpty() || !isMatched(stack.pop(), c)) {
                    return false;
                }
            }
        }

        // If stack is empty, all parenthses are balanced
        return stack.isEmpty();
    }

    private static boolean isOpenParenthesis(char c) {
        return c == '(' || c == '[' || c == '{';
    }

    private static boolean isMatched(char open, char closed) {
        return (open == '(' && closed == ')')
                || (open == '[' && closed == ']')
                || (open == '{' && closed == '}');
    }
}

class Solution {
    public String simplifyPath(String path) {
        // Store the simplified path components
        Stack<String> stack = new Stack<>();

        // Split the path string using "/" as a delimeter
        for (String s : path.split("/")) {
            if ("..".equals(s)) {
                // If the component is "..", pop the last component from the stack
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else if (!s.isEmpty() && !".".equals(s)) {
                // If the component is not empty and not ".", push it onto the stack
                stack.push(s);
            }
        }

        StringBuilder builder = new StringBuilder();
        for (String s : stack) {
            builder.append("/").append(s);
        }

        return builder.isEmpty() ? "/" : builder.toString();
    }
}

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            if (isOperator(token)) {
                int b = stack.pop(); // Second operand (popped first)
                int a = stack.pop(); // First operand (popped second)
                stack.push(compute(a, b, token)); // Push result back to stack
            } else {
                stack.push(Integer.parseInt(token)); // Convert operand to integer and push
            }
        }

        return stack.pop(); // Final result
    }

    private boolean isOperator(String s) {
        return "+".equals(s) || "-".equals(s) || "*".equals(s) || "/".equals(s);
    }

    private int compute(int a, int b, String operator) {
        switch (operator) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "*":
                return a * b;
            case "/":
                return a / b; // Integer division truncates toward zero
            default:
                throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}

import java.util.Stack;

class Solution {
    public String decodeString(String s) {
        Stack<Integer> countStack = new Stack<>();
        Stack<StringBuilder> stringStack = new Stack<>();
        StringBuilder currentString = new StringBuilder();
        int currentCount = 0;

        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                // Build the repeat count (handles multiple digits)
                currentCount = currentCount * 10 + (c - '0');

            } else if (c == '[') {
                // Push the current count and string to their respective stacks
                countStack.push(currentCount);
                stringStack.push(currentString);
                // Reset for the new encoded block
                currentString = new StringBuilder();
                currentCount = 0;

            } else if (c == ']') {
                // Decode the string inside the brackets
                int repeatTimes = countStack.pop();
                StringBuilder decodedSubstring = new StringBuilder();
                for (int i = 0; i < repeatTimes; i++) {
                    decodedSubstring.append(currentString);
                }

                // Append the decoded string to the previous stored string
                currentString = stringStack.pop().append(decodedSubstring);

            } else { // Normal characters
                currentString.append(c);
            }
        }

        return currentString.toString();
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String s = in.nextLine().trim();

        // Evaluate the given expression
        int result = evaluate(s);

        // Output result
        System.out.println(result);
    }

    private static int evaluate(String s) {
        Stack<Integer> numStack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        int num = 0;
        boolean isParsingNumber = false;

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                // Construct multi-digit number
                num = num * 10 + (c - '0');
                isParsingNumber = true;
            } else {
                if (isParsingNumber) {
                    numStack.push(num);
                    num = 0;
                    isParsingNumber = false;
                }

                if (c == '(') {
                    opStack.push(c);
                } else if (c == ')') {
                    // Process until '(' encountered
                    while (opStack.peek() != '(') {
                        numStack.push(calculate(numStack.pop(), numStack.pop(), opStack.pop()));
                    }
                    opStack.pop(); // Remove '('
                } else if (isOperator(c)) {
                    // Process operators with higher or equal precedence
                    while (!opStack.isEmpty() &&
                            precedence(opStack.peek()) >= precedence(c)) {
                        numStack.push(calculate(numStack.pop(), numStack.pop(), opStack.pop()));
                    }
                    opStack.push(c);
                }
            }
        }

        // Push last number if any
        if (isParsingNumber) {
            numStack.push(num);
        }

        // Process remaining operators
        while (!opStack.isEmpty()) {
            numStack.push(calculate(numStack.pop(), numStack.pop(), opStack.pop()));
        }

        return numStack.pop();
    }

    private static int calculate(int a, int b, char operator) {
        switch (operator) {
            case '+' :
                return b + a;
            case '-' :
                return b - a;
            case '*' :
                return a * b;
            default:
                throw new IllegalArgumentException("Invalid Operator" + operator);
        }
    }

    private static int precedence(char c) {
        if (c == '+' || c == '-') {
            return 1;
        } else if (c == '*') {
            return 2;
        }
        return 0;
    }

    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*';

    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int[] nums = Arrays.stream(in.nextLine().trim().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        Stack<Integer> stack = new Stack<>();
        pushAndMerge(nums, stack); // Process numbers and apply merging rules

        formatOutput(stack); // Print the final stack
    }

    private static void pushAndMerge(int[] nums, Stack<Integer> stack) {
        for (int num : nums) {
            stack.push(num); // Push the current number onto the stack

           /*
             1. Rule 1: Merge if top two elements are equal.
             2. Rule 2: Merge if sum of from the second-to-top to certain bottom
                element equal to top.
             3. Merge rule 1 & rule 2: Starting from the top and moving downward,
                if the first element equals the sum of any number of elements below
                it, they can be merged.
           */
            // Apply merging rules until no further merges are possible
            while (stack.size() >= 2) {
                int sum = 0;
                int count = 0;
                boolean merged = false;

                for (int i = stack.size() - 2; i >= 0; i--) {
                    int topNum = stack.peek();
                    sum += stack.get(i);
                    count++;

                    if (sum == topNum) {
                        stack.pop(); // Remove the top element
                        // Remove elements contributing to sum
                        while (count-- > 0) {
                            stack.pop();
                        }
                        stack.push(topNum * 2);
                        merged = true;
                        break;
                    } else if (sum > topNum) {
                        break;
                    }
                }

                if (!merged) {
                    break;
                }
            }
        }
    }

    private static void formatOutput(Stack<Integer> stack) {
        for (int i = stack.size() - 1; i >= 0; i--) {
            System.out.print(stack.get(i) + " ");
        }
    }
}

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // Initialize an empty stack to track elements in nums2
        Stack<Integer> stack = new Stack<>();
        // Map to store the next greater element for each number in nums2
        Map<Integer, Integer> nextGreaterMap = new HashMap<>();

        // Traverse nums2 from right to left to populate the nextGreaterMap
        for (int i = nums2.length - 1; i >= 0; i--) {
            int num = nums2[i];

            // Pop elements from stack that are less than or equal to the current number
            while (!stack.isEmpty() && stack.peek() <= num) {
                stack.pop();
            }

            // If stack is empty, no greater element exists, otherwise top of stack is the next greater element
            nextGreaterMap.put(num, stack.isEmpty() ? -1 : stack.peek());

            // Push the current number onto the stack for future comparisons
            stack.push(num);
        }

        // Prepare the result array for nums1 based on nextGreaterMap
        int[] result = new int[nums1.length];
        // Find the next greater element for each number in nums1
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreaterMap.get(nums1[i]);
        }

        return result;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        Stack<ListNode> stack = new Stack<>();

        ListNode current = head;
        while (current != null) {
            while (!stack.isEmpty() && stack.peek().val < current.val) {
                stack.pop(); // Remove nodes from the stack that are samller than the current node
            }

            if (!stack.isEmpty()) {
                // Update the next pointer of the top node in the stack
                stack.peek().next = current;
            }

            // Push the current node onto the stack
            stack.push(current);
            current = current.next;
        }

        return stack.get(0);
    }
}

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        Stack<Integer> stack = new Stack<>();
        int[] answer = new int[n];

        for (int i = 0; i < n; i++) {
            // Pop elements from the stack as long as the current temperature is higher than
            // the temperature at the index of the stack's top
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int topIndex = stack.pop();
                answer[topIndex] = i - topIndex; // Calculate the difference in days
            }

            // Push current day's index onto the stack
            stack.push(i);
        }

        return answer;
    }
}

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (!stack.isEmpty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }

        StringBuilder builder = new StringBuilder();
        for (char c : stack) {
            builder.append(c);
        }

        return builder.toString();
    }
}

// class Solution {
//     public String removeDuplicates(String s) {
//         StringBuilder builder = new StringBuilder();

//         for (char c : s.toCharArray()) {
//             if (!builder.isEmpty() && builder.charAt(builder.length() - 1) == c) {
//                 builder.setLength(builder.length() - 1);
//             } else {
//                 builder.append(c);
//             }
//         }

//         return builder.toString();
//     }
// }

class Solution {
    public String removeDuplicates(String s, int k) {
        // Stack to store characters along with their consecutive count
        Stack<int[]> stack = new Stack<>();

        // Iterate over each character in the string
        for (char c : s.toCharArray()) {
            // Check if the stack is not empty and the current character is the same as the top character
            if (!stack.isEmpty() && stack.peek()[0] == c) {
                // Increment the count of top character by 1
                stack.peek()[1]++;
            } else {
                // Otherwise, push the current character onto the stack with count 1
                stack.push(new int[]{c, 1});
            }

            // If the top character's count reaches k, remove it from the stack
            if (stack.peek()[1] == k) {
                stack.pop();
            }
        }

        // Construct result string from the stack
        StringBuilder builder = new StringBuilder();
        for (int[] entry : stack) {
            builder.append(String.valueOf((char) entry[0]).repeat(entry[1]));
        }

        return builder.toString();
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        // Return an empty list if the tree is empty
        if (root == null) {
            return result;
        }

        // Initialize a queue for level order traversal
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // Add the root node to the queue

        while (!queue.isEmpty()) {
            int levelSize = queue.size();  // Get the number of nodes at the current level
            List<Integer> currentLevel = new ArrayList<>();

            // Process all nodes at the current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                currentLevel.add(node.val);

                // Add left and right children to the queue if they exist
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            // Add the current level's result to the overall result
            result.add(currentLevel);
        }

        return result;  // Return the level order traversal result
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();

        // Return empty result if tree is empty
        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);  // Add the root node to the queue

        boolean leftToRight = true;  // Flag to alternate direction of traversal

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            List<Integer> currentLevel = new LinkedList<>();

            // Process each node at the current level
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                // Add node value based on the current direction
                if (leftToRight) {
                    currentLevel.add(node.val);  // Left to right
                } else {
                    currentLevel.add(0, node.val);  // Right to left
                }

                // Enqueue left and right children if they exist
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }

            result.add(currentLevel);
            leftToRight = !leftToRight;  // Toggle the direction for the next level
        }

        return result;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        // If the root is null, return null as there's nothing to connect
        if (root == null) {
            return root;
        }

        // Initialize a queue for level order traversal
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        // Process nodes level by level
        while (!queue.isEmpty()) {
            int levelSize = queue.size(); // Get the number of nodes at the current level

            // Iterate through nodes at the current level
            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();

                // Set the next pointer for all nodes except the last node at the level
                if (i < levelSize - 1) {
                    node.next = queue.peek();  // Next node at the same level
                } else {
                    node.next = null;  // Last node points to null
                }

                // Enqueue left and right children for the next level
                if (node.left != null) {
                    queue.offer(node.left);
                }

                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        // Return the root of the tree with updated next pointers
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            depth++;

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                
                // Check if the current node is a leaf node
                if (node.left == null && node.right == null) {
                    return depth;
                }

                // Insert the children of the current node to the queue
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return depth;
    }
}

class Solution {
    public int[] numsSameConsecDiff(int n, int k) {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        // Start numbers from 1 to 9 (no leading zeros)
        for (int i = 1; i <= 9; i++) {
            queue.offer(i);
        }

        while (!queue.isEmpty()) {
            int num = queue.poll();

            // A n-digit built, add it to the result
            if (String.valueOf(num).length() == n) {
                result.add(num);
                continue;
            }

            int lastDigit = num % 10;

            // Try adding lastDigit + k if it's a valid digit (0-9)
            if (lastDigit + k <= 9) {
                queue.offer(num * 10 + (lastDigit + k));
            }

            // Try adding lastDigit - k if it's a valid digit (0-9)
           if (k > 0 && lastDigit - k >= 0) {
                queue.offer(num * 10 + (lastDigit - k));
            }
        }

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderHelper(root, result);

        return result;
    }

    private static void inorderHelper(TreeNode node, List<Integer> result) {
        // Base case
        if (node == null) {
            return;
        }

        // Traverse the left subtree
        inorderHelper(node.left, result);
        // Visit the current node
        result.add(node.val);
        // Traverse the right subtree
        inorderHelper(node.right, result);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        preorderHelper(root, result);
        
        return result;
    }

    private static void preorderHelper(TreeNode node, List<Integer> result) {
        // Base case
        if (node == null) {
            return;
        }

        // Visit the current node
        result.add(node.val);
        // Traverse the left subtree
        preorderHelper(node.left, result);
        // Traverse the right subtree
        preorderHelper(node.right, result);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorderHelper(root, result);
        return result;
    }

    private static void postorderHelper(TreeNode root, List<Integer> result) {
        // Base case
        if (root == null) {
            return;
        }

        // Traverse the left subtree
        postorderHelper(root.left, result);
        // Traverse the right subtree
        postorderHelper(root.right, result);
        // Visit the current node
        result.add(root.val);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        // Base case
        if (root == null) {
            return root;
        }

        // Swap the left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // Recursively invert the left and right subtrees
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        // Base case
        if (root == null) {
            return 0;
        }

        // Recursively calculate the left subtree depth
        int leftDepth = maxDepth(root.left);
        // Recursively calculate the right subtree depth
        int rightDepth = maxDepth(root.right);

        // The current node depth equals to the maximum left or right subtree depth plus 1
        return Math.max(leftDepth, rightDepth) + 1;
        
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private static boolean isValidBSTHelper(TreeNode node, long min, long max) {
        // Base case 
        if (node == null) {
            return true;
        }

        if (node.val <= min || node.val >= max) {
            return false;
        }

        // Recursively check the left (with updated upper limit) and right (with updated lower limit)
        return isValidBSTHelper(node.left, min, node.val) && isValidBSTHelper(node.right, node.val, max);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        // Return false if the node is null
        if (root == null) {
            return false;
        }

        // Check if current node is a leaf node
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }

        // Recursively check left and right subtrees with the reduced target
        targetSum -= root.val; // Reduce the target sum by the current node's value
        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        findPaths(root, targetSum, new ArrayList<>(), result);
        return result;
    }

    private void findPaths(TreeNode node, int remainingSum, List<Integer> currentPath, List<List<Integer>> result) {
        // Base case: return if the node is null
        if (node == null) return;

        // Add the current node's value to the path
        currentPath.add(node.val);

        // If it's a leaf node and the remaining sum equals the node's value, add the path to the result
        if (node.left == null && node.right == null && node.val == remainingSum) {
            result.add(new ArrayList<>(currentPath));  // Add a copy of current path
        } else {
            // Recursively explore left and right subtrees, updating the remaining sum
            findPaths(node.left, remainingSum - node.val, currentPath, result);
            findPaths(node.right, remainingSum - node.val, currentPath, result);
        }

        // Backtrack: remove the current node from the path
        currentPath.remove(currentPath.size() - 1);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Long, Integer> prefixSumMap = new HashMap<>();
        // Base case: a path with current sum matches target sum exitst at the root
        prefixSumMap.put(0L, 1);

        return pathSumRecursive(root, 0, targetSum, prefixSumMap);
    }

    private static int pathSumRecursive(TreeNode node, long currentSum, int targetSum, Map<Long, Integer> prefixSumMap) {
        if (node == null) {
            return 0;
        }

        // Update the current sum
        currentSum += node.val;

        // Calculate the number of valid paths ending at this node
        int pathCount = prefixSumMap.getOrDefault(currentSum - targetSum, 0);

        // Add the current sum to the map
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);

        // Recur for left and right sub-trees
        pathCount += pathSumRecursive(node.left, currentSum, targetSum, prefixSumMap);
        pathCount += pathSumRecursive(node.right, currentSum, targetSum, prefixSumMap);

        // Remove the current path sum to backtrack
        prefixSumMap.put(currentSum, prefixSumMap.get(currentSum) - 1);

        return pathCount;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = Integer.parseInt(in.nextLine().trim());
        int[] nums = Arrays.stream(in.nextLine().trim().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        // Build a ternary tree based on nums array
        TreeNode root = buildeTernaryTree(nums);

        // Calculate max heat value
        int maxHeatValue = getMaxHeatValue(root);

        // Output result
        System.out.println(maxHeatValue);

    }

    private static int getMaxHeatValue(TreeNode node) {
        return dfs(node, 0);
    }

    private static int dfs(TreeNode node, int currentSum) {
        if (node == null) {
            return 0; // Return 0 for null nodes
        }

        // Add the current node's value to the running sum
        currentSum += node.val;

        // If it's a leaf node, return the current sum
        if (node.left == null && node.mid == null && node.right == null) {
            return currentSum;
        }

        // Recursively compute the maximum left, mid, and right subtree
        int leftSum = dfs(node.left, currentSum);
        int midSum = dfs(node.mid, currentSum);
        int rightSum = dfs(node.right, currentSum);

        return Math.max(leftSum, Math.max(midSum, rightSum));

    }

    private static TreeNode buildeTernaryTree(int[] nums) {
        if (nums.length == 0 || nums[0] == -1) {
            return null;
        }

        TreeNode root = new TreeNode(nums[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        int i = 1;
        while (i < nums.length) {
            TreeNode current = queue.poll();

            if (nums[i] != -1) {
                current.left = new TreeNode(nums[i]);
                queue.offer(current.left);
            }
            i++;

            if (i < nums.length && nums[i] != -1) {
                current.mid = new TreeNode(nums[i]);
                queue.offer(current.mid);
            }
            i++;

            if (i < nums.length && nums[i] != -1) {
                current.right = new TreeNode(nums[i]);
                queue.offer(current.right);
            }
            i++;
        }

        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left, mid, right;

    public TreeNode(int val) {
        this.val = val;
        this.left = this.mid = this.right = null;
    }
}

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;

        for (int bill : bills) {
            if (bill == 5) {
                five++;  // Collect 5 dollar bill
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;  // 5 dollars for change
                ten++; // Collect 10 dollar bill
            } else if (bill == 20) {
                if (five > 0 && ten > 0) {
                    five--; // Give one 5 dollar bill
                    ten--;  // Give one 10 dollar bill
                } else if (five >= 3) {
                    five -= 3; // Give three five dollar bills
                } else {
                    return false;
                }
            }
        }

        return true;
    }
}

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g); // Sort greed factors
        Arrays.sort(s); // Sort cookie sizes
        
        int i = 0, j = 0, count = 0;
        while (i < g.length && j < s.length) {
            // Assign cookie j to child i if it satisfies greed factor
            if (g[i] <= s[j]) {
                count++;
                i++; // Move to next child
            }
            j++;
            // if (g[i] <= s[j]) {
            //     count++;
            //     i++;
            //     j++;
            // } else {
            //     j++;
            // }
        }

        return count;
    }
}

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        // Sort the array in an ascending order to facilitate pairing
        Arrays.sort(people);

        // Initialize two pointers
        int left = 0, right = people.length - 1;
        int boats = 0; // Record the number of boats
        while (left <= right) {
            // The current lightest and the heaviest person can share the boat
            if (people[left] + people[right] <= limit) {
                left++;
                // right--;
                // boat++;
            }
            right--;
            boats++;
        }

        return boats;
    }
}

class Solution {
    public boolean validPalindrome(String s) {
        // Initialize two pointers
        int left = 0, right = s.length() - 1;
        while (left <= right) {
            // If characters don't match, try skipping either left character or the right character
            if (s.charAt(left) != s.charAt(right)) {
                return isPalindrome(left + 1, right, s) || isPalindrome(left, right - 1, s);
            }
            left++;
            right--;
        }

        return true;
    }

    private static boolean isPalindrome(int left, int right, String s) {
        while (left <= right) {
            if (s.charAt(left) != s.charAt(right)) {
                // If any characters don't match, it's not a palindrome
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}

class Solution {
    public int findLongestChain(int[][] pairs) {
        // Sort the pairs in an ascending order based on the second element of each pair
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

        // Initialize the second element of the last pair
        int lastEnd = Integer.MIN_VALUE;
        int maxLength = 0;
        for (int[] pair : pairs) {
            if (pair[0] > lastEnd) {
                maxLength++; // Increase the maximum length
                lastEnd = pair[1]; // Update the lastEnd for next loop
            }
        }

        return maxLength;
    }
}

class Solution {
    public int minAddToMakeValid(String s) {
        int unmatchedOpenCount = 0; // Tracks unmatched opening parentheses
        int neededOpenCount = 0; // Tracks needed opening parentheses to balance closing parentheses

        for (char c : s.toCharArray()) {
            if (c == '(') {
                // Found an opening parenthesis
                unmatchedOpenCount++;
            } else {
                if (unmatchedOpenCount > 0) {
                    // Balance the opening parenthesis
                    unmatchedOpenCount--;
                } else {
                    // Need an opening parenthesis to balance the closing parenthesis
                    neededOpenCount++;
                }
            }
        }

        // Return the minimum number of moves required
        return unmatchedOpenCount + neededOpenCount;
    }
}

class Solution {
    public String smallestSubsequence(String s) {
        Map<Character, Integer> charMap = new HashMap<>();
        Set<Character> charSet = new HashSet<>();
        Stack<Character> charStack = new Stack<>();

        // Count the frequency of each character
        for (char c : s.toCharArray()) {
            charMap.put(c, charMap.getOrDefault(c, 0) + 1);
        }

        for (char c : s.toCharArray()) {
            if (!charSet.contains(c)) {
                // Ensure the smallest lexicographical order by removing higher characters that will appear again
                while (!charStack.isEmpty() && c < charStack.peek() && charMap.get(charStack.peek()) > 0) {
                    // Remove the top element from the stack
                    // Character popped = charStack.pop();
                    // Remove the popped element from the charSet
                    // charSet.remove(popped);
                    charSet.remove(charStack.pop());
                }

                charStack.push(c);
                charSet.add(c);
            }

            // Decrease the frequency of current character
            charMap.put(c, charMap.get(c) - 1);
        }

        // Build the result from the char Stack
        StringBuilder builder = new StringBuilder();
        for (char c : charStack) {
            builder.append(c);
        }

        return builder.toString();
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = Arrays.stream(gas).sum();
        int totalCost = Arrays.stream(cost).sum();

        if (totalGas < totalCost) {
            return -1;
        }

        int tank = 0, startIndex = 0;
        // Find the starting Index
        for (int i = 0; i < gas.length; i++) {
            tank += gas[i] - cost[i];
            if (tank < 0) {
                // Reset tank and update the startIndex
                tank = 0;
                startIndex = i + 1;
            }
        }

        return startIndex;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        // Initialize to the last index, representing the goal
        int goal = n - 1; // Start from the end of the nums
        
        // Traverse from the second-to-last index backwards
        for (int i = n - 2; i >= 0; i--) {
            // Update currentEnd if the current index can reach it
            if (i + nums[i] >= goal) {
                goal = i;
            }
        }

        // Return true if the start index (0) can reach the last index
        return goal == 0;
    }
}

class Solution {
    public int jump(int[] nums) {
        int jumps = 0; // Track the number of jumps
        int currentEnd = 0; // Track the end of the range for the current jump
        int farthest = 0; // Track the farthest point that can be reached

        for (int i = 0; i < nums.length - 1; i++) {
            // Update the farthest point
            farthest = Math.max(farthest, i + nums[i]);

            if (i == currentEnd) { // Reached the end of current jump range
                jumps++; // Increment the jumps count
                currentEnd = farthest; // Update the end of range for the current jump
            }
        }

        return jumps;
    }
}

class Solution {
    // top-left is (0, 0), x represents row, y represents column
    // Direction representing movement: up, down, left, right
    private static final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int numIslands(char[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        int totalIslands = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // If a land cell is found, it represents a new island
                if (grid[i][j] == '1') {
                    totalIslands++;
                    // Recursively mark all cells in this island as visited
                    visitIslandDFS(grid, i, j);
                }
            }
        }

        return totalIslands;
    }

    private static void visitIslandDFS(char[][] grid, int x, int y) {
        // Check for out-of-bounds
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
            return;
        }

        // Check if it's a water cell
        if (grid[x][y] == '0') {
            return;
        }

        // Mark the cell as visited by changing it to '0'
        grid[x][y] = '0';

        // Explore all four adjacent directions
        for (int[] direction : DIRECTIONS) {
            visitIslandDFS(grid, x + direction[0], y + direction[1]);
        }
    }
}

class Solution {
    // top-left is (0, 0), x represents row, y represents column
    // Direction representing movement: up, down, left, right
    private static final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    
    public int maxAreaOfIsland(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;

        int maxIslandArea = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // If a land is found, it represents a new island
                if (grid[i][j] == 1) {
                    maxIslandArea = Math.max(maxIslandArea, visitIslandDFS(grid, i, j));
                }
            }
        }

        return maxIslandArea;
    }

    private static int visitIslandDFS(int[][] grid, int x, int y) {
        // Check for out-of-bounds
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length) {
            return 0;
        }

        // Check if it is a water cell or visited
        if (grid[x][y] == 0) {
            return 0;
        }

        // Mark the current cell as visited by changing it to water cell
        grid[x][y] = 0;

        int area = 1;
        // Recursively visit all neighboring cells
        for (int[] direction : DIRECTIONS) {
            area += visitIslandDFS(grid, x + direction[0], y + direction[1]);
        }

        return area;
    }
}

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        
        return result;
    }

    private static void backtrack(int[] candidates, int target, int start, List<Integer> combination, List<List<Integer>> result) {
        // Found a combination if the remaining target matches 0
        if (target == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }

        if (target < 0) {
            return;
        }

        // Iterate the candidates array to find the combination
        for (int i = start; i < candidates.length; i++) {
            // Skip the candidate greater than the remaining target
            if (candidates[i] > target) {
                continue;
            }

            // Add the current element to the combination array
            combination.add(candidates[i]);

            // Recur with the updated combination array and the remaining target
            backtrack(candidates, target - candidates[i], i, combination, result);

            // Backtrack to explore other possibilities
            combination.remove(combination.size() - 1);
        }
    }
}

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    static int minServer = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // Read input and transform it to a decreasing array
        int[] powers = Arrays.stream(in.nextLine().trim().split(" "))
                .map(Integer::parseInt)
                .sorted(Comparator.reverseOrder())
                .mapToInt(Integer::intValue)
                .toArray();

        // Read the target power
        int target = Integer.parseInt(in.nextLine().trim());

        // Generate all power combinations with minimum servers
        List result = generatePowerCombinations(powers, target);

        // Sort the combination result
        sortCombinations(result);

        // Format and print the result
        formatOutput(result);
    }

    private static List generatePowerCombinations(int[] nums, int target) {
        List result = new ArrayList<>();

        backtrack(nums, target, 0, new ArrayList<>(), result);

        return result;
    }

    private static void backtrack(int[] nums, int target, int start, List<Integer> current, List result) {
        if (target == 0) {
            // The nums is in decreasing order, the first combinations must be with minimum servers
            if (result.isEmpty()) {
                minServer = current.size();
            }
            result.add(new ArrayList<>(current));
            return;
        }

        // Prune branches
        if (target < 0 || (!result.isEmpty() && current.size() >= minServer)) {
            return;
        }


        for (int i = start; i < nums.length; i++) {
            current.add(nums[i]); // Add the current number to the current subset

            // Recursively explore further with the reduced target
            backtrack(nums, target - nums[i], i, current, result);

            // Backtrack to explore other options
            current.remove(current.size() - 1);
        }
    }

    private static void sortCombinations(List result) {
        for (List<Integer> list : result) {
            list.sort(Comparator.comparingInt(a -> a));
        }
    }

    private static void formatOutput(List result) {
        if (result.isEmpty()) {
            System.out.println("-1");
            return;
        }

        for (List<Integer> list : result) {
            String joinedString = list.stream()
                    .map(Object::toString) // Convert each integer to string
                    .collect(Collectors.joining(" ")); // Join with a space delimiter

            System.out.println(joinedString);
        }
    }
}

class Solution {
    // top-left is (0, 0), x represents row, y represents column
    // Direction representing movement: up, down, left, right
    private static final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (visitBoardDFS(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    private static boolean visitBoardDFS(char[][] board, String word, int x, int y, int index) {
        // Check for out-of-bounds
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return false;
        }

        // Check if the current cell matches the character at current index
        if (board[x][y] != word.charAt(index)) {
            return false;
        }

        // Check if it reach end of the word
        if (index == word.length() - 1) {
            return true;
        }

        char temp = board[x][y];
        board[x][y] = '#'; // Mark the current cell as visited by changing it to '#'

        // boolean result = false;
        // Recursively check all 4 adjacent cells
        for (int[] direction : DIRECTIONS) {
            // result = result || visitBoardDFS(board, word, x + direction[0], y + direction[1], index + 1);
            if (visitBoardDFS(board, word, x + direction[0], y + direction[1], index + 1)) {
                return true; // If a valid path is found, no need to check other drections
            }
        }

        // Backtrack by replacing the cell with its original cell
        board[x][y] = temp;

        // return result;
        return false;
    }
}

class Solution {
    public int maxUniqueSplit(String s) {
        return splitAndCount(s, 0, new HashSet<>());
    }

    private static int splitAndCount(String s, int start, Set<String> set) {
        // Base case, return the size of set when reach the end of the string
        if (start == s.length()) {
            return set.size();
        }

        int count = 0;
        for (int i = start + 1; i <= s.length(); i++) {
            String subStr = s.substring(start, i);

            // Only proceed if the substring is unique
            if (set.add(subStr)) {
                count = Math.max(count, splitAndCount(s, i, set));

                // Backtrack by removing the subStr from the set
                set.remove(subStr);
            }
        }

        return count;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String s = in.nextLine().trim();

        List<String> palindromes = generatePalindromes(s);

        System.out.println(palindromes);
    }

    private static List<String> generatePalindromes(String s) {
        // Count the frequency of each character
        Map<Character, Integer> charCount = new HashMap<>();
        for (char c : s.toCharArray()) {
            charCount.put(c, charCount.getOrDefault(c, 0) + 1);
        }

        // Check if the string can form a palindrome
        String mid = "";
        List<Character> halfChars = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : charCount.entrySet()) {
            char key = entry.getKey();
            int count = entry.getValue();

            if (count % 2 == 1) {
                // If mid is not empty, meaning the odd count of characters is greater than 1
                if (!mid.isEmpty()) {
                    return new ArrayList<>();
                }
                mid = String.valueOf(key);
            }

            for (int i = 0; i < count / 2; i++) {
                halfChars.add(key);
            }
        }

        List<String> result = new ArrayList<>();
        boolean[] used = new boolean[halfChars.size()];
        backtrack(halfChars, mid, new StringBuilder(), used, result);

        return result;
    }

    private static void backtrack(List<Character> halfChars, String mid, StringBuilder path, boolean[] used, List<String> result) {
        if (path.length() == halfChars.size()) {
            result.add(new String(path) + mid + new StringBuilder(path).reverse());
            return;
        }

        for (int i = 0; i < halfChars.size(); i++) {
            if (used[i] || (i > 0 && halfChars.get(i).equals(halfChars.get(i - 1)) && !used[i - 1])) {
                continue; // Skip duplicates
            }

            // Add the current character to the path
            path.append(halfChars.get(i));
            // Mark the current character as used
            used[i] = true;

            backtrack(halfChars, mid, path, used, result);

            // Backtrack: Remove the last element of path for further exploration
            path.setLength(path.length() - 1);
            used[i] = false;
        }
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), subsets);
        return subsets;
    }

    private static void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> subsets) {
        // Add the current subset to the result
        subsets.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            // Include the nums[i] in the current subset
            current.add(nums[i]);

            // Recurse to explore further elements
            backtrack(nums, i + 1, current, subsets);

            // Backtrack by removing the last added element
            current.remove(current.size() - 1);
        }
    }
}

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        // Sort the array to ensure duplicate elements are adjacent
        Arrays.sort(nums);
        backtrack(nums, 0, new ArrayList<>(), subsets);
        return subsets;
    }

    private static void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> subsets) {
        // Add the current subset to the subsets
        subsets.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            // Skip if the current number is equal to the previous number
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }

            // Include the current number to the current subset
            current.add(nums[i]);

            backtrack(nums, i + 1, current, subsets);

            // Backtrack to explore other options
            current.remove(current.size() - 1);
        }
    }
}