class Solution {
    public int longestLine(int[][] mat) {
        int ans = 0, m = mat.length, n = mat[0].length;
        for (int i = 0; i < m; i++) {
            int prev = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    prev += 1;
                    ans = Math.max(prev, ans);
                } else {
                    prev = 0;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            int prev = 0;
            for (int j = 0; j < m; j++) {
                if (mat[j][i] == 1) {
                    prev += 1;
                    ans = Math.max(prev, ans);
                } else {
                    prev = 0;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            int prev = 0, row = i, col = 0;
            while (row < m && col < n) {
                if (mat[row][col] == 1) {
                    prev += 1;
                    ans = Math.max(ans, prev);
                } else {
                    prev = 0;
                }
                row += 1;
                col += 1;
            }
        }
        for (int i = 1; i < n; i++) {
            int prev = 0, row = 0, col = i;
            while (row < m && col < n) {
                if (mat[row][col] == 1) {
                    prev += 1;
                    ans = Math.max(ans, prev);
                } else {
                    prev = 0;
                }
                row += 1;
                col += 1;
            }
        }
        for (int i = 0; i < m; i++) {
            int prev = 0, row = i, col = n - 1;
            while (row < m && col >= 0) {
                if (mat[row][col] == 1) {
                    prev += 1;
                    ans = Math.max(ans, prev);
                } else {
                    prev = 0;
                }
                row += 1;
                col -= 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            int prev = 0, row = 0, col = i;
            while (row < m && col >= 0) {
                if (mat[row][col] == 1) {
                    prev += 1;
                    ans = Math.max(ans, prev);
                } else {
                    prev = 0;
                }
                row += 1;
                col -= 1;
            }
        }
        return ans;
    }
}

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        int count = 0, currRow = 0, ptr = 0, size = 0;
        while (currRow < rows) {
            while (ptr < sentence.length && size + sentence[ptr].length() + 1 <= cols + 1) {
                size += sentence[ptr].length() + 1;
                ptr += 1;
            }
            if (ptr == sentence.length) {
                count += 1;
                ptr = 0;
            } else {
                size = 0;
                currRow += 1;
            }
        }
        return count;
    }
}

class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int[] largeCount = new int[security.length];
        int[] smallCount = new int[security.length];
        for (int i = 1; i < largeCount.length; i++) {
            if (security[i] <= security[i - 1]) {
                largeCount[i] = largeCount[i - 1] + 1;
            } else {
                largeCount[i] = 0;
            }
        }
        for (int i = smallCount.length - 2; i >= 0; i--) {
            if (security[i] <= security[i + 1]) {
                smallCount[i] = smallCount[i + 1] + 1;
            } else {
                smallCount[i] = 0;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < largeCount.length; i++) {
            if (smallCount[i] >= time && largeCount[i] >= time) {
                ans.add(i);
            }
        }
        return ans;
    }
}

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left += 1;
            right -= 1;
        }
        for (int i = 1; i < nums.length; i += 2) {
            swap(nums, i - 1, i);
        }
    }

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

class Solution {
    private List<Integer> sides;
    private List<Integer> center;

    public List<String> findStrobogrammatic(int n) {
        if (n == 1) {
            return new ArrayList<>(Arrays.asList("0", "1", "8"));
        }
        sides = new ArrayList<>(Arrays.asList(0, 1, 6, 8, 9, 6, 8, 9, 1, 0));
        center = new ArrayList<>(Arrays.asList(0, 1, 8));
        List<String> ans = new ArrayList<>();
        backtrack(ans, new StringBuilder(), new StringBuilder(), 0, n);
        return ans;
    }

    private void backtrack(List<String> ans, StringBuilder left, StringBuilder right, int pos, int n) {
        if (pos == n / 2) {
            StringBuilder reverse = new StringBuilder(right);
            reverse.reverse();
            if (n % 2 == 0) {
                ans.add(left.toString() + reverse.toString());
            } else {
                for (int digit : center) {
                    ans.add(left.toString() + digit + reverse.toString());
                }
            }
            return;
        }
        for (int i = 0; i < sides.size() / 2; i++) {
            if (pos == 0 && i == 0) {
                continue;
            }
            int digit = sides.get(i);
            int pairDigit = sides.get(sides.size() - 1 - i);
            left.append(digit);
            right.append(pairDigit);
            backtrack(ans, left, right, pos + 1, n);
            left.setLength(left.length() - 1);
            right.setLength(right.length() - 1);
        }
    }
}

class Solution {
    public int shortestWordDistance(String[] wordsDict, String word1, String word2) {
        Map<String, List<Integer>> wordIndex = new HashMap<>();
        for (int i = 0; i < wordsDict.length; i++) {
            String word = wordsDict[i];
            wordIndex.putIfAbsent(word, new ArrayList<>());
            List<Integer> wordList = wordIndex.get(word);
            if (wordList.size() == 0) {
                wordList.add(Integer.MAX_VALUE);
                wordList.add(i);
            } else {
                int distanceToLast = i - wordList.get(wordList.size() - 1);
                wordList.set(0, Math.min(distanceToLast, wordList.get(0)));
                wordList.add(i);
            }
        }
        if (word1.equals(word2)) {
            return wordIndex.get(word1).get(0);
        } else {
            List<Integer> word1List = wordIndex.get(word1);
            List<Integer> word2List = wordIndex.get(word2);
            int ptrOne = 1, ptrTwo = 1, ans = Integer.MAX_VALUE;
            while (ptrOne < word1List.size() && ptrTwo < word2List.size()) {
                int word1Index = word1List.get(ptrOne), word2Index = word2List.get(ptrTwo);
                ans = Math.min(ans, Math.abs(word1Index - word2Index));
                if (word1List.get(ptrOne) < word2List.get(ptrTwo)) {
                    ptrOne += 1;
                } else {
                    ptrTwo += 1;
                }
            }
            return ans;
        }
    }
}

class Solution {
    public void reverseWords(char[] s) {
        int left = 0, right = s.length - 1;
        reverse(s, left, right);
        for (left = 0; left < s.length; left++) {
            if (s[left] == ' ') {
                continue;
            }
            right = left;
            while (right < s.length && s[right] != ' ') {
                right += 1;
            }
            right -= 1;
            reverse(s, left, right);
            left = right;
        }
    }

    private void reverse(char[] s, int left, int right) {
        while (left < right) {
            swap(s, left, right);
            left += 1;
            right -= 1;
        }
    }

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

class MyCalendar {
    TreeMap<Integer, Integer> intervals;

    public MyCalendar() {
        intervals = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Integer prev = intervals.floorKey(start), next = intervals.ceilingKey(start);
        if ((prev == null || intervals.get(prev) <= start) && (next == null || next >= end)) {
            intervals.put(start, end);
            return true;
        }
        return false;
    }
}

class Solution {
    public long appealSum(String s) {
        Integer[] lastIdx = new Integer[26];
        long ans = 0;
        for (int i = 0; i < s.length(); i++) {
            char currLetter = s.charAt(i);
            int left = i - (lastIdx[currLetter - 'a'] != null ? lastIdx[currLetter - 'a'] : -1);
            int right = s.length() - i;
            ans += left * right;
            lastIdx[currLetter - 'a'] = i;
        }
        return ans;
    }
}

class Solution {
    public Node cloneTree(Node root) {
        if (root == null) {
            return null;
        }
        Node newRoot = new Node(root.val, new ArrayList<>());
        dfs(root, newRoot);
        return newRoot;
    }

    private void dfs(Node ptr, Node newPtr) {
        for (Node child : ptr.children) {
            Node newChild = new Node(child.val, new ArrayList<>());
            newPtr.children.add(newChild);
            dfs(child, newChild);
        }
    }
}