class Solution {
    private int[] array;
    private int[] original;
    private Random rand;

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
        rand = new Random();
    }

    public int[] reset() {
        array = original;
        return original = original.clone();
    }

    public int[] shuffle() {
        int[] ans = array;
        for (int i = 0; i < ans.length; i++) {
            int selectedIdx = rand.nextInt(ans.length - i) + i;
            swap(ans, i, selectedIdx);
        }
        return ans;
    }

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

class Solution {
    public int removeElement(int[] nums, int val) {
        int ptrNextPlace = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[ptrNextPlace] = nums[i];
                ptrNextPlace += 1;
            }
        }
        return ptrNextPlace;
    }
}

class Solution {
    public String smallestNumber(String pattern) {
        StringBuilder ans = new StringBuilder(), stack = new StringBuilder();
        for (int i = 0; i <= pattern.length(); i++) {
            stack.append((char) (i + '1'));
            if (i == pattern.length() || pattern.charAt(i) == 'I') {
                ans.append(stack.reverse());
                stack = new StringBuilder();
            }
        }
        return ans.toString();
    }
}

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        helper(ans, new ArrayList<>(), candidates, 0, target);
        return ans;
    }

    private void helper(List<List<Integer>> ans, List<Integer> curr, int[] candidates, int pos, int remain) {
        if (remain == 0) {
            ans.add(new ArrayList<>(curr));
            return;
        }
        for (int i = pos; i < candidates.length && candidates[i] <= remain; i++) {
            if (i > pos && candidates[i] == candidates[i - 1]) {
                continue;
            }
            curr.add(candidates[i]);
            helper(ans, curr, candidates, i + 1, remain - candidates[i]);
            curr.remove(curr.size() - 1);
        }
    }
}

class Solution {
    private static class Node {
        int pos;
        boolean canMoveBack;

        Node(int _pos, boolean _canMoveBack) {
            pos = _pos;
            canMoveBack = _canMoveBack;
        }
    }

    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        if (x == 0) {
            return 0;
        }
        int furthest = 2000 + 2 * b + 1;
        boolean[] visited = new boolean[furthest];
        for (int num : forbidden) {
            visited[num] = true;
        }
        int step = 0;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(0, false));
        visited[0] = true;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node currNode = q.poll();
                if (currNode.pos == x) {
                    return step;
                }
                if (currNode.canMoveBack && currNode.pos - b > 0 && !visited[currNode.pos - b]) {
                    q.offer(new Node(currNode.pos - b, false));
                    visited[currNode.pos - b] = true;
                }
                if (currNode.pos + a < furthest && !visited[currNode.pos + a]) {
                    q.offer(new Node(currNode.pos + a, true));
                    visited[currNode.pos + a] = true;
                }
            }
            step += 1;
        }
        return -1;
    }
}

class Solution {
    public int longestStrChain(String[] words) {
        Map<String, Integer> memo = new HashMap<>();
        Set<String> wordSet = new HashSet<>();
        Collections.addAll(wordSet, words);
        int ans = 0;
        for (String word : words) {
            ans = Math.max(ans, helper(word, memo, wordSet));
        }
        return ans;
    }

    private int helper(String word, Map<String, Integer> memo, Set<String> wordSet) {
        if (memo.containsKey(word)) {
            return memo.get(word);
        }
        StringBuilder currWord = new StringBuilder(word);
        // 关键点不能初始化为0
        int maxLength = 1;
        for (int i = 0; i < currWord.length(); i++) {
            currWord.deleteCharAt(i);
            String newWord = currWord.toString();
            // 关键点, 删除某个位置char后的String必须在Set里面, 否则我们就会引入一些不在Set里面的String
            // 到map里面, 从而会让别的String以为这些String存在而和它们组成chain
            if (wordSet.contains(newWord)) {
                maxLength = Math.max(maxLength, helper(newWord, memo, wordSet) + 1);
            }
            currWord.insert(i, word.charAt(i));
        }
        memo.put(word, maxLength);
        return maxLength;
    }
}

class Solution {
    private static class Node {
        int listNum;
        int idx;
        int val;

        Node(int _listNum, int _idx, int _val) {
            listNum = _listNum;
            idx = _idx;
            val = _val;
        }
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            minHeap.offer(new Node(i, 0, nums.get(i).get(0)));
            max = Math.max(max, nums.get(i).get(0));
        }
        int intervalLength = Integer.MAX_VALUE;
        int left = -1000000, right = 1000000;
        while (!minHeap.isEmpty()) {
            Node currMinNode = minHeap.peek();
            int currIntervalLength = max - currMinNode.val;
            if (currIntervalLength < intervalLength || (currIntervalLength == intervalLength &&
                    currMinNode.val < left)) {
                left = currMinNode.val;
                right = max;
                intervalLength = currIntervalLength;
            }
            minHeap.poll();
            if (currMinNode.idx + 1 == nums.get(currMinNode.listNum).size()) {
                break;
            }
            Node newNode = new Node(currMinNode.listNum, currMinNode.idx + 1,
                    nums.get(currMinNode.listNum).get(currMinNode.idx + 1));
            minHeap.offer(newNode);
            max = Math.max(max, newNode.val);
        }
        return new int[] { left, right };
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> deque = new LinkedList<>();
        for (ListNode node : lists) {
            if (node != null) {
                deque.offer(node);
            }
        }
        while (deque.size() > 1) {
            ListNode nodeOne = deque.poll();
            ListNode nodeTwo = deque.poll();
            deque.offer(merge(nodeOne, nodeTwo));
        }
        return deque.size() != 0 ? deque.poll() : null;
    }

    private ListNode merge(ListNode nodeOne, ListNode nodeTwo) {
        ListNode prev = null, currNode = nodeOne, ptr = nodeTwo;
        while (currNode != null && ptr != null) {
            if (currNode.val <= ptr.val) {
                prev = currNode;
                currNode = currNode.next;
            } else {
                if (prev != null) {
                    prev.next = ptr;
                }
                prev = ptr;
                ptr = ptr.next;
                prev.next = currNode;
            }
        }
        if (currNode == null) {
            prev.next = ptr;
        }
        return nodeOne.val <= nodeTwo.val ? nodeOne : nodeTwo;
    }
}

class Solution {
    public String minRemoveToMakeValid(String s) {
        int leftParenCount = 0, rightParenCount = 0;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                leftParenCount += 1;
            } else if (s.charAt(i) == ')') {
                if (leftParenCount > rightParenCount) {
                    rightParenCount += 1;
                } else {
                    continue;
                }
            }
            sb.append(s.charAt(i));
        }

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) == '(') {
                if (rightParenCount == 0) {
                    continue;
                }
                rightParenCount -= 1;
            }
            res.append(sb.charAt(i));
        }
        return res.toString();
    }
}

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> rightMovingRocks = new ArrayDeque<>();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < asteroids.length; i++) {
            if (asteroids[i] >= 0) {
                rightMovingRocks.addLast(asteroids[i]);
            } else {
                while (!rightMovingRocks.isEmpty() && rightMovingRocks.peekLast() < Math.abs(asteroids[i])) {
                    rightMovingRocks.pollLast();
                }
                if (rightMovingRocks.isEmpty()) {
                    ans.add(asteroids[i]);
                } else if (rightMovingRocks.peekLast() == Math.abs(asteroids[i])) {
                    rightMovingRocks.pollLast();
                }
            }
        }
        while (!rightMovingRocks.isEmpty()) {
            ans.add(rightMovingRocks.pollFirst());
        }
        int[] result = new int[ans.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = ans.get(i);
        }
        return result;
    }
}