class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int currNum = Math.abs(nums[i]);
            int targetIdx = currNum - 1;
            if (nums[targetIdx] < 0) {
                ans.add(currNum);
            } else {
                nums[targetIdx] = -nums[targetIdx];
            }
        }
        return ans;
    }
}

class Solution {
    public int longestSubstring(String s, int k) {
        return helper(s, 0, s.length() - 1, k);
    }

    private int helper(String s, int left, int right, int k) {
        // 这一行第一个条件left > right其实可以不要, 因为如果left > right, 那么
        // right - left + 1肯定小于k.
        // if (left > right || right - left + 1 < k) {
        // return 0;
        // }
        if (right - left + 1 < k) {
            return 0;
        }
        int[] charCount = new int[26];
        for (int i = left; i <= right; i++) {
            charCount[s.charAt(i) - 'a'] += 1;
        }
        for (int i = left; i <= right; i++) {
            if (charCount[s.charAt(i) - 'a'] >= k) {
                continue;
            }
            int midNext = i + 1;
            while (midNext <= right && charCount[s.charAt(midNext) - 'a'] < k) {
                midNext += 1;
            }
            return Math.max(helper(s, left, i - 1, k), helper(s, midNext, right, k));
        }
        return right - left + 1;
    }
}

class RandomizedCollection {
    private Map<Integer, Set<Integer>> map;
    private List<Integer> list;
    private Random rand;

    public RandomizedCollection() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (!map.containsKey(val))
            map.put(val, new LinkedHashSet<Integer>());
        map.get(val).add(list.size());
        list.add(val);
        return map.get(val).size() == 1;
    }

    public boolean remove(int val) {
        if (map.containsKey(val) && map.get(val).size() > 0) {
            int targetIdx = map.get(val).iterator().next();
            int lastIdx = list.size() - 1;
            list.set(targetIdx, list.get(lastIdx));
            map.get(val).remove(targetIdx);
            map.get(list.get(targetIdx)).add(targetIdx);
            map.get(list.get(targetIdx)).remove(list.size() - 1);
            list.remove(list.size() - 1);
            return true;
        }
        return false;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

class RandomizedSet {
    List<Integer> list;
    Map<Integer, Integer> map;
    Random rand;

    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            list.add(val);
            map.put(val, list.size() - 1);
            return true;
        }
        return false;
    }

    public boolean remove(int val) {
        if (map.containsKey(val)) {
            int candidateIdx = map.get(val);
            swap(list, candidateIdx, list.size() - 1);
            map.put(list.get(candidateIdx), candidateIdx);
            map.remove(val);
            list.remove(list.size() - 1);
            return true;
        }
        return false;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }

    private void swap(List<Integer> list, int i, int j) {
        int temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }
}

class Solution {
    public int combinationSum4(int[] nums, int target) {
        Integer[] memo = new Integer[target + 1];
        memo[0] = 1;
        return helper(nums, target, memo);
    }

    private int helper(int[] nums, int remain, Integer[] memo) {
        if (remain < 0) {
            return 0;
        }
        if (memo[remain] != null) {
            return memo[remain];
        }
        memo[remain] = 0;
        for (int num : nums) {
            int permutations = helper(nums, remain - num, memo);
            memo[remain] += permutations;
        }
        return memo[remain];
    }
}

class Solution {
    public int lengthOfLongestSubstringKDistinct(String s, int k) {
        Map<Character, Integer> charCount = new HashMap<>();
        int left = 0, right = 0, distinct = 0, maxLength = 0;
        while (right < s.length()) {
            // Move right first.
            while (right < s.length() && distinct <= k) {
                if (!charCount.containsKey(s.charAt(right))) {
                    charCount.put(s.charAt(right), 0);
                    distinct += 1;
                }
                charCount.put(s.charAt(right), charCount.get(s.charAt(right)) + 1);
                right += 1;
            }

            // Get current Length and update maxLength if necessary
            if (distinct > k) {
                maxLength = Math.max(right - left - 1, maxLength);
            } else {
                maxLength = Math.max(right - left, maxLength);
                break;
            }

            // Move left
            while (distinct > k) {
                charCount.put(s.charAt(left), charCount.get(s.charAt(left)) - 1);
                if (charCount.get(s.charAt(left)) == 0) {
                    charCount.remove(s.charAt(left));
                    distinct -= 1;
                }
                left += 1;
            }
        }
        return maxLength;
    }
}

public class Codec {
    private int pos;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder ans = new StringBuilder();
        serial(root, ans);
        return ans.toString();
    }

    private void serial(TreeNode node, StringBuilder str) {
        if (node == null) {
            str.append("#");
            str.append(",");
            return;
        }
        str.append(String.valueOf(node.val));
        str.append(",");
        serial(node.left, str);
        serial(node.right, str);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        return deserial(nodes);
    }

    private TreeNode deserial(String[] nodes) {
        if (nodes[pos].equals("#")) {
            pos += 1;
            return null;
        }
        TreeNode currNode = new TreeNode(Integer.parseInt(nodes[pos++]));
        currNode.left = deserial(nodes);
        currNode.right = deserial(nodes);
        return currNode;
    }
}

class MedianFinder {
    List<Integer> list;

    public MedianFinder() {
        list = new ArrayList<>();
    }

    public void addNum(int num) {
        int pos = binarySearch(num);
        if (pos == -1) {
            list.add(0, num);
        } else {
            list.add(pos + 1, num);
        }
    }

    public double findMedian() {
        return list.size() % 2 == 0 ? (0.0 + list.get(list.size() / 2) + list.get(list.size() / 2 - 1)) / 2
                : (double) list.get(list.size() / 2);
    }

    private void swap(List<Integer> list, int i, int j) {
        int temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
    }

    private int binarySearch(int target) {
        int left = 0, right = list.size() - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) > target) {
                right = mid - 1;
            } else if (list.get(mid) < target) {
                ans = mid;
                left = mid + 1;
            } else {
                ans = mid;
                break;
            }
        }
        return ans;
    }
}

class Solution {
    // 0 -> 1 mark as -2
    // 1 -> 0 mark as -1
    private final int[][] DIRECTIONS = new int[][] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 },
            { 1, -1 }, { 0, -1 } };

    public void gameOfLife(int[][] board) {
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                int liveNeighbors = countLiveNeighbors(board, row, col);
                if (board[row][col] == 1) {
                    board[row][col] = liveNeighbors < 2 ? -1 : liveNeighbors <= 3 ? 1 : -1;
                } else {
                    board[row][col] = liveNeighbors == 3 ? -2 : 0;
                }
            }
        }
        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board[0].length; col++) {
                if (board[row][col] == -1) {
                    board[row][col] = 0;
                } else if (board[row][col] == -2) {
                    board[row][col] = 1;
                }
            }
        }
    }

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

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