class Solution {
    private int totalSum;
    private long ans;

    public int maxProduct(TreeNode root) {
        totalSum = helper(root);
        dfs(root);
        return (int) (ans % (1000000007));
    }

    private int helper(TreeNode node) {
        if (node == null)
            return 0;
        return node.val + helper(node.left) + helper(node.right);
    }

    private int dfs(TreeNode node) {
        if (node == null)
            return 0;
        long leftSum = dfs(node.left);
        long rightSum = dfs(node.right);
        ans = Math.max(ans, Math.max(leftSum * (totalSum - leftSum), rightSum * (totalSum - rightSum)));
        return node.val + (int) leftSum + (int) rightSum;
    }
}

class Solution {
    private int ans;

    public int maxAncestorDiff(TreeNode root) {
        helper(root, root.val, root.val);
        return ans;
    }

    private void helper(TreeNode node, int currMax, int currMin) {
        if (node == null)
            return;
        ans = Math.max(ans, Math.max(Math.abs(node.val - currMax), Math.abs(node.val - currMin)));
        int newMax = Math.max(currMax, node.val), newMin = Math.min(currMin, node.val);
        helper(node.left, newMax, newMin);
        helper(node.right, newMax, newMin);
    }
}

class Solution {
    public int minimumAverageDifference(int[] nums) {
        long firstPartSum = 0, secondPartSum = 0;
        for (int num : nums) {
            secondPartSum += num;
        }
        long minDiff = Integer.MAX_VALUE, minIndex = -1;
        for (int i = 0; i < nums.length; i++) {
            firstPartSum += nums[i];
            secondPartSum -= nums[i];
            long currDiff = i == nums.length - 1 ? firstPartSum / nums.length
                    : Math.abs(firstPartSum / (i + 1) - secondPartSum / (nums.length - i - 1));
            if (currDiff < minDiff) {
                minDiff = currDiff;
                minIndex = i;
            }
        }
        return (int) minIndex;
    }
}

class Solution {
    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) {
            return false;
        }
        Map<Character, Integer> letterCountWord1 = new TreeMap<>();
        Map<Character, Integer> letterCountWord2 = new TreeMap<>();
        for (char letter : word1.toCharArray()) {
            letterCountWord1.put(letter, letterCountWord1.getOrDefault(letter, 0) + 1);
        }
        for (char letter : word2.toCharArray()) {
            letterCountWord2.put(letter, letterCountWord2.getOrDefault(letter, 0) + 1);
        }
        List<Character> word1LetterList = new ArrayList<>(letterCountWord1.keySet());
        List<Character> word2LetterList = new ArrayList<>(letterCountWord2.keySet());
        if (word1LetterList.size() != word2LetterList.size()) {
            return false;
        }
        Collections.sort(word1LetterList);
        Collections.sort(word2LetterList);
        for (int i = 0; i < word1LetterList.size(); i++) {
            if (word1LetterList.get(i) != word2LetterList.get(i)) {
                return false;
            }
        }
        List<Integer> word1Freq = new ArrayList<>(letterCountWord1.values());
        List<Integer> word2Freq = new ArrayList<>(letterCountWord2.values());
        Collections.sort(word1Freq);
        Collections.sort(word2Freq);
        for (int i = 0; i < word1Freq.size(); i++) {
            if (!word1Freq.get(i).equals(word2Freq.get(i))) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public List<List<Integer>> findWinners(int[][] matches) {
        Map<Integer, int[]> playerHistory = new HashMap<>();
        for (int[] match : matches) {
            playerHistory.putIfAbsent(match[0], new int[2]);
            playerHistory.putIfAbsent(match[1], new int[2]);
            playerHistory.get(match[0])[0] += 1;
            playerHistory.get(match[1])[1] += 1;
        }
        List<Integer> noLosePlayers = new ArrayList<>();
        List<Integer> oneLosePlayers = new ArrayList<>();
        for (Map.Entry<Integer, int[]> entry : playerHistory.entrySet()) {
            if (entry.getValue()[1] == 0) {
                noLosePlayers.add(entry.getKey());
            } else if (entry.getValue()[1] == 1) {
                oneLosePlayers.add(entry.getKey());
            }
        }
        Collections.sort(noLosePlayers);
        Collections.sort(oneLosePlayers);
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(noLosePlayers);
        ans.add(oneLosePlayers);
        return ans;
    }
}

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length, n = maze[0].length;
        Deque<int[]> emptyCells = new ArrayDeque<>();
        int steps = 0;
        Set<String> visited = new HashSet<>();
        emptyCells.offer(entrance);
        visited.add(entrance[0] + "," + entrance[1]);
        int[][] directions = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
        while (!emptyCells.isEmpty()) {
            for (int i = emptyCells.size(); i > 0; i--) {
                int[] currPos = emptyCells.poll();
                for (int[] direction : directions) {
                    int newRow = currPos[0] + direction[0];
                    int newCol = currPos[1] + direction[1];
                    if (!isOutOfBound(m, n, newRow, newCol) && maze[newRow][newCol] == '.'
                            && visited.add(newRow + "," + newCol)) {
                        if (newRow == 0 || newRow == m - 1 || newCol == 0 || newCol == n - 1) {
                            return steps + 1;
                        } else {
                            emptyCells.offer(new int[] { newRow, newCol });
                        }
                    }
                }
            }
            steps += 1;
        }
        return -1;
    }

    private boolean isOutOfBound(int totalRow, int totalCol, int currRow, int currCol) {
        return currRow < 0 || currRow >= totalRow || currCol < 0 || currCol >= totalCol;
    }
}

class Solution {
    public String removeDuplicates(String s) {
        char[] sArray = s.toCharArray();
        int left = 0, right = 1;
        while (right < sArray.length) {
            if (left != -1 && sArray[left] == sArray[right]) {
                left -= 1;
            } else {
                sArray[left + 1] = sArray[right];
                left += 1;
            }
            right += 1;
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i <= left; i++) {
            ans.append(sArray[i]);
        }
        return ans.toString();
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a, b) -> {
            if (a[1] == b[1])
                return 0;
            else if (a[1] < b[1])
                return -1;
            else
                return 1;
        });
        int currEnd = points[0][1], arrowCount = 1;
        for (int[] point : points) {
            if (point[0] > currEnd) {
                arrowCount += 1;
                currEnd = point[1];
            }
        }
        return arrowCount;
    }
}

class Solution {
    public int maximum69Number(int num) {
        char[] digitArray = String.valueOf(num).toCharArray();
        for (int i = 0; i < digitArray.length; i++) {
            if (digitArray[i] == '6') {
                digitArray[i] = '9';
                break;
            }
        }
        return Integer.valueOf(new String(digitArray));
    }
}

class Solution {
    public String reverseVowels(String s) {
        Character[] vowels = new Character[] { 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U' };
        Set<Character> vowelSet = new HashSet<>();
        Collections.addAll(vowelSet, vowels);
        char[] sArray = s.toCharArray();
        int left = 0, right = sArray.length - 1;
        while (left < right) {
            if (!vowelSet.contains(sArray[left])) {
                left += 1;
                continue;
            }
            if (!vowelSet.contains(sArray[right])) {
                right -= 1;
                continue;
            }
            swap(sArray, left, right);
            left += 1;
            right -= 1;
        }
        return new String(sArray);
    }

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