class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> ans = new ArrayList<>();
        int ptr = 0;
        while (ptr < intervals.length && intervals[ptr][1] <= toBeRemoved[0]) {
            ans.add(new ArrayList<>(Arrays.asList(intervals[ptr][0], intervals[ptr][1])));
            ptr += 1;
        }

        while (ptr < intervals.length && intervals[ptr][0] < toBeRemoved[1]) {
            if (intervals[ptr][0] < toBeRemoved[0]) {
                ans.add(new ArrayList<>(Arrays.asList(intervals[ptr][0], toBeRemoved[0])));
            }
            if (intervals[ptr][1] > toBeRemoved[1]) {
                ans.add(new ArrayList<>(Arrays.asList(toBeRemoved[1], intervals[ptr][1])));
            }
            ptr += 1;
        }

        while (ptr < intervals.length) {
            ans.add(new ArrayList<>(Arrays.asList(intervals[ptr][0], intervals[ptr][1])));
            ptr += 1;
        }
        return ans;
    }
}

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

    public int maxDistance(int[][] grid) {
        boolean[][] cellDistance = new boolean[grid.length][grid[0].length];
        Deque<int[]> cellQ = new ArrayDeque<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    cellDistance[i][j] = true;
                    cellQ.offer(new int[] { i, j });
                }
            }
        }
        if (cellQ.isEmpty() || cellQ.size() == grid.length * grid[0].length) {
            return -1;
        }
        int distance = 0;
        while (!cellQ.isEmpty()) {
            for (int i = cellQ.size(); i > 0; i--) {
                int[] currPos = cellQ.poll();
                for (int[] direction : directions) {
                    int newRow = currPos[0] + direction[0];
                    int newCol = currPos[1] + direction[1];
                    if (!isOutOfBound(grid, newRow, newCol) && !cellDistance[newRow][newCol]) {
                        cellDistance[newRow][newCol] = true;
                        cellQ.offer(new int[] { newRow, newCol });
                    }
                }
            }
            distance += 1;
        }
        return distance - 1;
    }

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

class Solution {
    public int minimumSwaps(int[] nums) {
        int minIdx = 0, maxIdx = 0, max = nums[0], min = nums[0];
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= max) {
                max = nums[i];
                maxIdx = i;
            } else if (nums[i] < min) {
                min = nums[i];
                minIdx = i;
            }
        }
        return minIdx <= maxIdx ? minIdx - 0 + nums.length - 1 - maxIdx : minIdx + nums.length - 1 - maxIdx - 1;
    }
}

class Solution {
    public int triangularSum(int[] nums) {
        Deque<Integer> numQ = new ArrayDeque<>();
        for (int num : nums) {
            numQ.offer(num);
        }
        while (numQ.size() > 1) {
            for (int i = numQ.size() - 1; i > 0; i--) {
                int topNum = numQ.poll();
                numQ.offer((topNum + numQ.peekFirst()) % 10);
            }
            numQ.poll();
        }
        return numQ.poll();
    }
}

class Solution {
    private static class UnionFind {
        private int[] parents;
        private int[] ranks;

        private UnionFind(int size) {
            parents = new int[size + 1];
            ranks = new int[size + 1];
            for (int i = 1; i < size + 1; i++) {
                parents[i] = i;
                ranks[i] = 1;
            }
        }

        private int find(int node) {
            if (parents[node] == node) {
                return node;
            }
            return parents[node] = find(parents[node]);
        }

        private void union(int nodeOne, int nodeTwo) {
            int rootOne = find(nodeOne);
            int rootTwo = find(nodeTwo);
            if (rootOne != rootTwo) {
                if (ranks[rootOne] > ranks[rootTwo]) {
                    parents[rootTwo] = rootOne;
                } else if (ranks[rootOne] < ranks[rootTwo]) {
                    parents[rootOne] = rootTwo;
                } else {
                    parents[rootTwo] = rootOne;
                    ranks[rootOne] += 1;
                }
            }
        }

        private boolean isConnected(int nodeOne, int nodeTwo) {
            return find(nodeOne) == find(nodeTwo);
        }
    }

    public boolean equationsPossible(String[] equations) {
        int charCount = 0;
        UnionFind uf = new UnionFind(26);
        for (String equation : equations) {
            if (equation.charAt(1) == '=') {
                int firstLetterIdx = equation.charAt(0) - 'a';
                int secondLetterIdx = equation.charAt(3) - 'a';
                uf.union(firstLetterIdx, secondLetterIdx);
            }
        }

        for (String equation : equations) {
            int firstLetterIdx = equation.charAt(0) - 'a';
            int secondLetterIdx = equation.charAt(3) - 'a';
            if (equation.charAt(1) == '!' && uf.isConnected(firstLetterIdx, secondLetterIdx)) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> moduCount = new HashMap<>();
        int sum = 0, ans = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int currModulo = Math.floorMod(sum, k);
            if (currModulo == 0) {
                ans += 1;
            }
            ans += moduCount.getOrDefault(currModulo, 0);
            moduCount.put(currModulo, moduCount.getOrDefault(currModulo, 0) + 1);
        }
        return ans;
    }
}

class Solution {
    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int max = nums[nums.length - 1], min = nums[0], ans = max - min;
        for (int i = 0; i < nums.length - 1; i++) {
            max = Math.max(max, nums[i] + 2 * k);
            min = Math.min(nums[0] + 2 * k, nums[i + 1]);
            ans = Math.min(ans, max - min);
        }
        return ans;
    }
}

class Solution {
    public int strStr(String hayStack, String needle) {
        if (needle.length() > hayStack.length()) {
            return -1;
        }
        int[] lps = buildLPS(needle);
        int ptrOne = 0, ptrTwo = 0;
        while (ptrOne < hayStack.length() && ptrTwo < needle.length()) {
            if (hayStack.charAt(ptrOne) == needle.charAt(ptrTwo)) {
                ptrOne += 1;
                ptrTwo += 1;
            } else {
                if (ptrTwo != 0) {
                    ptrTwo = lps[ptrTwo - 1];
                } else {
                    ptrOne += 1;
                }
            }
        }
        if (ptrTwo == needle.length()) {
            return ptrOne - needle.length();
        }
        return -1;
    }

    private int[] buildLPS(String needle) {
        char[] sArray = needle.toCharArray();
        int[] ans = new int[needle.length()];
        int index = 0;
        for (int i = 1; i < ans.length;) {
            if (sArray[i] == sArray[index]) {
                ans[i] = index + 1;
                index += 1;
                i += 1;
            } else {
                if (index != 0) {
                    index = ans[index - 1];
                } else {
                    ans[i] = 0;
                    i += 1;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int concatenatedBinary(int n) {
        long ans = 0;
        int length = 0;
        int mod = (int) 1e9 + 7;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                length += 1;
            }
            ans = ((ans << length) | i) % mod;
        }
        return (int) ans;
    }
}

class FirstUnique {
    static class Node {
        int val;
        Node prev;
        Node next;

        Node(int _val) {
            this.val = _val;
            prev = null;
            next = null;
        }
    }

    private void removeNode(Node node) {
        Node prevNode = node.prev;
        Node nextNode = node.next;
        if (prevNode == null && nextNode == null) {
            head = null;
            tail = null;
        } else if (prevNode == null) {
            head = nextNode;
            head.prev = null;
        } else if (nextNode == null) {
            tail = prevNode;
            tail.next = null;
        } else {
            prevNode.next = nextNode;
            nextNode.prev = prevNode;
        }
        node.prev = null;
        node.next = null;
    }

    private void insertNode(Node node) {
        if (head == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
    }

    private Node head;
    private Node tail;
    private Map<Integer, Node> nodeMap;
    private Set<Integer> duplicates;

    public FirstUnique(int[] nums) {
        nodeMap = new HashMap<>();
        duplicates = new HashSet<>();
        for (int num : nums) {
            add(num);
        }
    }

    public int showFirstUnique() {
        if (nodeMap.isEmpty()) {
            return -1;
        }
        return head.val;
    }

    public void add(int value) {
        Node head = this.head;
        Node tail = this.tail;
        Map<Integer, Node> nodeMap = this.nodeMap;
        if (nodeMap.containsKey(value)) {
            removeNode(nodeMap.get(value));
            nodeMap.remove(value);
            duplicates.add(value);
        } else if (!duplicates.contains(value)) {
            Node newNode = new Node(value);
            nodeMap.put(value, newNode);
            insertNode(newNode);
        }
        head = this.head;
        tail = this.tail;
    }
}