class Solution {
    private int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public int maxAreaOfIsland(int[][] grid) {
        int ans = 0;
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == 1) {
                    ans = Math.max(ans, dfs(grid, row, col));
                }
            }
        }
        return ans;
    }

    private int dfs(int[][] grid, int row, int col) {
        grid[row][col] = 0;
        int ans = 1;
        for (int[] direction : DIRECTIONS) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (!isOutOfBound(grid, newRow, newCol) && grid[newRow][newCol] != 0) {
                ans += dfs(grid, newRow, newCol);
            }
        }
        return ans;
    }

    private boolean isOutOfBound(int[][] grid, int row, int col) {
        return row < 0 || row >= grid.length || col < 0 || col >= grid[0].length;
    }
}

class Solution {
    private int ans = 0;

    public int goodNodes(TreeNode root) {
        dfs(root, Integer.MIN_VALUE);
        return ans;
    }

    private void dfs(TreeNode node, int currMax) {
        if (node == null) {
            return;
        }
        if (node.val >= currMax) {
            ans += 1;
        }
        dfs(node.left, Math.max(node.val, currMax));
        dfs(node.right, Math.max(node.val, currMax));
    }
}

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        if (position.length == 0) {
            return 0;
        }
        double[][] posTravelTime = new double[position.length][2];
        for (int i = 0; i < position.length; i++) {
            posTravelTime[i][0] = (double) position[i];
            posTravelTime[i][1] = ((double) (target - position[i])) / speed[i];
        }
        Arrays.sort(posTravelTime, (a, b) -> Double.compare(b[0], a[0]));
        int ans = 1;
        double currFleetTimeBound = posTravelTime[0][1];
        for (int i = 1; i < posTravelTime.length; i++) {
            if (posTravelTime[i][1] <= currFleetTimeBound) {
                continue;
            } else {
                ans += 1;
                currFleetTimeBound = posTravelTime[i][1];
            }
        }
        return ans;
    }
}

class Solution {
    public String removeStars(String s) {
        StringBuilder ans = new StringBuilder();
        int starCount = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '*') {
                starCount += 1;
            } else {
                if (starCount == 0) {
                    ans.append(s.charAt(i));
                } else {
                    starCount -= 1;
                }
            }
        }
        return ans.reverse().toString();
    }
}

class Solution {
    public long numberOfWays(String s) {
        long picksEndWith0 = 0, picksEndWith1 = 0, ans = 0;
        int zeroCount = 0, oneCount = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '0') {
                ans += picksEndWith1;
                picksEndWith0 = picksEndWith0 + oneCount;
                zeroCount += 1;
            } else {
                ans += picksEndWith0;
                picksEndWith1 = picksEndWith1 + zeroCount;
                oneCount += 1;
            }
        }
        return ans;
    }
}

class TicTacToe {
    private int[][] rowCount;
    private int[][] colCount;
    private int[] diagCount;
    private int[] antiDiagCount;
    private int size;

    public TicTacToe(int n) {
        rowCount = new int[n][2];
        colCount = new int[n][2];
        diagCount = new int[2];
        antiDiagCount = new int[2];
        size = n;
    }

    public int move(int row, int col, int player) {
        updateCount(row, col, player);
        return isWin(row, col, player) ? player : 0;
    }

    private void updateCount(int row, int col, int player) {
        rowCount[row][player - 1] += 1;
        colCount[col][player - 1] += 1;
        if (row == col) {
            diagCount[player - 1] += 1;
        }
        if (row + col == size - 1) {
            antiDiagCount[player - 1] += 1;
        }
    }

    private boolean isWin(int row, int col, int player) {
        return rowCount[row][player - 1] == size || colCount[col][player - 1] == size
                || diagCount[player - 1] == size || antiDiagCount[player - 1] == size;
    }

}

class Trie {
    private static class TrieNode {
        Map<Character, TrieNode> nodeMap;
        int wordCount;
        int prefixCount;

        TrieNode(Map<Character, TrieNode> _nodeMap) {
            this.nodeMap = _nodeMap;
        }
    }

    private TrieNode root;

    public Trie() {
        root = new TrieNode(new HashMap<>());
    }

    public void insert(String word) {
        TrieNode ptr = root;
        for (int i = 0; i < word.length(); i++) {
            ptr.nodeMap.putIfAbsent(word.charAt(i), new TrieNode(new HashMap<>()));
            ptr = ptr.nodeMap.get(word.charAt(i));
            ptr.prefixCount += 1;
        }
        ptr.wordCount += 1;
    }

    public int countWordsEqualTo(String word) {
        TrieNode foundNode = findPrefix(word);
        return foundNode != null ? foundNode.wordCount : 0;

    }

    public int countWordsStartingWith(String prefix) {
        TrieNode foundNode = findPrefix(prefix);
        return foundNode != null ? foundNode.prefixCount : 0;
    }

    public void erase(String word) {
        TrieNode ptr = root;
        for (int i = 0; i < word.length(); i++) {
            ptr = ptr.nodeMap.get(word.charAt(i));
            ptr.prefixCount -= 1;
        }
        ptr.wordCount -= 1;
    }

    private TrieNode findPrefix(String prefix) {
        TrieNode ptr = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (!ptr.nodeMap.containsKey(prefix.charAt(i))) {
                return null;
            }
            ptr = ptr.nodeMap.get(prefix.charAt(i));
        }
        return ptr;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                return new int[] { left + 1, right + 1 };
            } else if (nums[left] + nums[right] < target) {
                left += 1;
            } else {
                right -= 1;
            }
        }
        return new int[0];
    }
}

class Solution {
    public int pairSum(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow = reverse(slow);
        fast = head;
        int ans = Integer.MIN_VALUE;
        while (slow != null) {
            int currSum = slow.val + fast.val;
            ans = Math.max(ans, currSum);
            slow = slow.next;
            fast = fast.next;
        }
        return ans;
    }

    private ListNode reverse(ListNode node) {
        ListNode prev = null, curr = node;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

class Solution {
    public String multiply(String num1, String num2) {
        int m = num1.length(), n = num2.length();
        int[] product = new int[m + n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int pos1 = i + j + 1, pos2 = i + j;
                int multiple = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                int sum = multiple + product[pos1];
                product[pos1] = sum % 10;
                product[pos2] += sum / 10;
            }
        }
        StringBuilder ans = new StringBuilder();
        for (int digit : product) {
            if (!(ans.length() == 0 && digit == 0)) {
                ans.append(digit);
            }
        }
        return ans.length() == 0 ? "0" : ans.toString();
    }
}