public int search(int key, int[] array) {
    int l = 0, h = array.length - 1;
    while (l <= h) {
        int mid = l + (h - l) / 2;
        if (key == array[mid]) return mid;
        if (key < array[mid])  h = mid - 1;
        else l = mid + 1;
    }
    return -1;
}

public int mySqrt(int x) {
    if(x <= 1) return x;
    int l = 1, h = x;
    while(l <= h){
        int mid = l + (h - l) / 2;
        int sqrt = x / mid;
        if(sqrt == mid) return mid;
        else if(sqrt < mid) h = mid - 1;
        else l = mid + 1;
    }
    return h;
}

public int arrangeCoins(int n) {
    int l = 0, h = n;
    while(l <= h){
        int m = l + (h - l) / 2;
        long x = m * (m + 1L) / 2;
        if(x == n) return m;
        else if(x < n) l = m + 1;
        else h = m - 1;
    }
    return h;
}

public int arrangeCoins(int n) {
    int level = 1;
    while (n > 0) {
        n -= level;
        level++;
    }
    return n == 0 ? level - 1 : level - 2;
}

public int singleNonDuplicate(int[] nums) {
    int l = 0, h = nums.length - 1;
    while(l < h) {
        int m = l + (h - l) / 2;
        if(m % 2 == 1) m--; // 保证 l/h/m 都在偶数位，使得查找区间大小一直都是奇数
        if(nums[m] == nums[m + 1]) l = m + 2;
        else h = m;
    }
    return nums[l];
}

public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int i = 0, j = 0;
    while(i < g.length && j < s.length){
        if(g[i] <= s[j]) i++;
        j++;
    }
    return i;
}

public int findMinArrowShots(int[][] points) {
    if(points.length == 0) return 0;
    Arrays.sort(points,(a,b) -> (a[1] - b[1]));
    int curPos = points[0][1];
    int ret = 1;
    for (int i = 1; i < points.length; i++) {
        if(points[i][0] <= curPos) {
            continue;
        }
        curPos = points[i][1];
        ret++;
    }
    return ret;
 }

public int maxProfit(int[] prices) {
    int profit = 0;
    for(int i = 1; i < prices.length; i++){
        if(prices[i] > prices[i-1]) profit += (prices[i] - prices[i-1]);
    }
    return profit;
}

public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int cnt = 0;
    for(int i = 0; i < flowerbed.length; i++){
        if(flowerbed[i] == 1) continue;
        int pre = i == 0 ? 0 : flowerbed[i - 1];
        int next = i == flowerbed.length - 1 ? 0 : flowerbed[i + 1];
        if(pre == 0 && next == 0) {
            cnt++;
            flowerbed[i] = 1;
        }
    }
    return cnt >= n;
}

public boolean checkPossibility(int[] nums) {
    int cnt = 0;
    for(int i = 1; i < nums.length; i++){
        if(nums[i] < nums[i - 1]){
            cnt++;
            if(i - 2 >= 0 && nums[i - 2] > nums[i]) nums[i] = nums[i-1];
            else nums[i - 1] = nums[i];
        }
    }
    return cnt <= 1;
}

public boolean isSubsequence(String s, String t) {
    for (int i = 0, pos = 0; i < s.length(); i++, pos++) {
        pos = t.indexOf(s.charAt(i), pos);
        if(pos == -1) return false;
    }
    return true;
}

public List<Integer> partitionLabels(String S) {
    List<Integer> ret = new ArrayList<>();
    int[] lastIdxs = new int[26];
    for(int i = 0; i < S.length(); i++) lastIdxs[S.charAt(i) - 'a'] = i;
    int startIdx = 0;
    while(startIdx < S.length()) {
        int endIdx = startIdx;
        for(int i = startIdx; i < S.length() && i <= endIdx; i++) {
            int lastIdx = lastIdxs[S.charAt(i) - 'a'];
            if(lastIdx == i) continue;
            if(lastIdx > endIdx) endIdx = lastIdx;
        }
        ret.add(endIdx - startIdx + 1);
        startIdx = endIdx + 1;
    }
    return ret;
}

public int[][] reconstructQueue(int[][] people) {
    if(people == null || people.length == 0 || people[0].length == 0) return new int[0][0];

    Arrays.sort(people, new Comparator<int[]>() {
       public int compare(int[] a, int[] b) {
           if(a[0] == b[0]) return a[1] - b[1];
           return b[0] - a[0];
       }
    });

    int n = people.length;
    List<int[]> tmp = new ArrayList<>();
    for(int i = 0; i < n; i++) {
        tmp.add(people[i][1], new int[]{people[i][0], people[i][1]});
    }

    int[][] ret = new int[n][2];
    for(int i = 0; i < n; i++) {
        ret[i][0] = tmp.get(i)[0];
        ret[i][1] = tmp.get(i)[1];
    }
    return ret;
}

public int[] twoSum(int[] numbers, int target) {
    int i = 0, j = numbers.length - 1;
    while (i < j) {
        int sum = numbers[i] + numbers[j];
        if (sum == target) return new int[]{i + 1, j + 1};
        else if (sum < target) i++;
        else j--;
    }
    return null;
}

private HashSet<Character> vowels = new HashSet<>(Arrays.asList('a','e','i','o','u','A','E','I','O','U'));

public String reverseVowels(String s) {
    if(s.length() == 0) return s;
    int i = 0, j = s.length() - 1;
    char[] result = new char[s.length()];
    while(i <= j){
        char ci = s.charAt(i);
        char cj = s.charAt(j);
        if(!vowels.contains(ci)){
            result[i] = ci;
            i++;
        } else if(!vowels.contains(cj)){
            result[j] = cj;
            j--;
        } else{
            result[i] = cj;
            result[j] = ci;
            i++;
            j--;
        }
    }
    return new String(result);
}

public boolean judgeSquareSum(int c) {
    int left = 0, right = (int) Math.sqrt(c);
    while(left <= right){
        int powSum = left * left + right * right;
        if(powSum == c) return true;
        else if(powSum > c) right--;
        else left++;
    }
    return false;
}

public boolean validPalindrome(String s) {
    int i = 0, j = s.length() -1;
    while(i < j){
        if(s.charAt(i) != s.charAt(j)){
            return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
        }
        i++;
        j--;
    }
    return true;
}

private boolean isPalindrome(String s, int l, int r){
    while(l < r){
        if(s.charAt(l) != s.charAt(r))
            return false;
        l++;
        r--;
    }
    return true;
}

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1; // 需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值
    int idx = m + n - 1;
    while(i >= 0 || j >= 0){
        if(i < 0) nums1[idx] = nums2[j--];
        else if(j < 0) nums1[idx] = nums1[i--];
        else if(nums1[i] > nums2[j]) nums1[idx] = nums1[i--];
        else nums1[idx] = nums2[j--];
        idx--;
    }
}

public boolean hasCycle(ListNode head) {
    if(head == null) return false;
    ListNode l1 = head, l2 = head.next;
    while(l1 != null && l2 != null){
        if(l1 == l2) return true;
        l1 = l1.next;
        if(l2.next == null) break;
        l2 = l2.next.next;
    }
    return false;
}

public String findLongestWord(String s, List<String> d) {
    String ret = "";
    for (String str : d) {
        for (int i = 0, j = 0; i < s.length() && j < str.length(); i++) {
            if (s.charAt(i) == str.charAt(j)) j++;
            if (j == str.length()) {
                if (ret.length() < str.length()
                        || (ret.length() == str.length() && ret.compareTo(str) > 0)) {
                    ret = str;
                }
            }
        }
    }
    return ret;
}

public int findKthLargest(int[] nums, int k) {
        int N = nums.length;
        Arrays.sort(nums);
        return nums[N - k];
}

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int val : nums) {
        pq.offer(val);
        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }

    private int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        while(true) {
            while(i < hi && less(a[++i], a[lo]));
            while(j > lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    private void exch(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private boolean less(int v, int w) {
        return v < w;
    }
}

public List<Integer> topKFrequent(int[] nums, int k) {
    List<Integer> ret = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    for(int num : nums) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    List<Integer>[] bucket = new List[nums.length + 1];
    for(int key : map.keySet()) {
        int frequency = map.get(key);
        if(bucket[frequency] == null) {
            bucket[frequency] = new ArrayList<>();
        }
        bucket[frequency].add(key);
    }

    for(int i = bucket.length - 1; i >= 0 && ret.size() < k; i--) {
        if(bucket[i] != null) {
            ret.addAll(bucket[i]);
        }
    }
    return ret;
}

public int minPathLength(int[][] grids, int tr, int tc) {
    int[][] next = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int m = grids.length, n = grids[0].length;
    Queue<Position> queue = new LinkedList<>();
    queue.add(new Position(0, 0, 1));
    while (!queue.isEmpty()) {
        Position pos = queue.poll();
        for (int i = 0; i < 4; i++) {
            Position nextPos = new Position(pos.r + next[i][0], pos.c + next[i][1], pos.length + 1);
            if (nextPos.r < 0 || nextPos.r >= m || nextPos.c < 0 || nextPos.c >= n) continue;
            if (grids[nextPos.r][nextPos.c] != 1) continue;
            grids[nextPos.r][nextPos.c] = 0;
            if (nextPos.r == tr && nextPos.c == tc) return nextPos.length;
            queue.add(nextPos);
        }
    }
    return -1;
}

private class Position {
    int r, c, length;
    public Position(int r, int c, int length) {
        this.r = r;
        this.c = c;
        this.length = length;
    }
}

public int maxAreaOfIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int max = 0;
    for(int i = 0; i < m; i++){
        for(int j = 0; j < n; j++){
            if(grid[i][j] == 1) max = Math.max(max, dfs(grid, i, j));
        }
    }
    return max;
}

private int dfs(int[][] grid, int i, int j){
    int m = grid.length, n = grid[0].length;
    if(i < 0 || i >= m || j < 0 || j >= n) return 0;
    if(grid[i][j] == 0) return 0;
    grid[i][j] = 0;
    return dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1) + 1;
}

public int findCircleNum(int[][] M) {
    int n = M.length;
    int ret = 0;
    boolean[] hasFind = new boolean[n];
    for(int i = 0; i < n; i++) {
        if(!hasFind[i]) {
            dfs(M, i, hasFind);
            ret++;
        }
    }
    return ret;
}

private void dfs(int[][] M, int i, boolean[] hasFind) {
    hasFind[i] = true;
    int n = M.length;
    for(int k = 0; k < n; k++) {
        if(M[i][k] == 1 && !hasFind[k]) {
            dfs(M, k, hasFind);
        }
    }
}

private int m, n;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    m = grid.length;
    n = grid[0].length;
    int ret = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j);
                ret++;
            }
        }
    }
    return ret;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
    grid[i][j] = '0';
    for (int k = 0; k < direction.length; k++) {
        dfs(grid, i + direction[k][0], j + direction[k][1]);
    }
}

public List<String> binaryTreePaths(TreeNode root) {
    List<String> ret = new ArrayList();
    if(root == null) return ret;
    dfs(root, "", ret);
    return ret;
}

private void dfs(TreeNode root, String prefix, List<String> ret){
    if(root == null) return;
    if(root.left == null && root.right == null){
        ret.add(prefix + root.val);
        return;
    }
    prefix += (root.val + "->");
    dfs(root.left, prefix, ret);
    dfs(root.right, prefix, ret);
}

private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private int m, n;

public void solve(char[][] board) {
    if (board == null || board.length == 0) return;
    m = board.length;
    n = board[0].length;
    for (int i = 0; i < m; i++) {
        dfs(board, i, 0);
        dfs(board, i, n - 1);
    }
    for (int i = 0; i < n; i++) {
        dfs(board, 0, i);
        dfs(board, m - 1, i);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'T') board[i][j] = 'O';
            else if (board[i][j] == 'O') board[i][j] = 'X';
        }
    }
}

private void dfs(char[][] board, int r, int c) {
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') return;
    board[r][c] = 'T';
    for (int i = 0; i < direction.length; i++) {
        dfs(board, r + direction[i][0], c + direction[i][1]);
    }
}

private int m, n;
private int[][] matrix;
private int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

public List<int[]> pacificAtlantic(int[][] matrix) {
    List<int[]> ret = new ArrayList<>();
    if (matrix == null || matrix.length == 0) return ret;
    this.m = matrix.length;
    this.n = matrix[0].length;
    this.matrix = matrix;
    boolean[][] canReachP = new boolean[m][n];
    boolean[][] canReachA = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        dfs(i, 0, canReachP);
        dfs(i, n - 1, canReachA);
    }
    for (int i = 0; i < n; i++) {
        dfs(0, i, canReachP);
        dfs(m - 1, i, canReachA);
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (canReachP[i][j] && canReachA[i][j]) {
                ret.add(new int[]{i, j});
            }
        }
    }
    return ret;
}

private void dfs(int r, int c, boolean[][] canReach) {
    if(canReach[r][c]) return;
    canReach[r][c] = true;
    for (int i = 0; i < direction.length; i++) {
        int nextR = direction[i][0] + r;
        int nextC = direction[i][1] + c;
        if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n
                || matrix[r][c] > matrix[nextR][nextC]) continue;
        dfs(nextR, nextC, canReach);
    }
}

private List<List<String>> ret;
private char[][] nQueens;
private boolean[] colUsed;
private boolean[] diagonals45Used;
private boolean[] diagonals135Used;
private int n;

public List<List<String>> solveNQueens(int n) {
    ret = new ArrayList<>();
    nQueens = new char[n][n];
    Arrays.fill(nQueens, '.');
    colUsed = new boolean[n];
    diagonals45Used = new boolean[2 * n - 1];
    diagonals135Used = new boolean[2 * n - 1];
    this.n = n;
    backstracking(0);
    return ret;
}

private void backstracking(int row) {
    if (row == n) {
        List<String> list = new ArrayList<>();
        for (char[] chars : nQueens) {
            list.add(new String(chars));
        }
        ret.add(list);
        return;
    }

    for (int col = 0; col < n; col++) {
        int diagonals45Idx = row + col;
        int diagonals135Idx = n - 1 - (row - col);
        if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]) {
            continue;
        }
        nQueens[row][col] = 'Q';
        colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = true;
        backstracking(row + 1);
        colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = false;
        nQueens[row][col] = '.';
    }
}

private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> ret = new ArrayList<>();
    if (digits != null && digits.length() != 0) {
        combination("", digits, 0, ret);
    }
    return ret;
}

private void combination(String prefix, String digits, int offset, List<String> ret) {
    if (offset == digits.length()) {
        ret.add(prefix);
        return;
    }
    String letters = KEYS[digits.charAt(offset) - '0'];
    for (char c : letters.toCharArray()) {
        combination(prefix + c, digits, offset + 1, ret);
    }
}

private static int[][] shift = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private static boolean[][] visited;
private int m;
private int n;

public boolean exist(char[][] board, String word) {
    if (word == null || word.length() == 0) return true;
    if (board == null || board.length == 0 || board[0].length == 0) return false;
    m = board.length;
    n = board[0].length;
    visited = new boolean[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dfs(board, word, 0, i, j)) return true;
        }
    }
    return false;
}

private boolean dfs(char[][] board, String word, int start, int r, int c) {
    if (start == word.length()) {
        return true;
    }
    if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(start) ||  visited[r][c] ) {
        return false;
    }
    visited[r][c] = true;
    for (int i = 0; i < shift.length; i++) {
        int nextR = r + shift[i][0];
        int nextC = c + shift[i][1];
        if (dfs(board, word, start + 1, nextR, nextC)) return true;
    }
    visited[r][c] = false;
    return false;
}

private List<String> ret;

public List<String> restoreIpAddresses(String s) {
    ret = new ArrayList<>();
    doRestore(0, "", s);
    return ret;
}

private void doRestore(int k, String path, String s) {
    if (k == 4 || s.length() == 0) {
        if (k == 4 && s.length() == 0) {
            ret.add(path);
        }
        return;
    }
    for (int i = 0; i < s.length() && i <= 2; i++) {
        if (i != 0 && s.charAt(0) == '0') break;
        String part = s.substring(0, i + 1);
        if (Integer.valueOf(part) <= 255) {
            doRestore(k + 1, path.length() != 0 ? path + "." + part : part, s.substring(i + 1));
        }
    }
}

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> permuteList = new ArrayList<>();
    boolean[] visited = new boolean[nums.length];
    backtracking(permuteList, visited, nums, ret);
    return ret;
}

private void backtracking(List<Integer> permuteList, boolean[] visited, int[] nums, List<List<Integer>> ret){
    if(permuteList.size() == nums.length){
        ret.add(new ArrayList(permuteList));
        return;
    }

    for(int i = 0; i < visited.length; i++){
        if(visited[i]) continue;
        visited[i] = true;
        permuteList.add(nums[i]);
        backtracking(permuteList, visited, nums, ret);
        permuteList.remove(permuteList.size() - 1);
        visited[i] = false;
    }
}

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> permuteList = new ArrayList<>();
    Arrays.sort(nums);
    boolean[] visited = new boolean[nums.length];
    backtracking(permuteList, visited, nums, ret);
    return ret;
}

private void backtracking(List<Integer> permuteList, boolean[] visited, int[] nums, List<List<Integer>> ret) {
    if (permuteList.size() == nums.length) {
        ret.add(new ArrayList(permuteList));
        return;
    }

    for (int i = 0; i < visited.length; i++) {
        if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
        if (visited[i]) continue;
        visited[i] = true;
        permuteList.add(nums[i]);
        backtracking(permuteList, visited, nums, ret);
        permuteList.remove(permuteList.size() - 1);
        visited[i] = false;
    }
}

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> combineList = new ArrayList<>();
    backtracking(1, n, k, combineList, ret);
    return ret;
}

private void backtracking(int start, int n, int k, List<Integer> combineList, List<List<Integer>> ret){
    if(k == 0){
        ret.add(new ArrayList(combineList)); // 这里要重新构造一个 List
        return;
    }

    for(int i = start; i <= n - k + 1; i++){ // 剪枝

        combineList.add(i);                        // 把 i 标记为已访问
        backtracking(i + 1, n, k - 1, combineList, ret);
        combineList.remove(combineList.size() - 1); // 把 i 标记为未访问
    }
}

 private List<List<Integer>> ret;

 public List<List<Integer>> combinationSum(int[] candidates, int target) {
     ret = new ArrayList<>();
     doCombination(candidates, target, 0, new ArrayList<>());
     return ret;
 }

 private void doCombination(int[] candidates, int target, int start, List<Integer> list) {
     if (target == 0) {
         ret.add(new ArrayList<>(list));
         return;
     }
     for (int i = start; i < candidates.length; i++) {
         if (candidates[i] <= target) {
             list.add(candidates[i]);
             doCombination(candidates, target - candidates[i], i, list);
             list.remove(list.size() - 1);
         }
     }
 }

private List<List<Integer>> ret;

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    ret = new ArrayList<>();
    Arrays.sort(candidates);
    doCombination(candidates, target, 0, new ArrayList<>(), new boolean[candidates.length]);
    return ret;
}

private void doCombination(int[] candidates, int target, int start, List<Integer> list, boolean[] visited) {
    if (target == 0) {
        ret.add(new ArrayList<>(list));
        return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (i != 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]) continue;
        if (candidates[i] <= target) {
            list.add(candidates[i]);
            visited[i] = true;
            doCombination(candidates, target - candidates[i], i + 1, list, visited);
            visited[i] = false;
            list.remove(list.size() - 1);
        }
    }
}

private List<List<Integer>> ret;
private List<Integer> subsetList;

public List<List<Integer>> subsets(int[] nums) {
    ret = new ArrayList<>();
    subsetList = new ArrayList<>();
    for (int i = 0; i <= nums.length; i++) {
        backtracking(0, i, nums);
    }
    return ret;
}

private void backtracking(int startIdx, int size, int[] nums) {
    if (subsetList.size() == size) {
        ret.add(new ArrayList(subsetList));
        return;
    }

    for (int i = startIdx; i < nums.length; i++) {
        subsetList.add(nums[i]);
        backtracking(i + 1, size, nums); // startIdx 设为下一个元素，使 subset 中的元素都递增排序
        subsetList.remove(subsetList.size() - 1);
    }
}

private List<List<Integer>> ret;
private List<Integer> subsetList;
private boolean[] visited;

public List<List<Integer>> subsetsWithDup(int[] nums) {
    ret = new ArrayList<>();
    subsetList = new ArrayList<>();
    visited = new boolean[nums.length];
    Arrays.sort(nums);
    for (int i = 0; i <= nums.length; i++) {
        backtracking(0, i, nums);
    }
    return ret;
}

private void backtracking(int startIdx, int size, int[] nums) {
    if (subsetList.size() == size) {
        ret.add(new ArrayList(subsetList));
        return;
    }

    for (int i = startIdx; i < nums.length; i++) {
        if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
        subsetList.add(nums[i]);
        visited[i] = true;
        backtracking(i + 1, size, nums);
        visited[i] = false;
        subsetList.remove(subsetList.size() - 1);
    }
}

private List<List<String>> ret;

public List<List<String>> partition(String s) {
    ret = new ArrayList<>();
    doPartion(new ArrayList<>(), s);
    return ret;
}

private void doPartion(List<String> list, String s) {
    if (s.length() == 0) {
        ret.add(new ArrayList<>(list));
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        if (isPalindrome(s, 0, i)) {
            list.add(s.substring(0, i + 1));
            doPartion(list, s.substring(i + 1));
            list.remove(list.size() - 1);
        }
    }
}

private boolean isPalindrome(String s, int begin, int end) {
    while (begin < end) {
        if (s.charAt(begin++) != s.charAt(end--)) return false;
    }
    return true;
}

private boolean[][] rowsUsed = new boolean[9][10];
private boolean[][] colsUsed = new boolean[9][10];
private boolean[][] cubesUsed = new boolean[9][10];
private char[][] board;

public void solveSudoku(char[][] board) {
    this.board = board;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            int num = board[i][j] - '0';
            rowsUsed[i][num] = true;
            colsUsed[j][num] = true;
            cubesUsed[cubeNum(i, j)][num] = true;
        }
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            backtracking(i, j);
        }
    }
}

private boolean backtracking(int row, int col) {
    while (row < 9 && board[row][col] != '.') {
        row = col == 8 ? row + 1 : row;
        col = col == 8 ? 0 : col + 1;
    }
    if (row == 9) {
        return true;
    }
    for (int num = 1; num <= 9; num++) {
        if (rowsUsed[row][num] || colsUsed[col][num] || cubesUsed[cubeNum(row, col)][num]) continue;
        rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = true;
        board[row][col] = (char) (num + '0');
        if (backtracking(row, col)) return true;
        board[row][col] = '.';
        rowsUsed[row][num] = colsUsed[col][num] = cubesUsed[cubeNum(row, col)][num] = false;
    }
    return false;
}

private int cubeNum(int i, int j) {
    int r = i / 3;
    int c = j / 3;
    return r * 3 + c;
}

public List<Integer> diffWaysToCompute(String input) {
    int n = input.length();
    List<Integer> ret = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        char c = input.charAt(i);
        if (c == '+' || c == '-' || c == '*') {
            List<Integer> left = diffWaysToCompute(input.substring(0, i));
            List<Integer> right = diffWaysToCompute(input.substring(i + 1));
            for (int l : left) {
                for (int r : right) {
                    switch (c) {
                        case '+': ret.add(l + r); break;
                        case '-': ret.add(l - r); break;
                        case '*': ret.add(l * r); break;
                    }
                }
            }
        }
    }
    if (ret.size() == 0) ret.add(Integer.valueOf(input));
    return ret;
}

public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for(int i = 2; i <= n; i++) {
        for(int j = 1; j <= i - 1; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
        }
    }
    return dp[n];
}

public int numSquares(int n) {
    List<Integer> squares = new ArrayList<>(); // 存储小于 n 的平方数
    int diff = 3;
    while(square <= n) {
        squares.add(square);
        square += diff;
        diff += 2;
    }
    int[] dp = new int[n + 1];
    for(int i = 1; i <= n; i++) {
        int max = Integer.MAX_VALUE;
        for(int s : squares) {
            if(s > i) break;
            max = Math.min(max, dp[i - s] + 1);
        }
        dp[i] = max;
    }
    return dp[n];
}

public int numDecodings(String s) {
    if(s == null || s.length() == 0) return 0;
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = s.charAt(0) == '0' ? 0 : 1;
    for(int i = 2; i <= n; i++) {
        int one = Integer.valueOf(s.substring(i - 1, i));
        if(one != 0) dp[i] += dp[i - 1];
        if(s.charAt(i - 2) == '0') continue;
        int two = Integer.valueOf(s.substring(i - 2, i));
        if(two <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if(i == 0) dp[j] = 1;
            else if(j != 0) dp[j] = dp[j] + dp[j - 1];
        }
    }
    return dp[n - 1];
}

public int minPathSum(int[][] grid) {
    if(grid.length == 0 || grid[0].length == 0) return 0;
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            if(j == 0) dp[0] = dp[0] + grid[i][0];
            else if(i == 0) dp[j] = dp[j - 1] + grid[0][j];
            else dp[j] = Math.min(dp[j - 1], dp[j]) + grid[i][j];
        }
    }
    return dp[n - 1];
}

public int climbStairs(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    // 前一个楼梯、后一个楼梯
    int pre1 = 2, pre2 = 1;
    for(int i = 2; i < n; i++){
        int cur = pre1 + pre2;
        pre2 = pre1;
        pre1 = cur;
    }
    return pre1;
}

public int rob(int[] nums) {
    int n = nums.length;
    if(n == 0) return 0;
    if(n == 1) return nums[0];
    if(n == 2) return Math.max(nums[0], nums[1]);
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = nums[1];
    dp[2] = nums[0] + nums[2];
    for(int i = 3; i < n; i++){
        dp[i] = Math.max(dp[i -2], dp[i - 3]) + nums[i];
    }
    return Math.max(dp[n - 1], dp[n - 2]);
}

public int rob(int[] nums) {
    int n = nums.length;
    if(n == 0) return 0;
    if(n == 1) return nums[0];
    if(n == 2) return Math.max(nums[0], nums[1]);
    int pre3 = nums[0], pre2 = nums[1], pre1 = nums[2] + nums[0];
    for(int i = 3; i < n; i++){
        int cur = Math.max(pre2, pre3) + nums[i];
        pre3 = pre2;
        pre2 = pre1;
        pre1 = cur;
    }
    return Math.max(pre1, pre2);
}

public int rob(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int n = nums.length;
    if(n == 1) return nums[0];
    return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
}

private int rob(int[] nums, int s, int e) {
    int n = nums.length;
    if(e - s == 0) return nums[s];
    if(e - s == 1) return Math.max(nums[s], nums[s + 1]);
    int[] dp = new int[n];
    dp[s] = nums[s];
    dp[s + 1] = nums[s + 1];
    dp[s + 2] = nums[s] + nums[s + 2];
    for (int i = s + 3; i <= e; i++) {
        dp[i] = Math.max(dp[i - 2], dp[i - 3]) + nums[i];
    }
    return Math.max(dp[e], dp[e - 1]);
}

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    for(int i = 0; i < n; i++){
        int max = 1;
        for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]) max = Math.max(max, dp[j] + 1);
        }
        dp[i] = max;
    }
    int ret = 0;
    for(int i = 0; i < n; i++){
        ret = Math.max(ret, dp[i]);
    }
    return ret;
}

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] tails = new int[n];
    int size = 0;
    for(int i = 0; i < n; i++){
        int idx = binarySearch(tails, 0, size, nums[i]);
        tails[idx] = nums[i];
        if(idx == size) size++;
    }
    return size;
}

private int binarySearch(int[] nums, int sIdx, int eIdx, int key){
    while(sIdx < eIdx){
        int mIdx = sIdx + (eIdx - sIdx) / 2;
        if(nums[mIdx] == key) return mIdx;
        else if(nums[mIdx] > key) eIdx = mIdx;
        else sIdx = mIdx + 1;
    }
    return sIdx;
}

public int wiggleMaxLength(int[] nums) {
    int len = nums.length;
    if (len == 0) return 0;
    int up = 1, down = 1;
    for (int i = 1; i < len; i++) {
        if (nums[i] > nums[i - 1]) up = down + 1;
        else if (nums[i] < nums[i - 1]) down = up + 1;
    }
    return Math.max(up, down);
}

public int lengthOfLCS(int[] nums1, int[] nums2) {
    int n1 = nums1.length, n2 = nums2.length;
    int[][] dp = new int[n1 + 1][n2 + 1];
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++) {
            if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n1][n2];
}

public int knapsack(int W, int N, int[] weights, int[] values) {
    int[][] dp = new int[N][W];
    for (int i = W - 1; i >= 0; i--) {
        dp[0][i] = i > weights[0] ? values[0] : 0;
    }
    for (int i = 1; i < N; i++) {
        for (int j = W - 1; j >= weights[i]; j--) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
        }
        for (int j = weights[i - 1] - 1; j >= 0; j--) {
            dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[N - 1][W - 1];
}

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum % 2 != 0) {
        return false;
    }
    int W = sum / 2;
    boolean[] dp = new boolean[W + 1];
    int n = nums.length;
    for(int i = 0; i <= W; i++) {
        if(nums[0] == i) dp[i] = true;
    }
    for(int i = 1; i < n; i++) {
        for(int j = W; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }

    return dp[W];
}

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (String word : wordDict) {
            if (word.length() <= i
                    && word.equals(s.substring(i - word.length(), i))) {
                dp[i] = dp[i] || dp[i - word.length()];
            }
        }
    }
    return dp[n];
}

public int findTargetSumWays(int[] nums, int S) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    if (sum < S || (sum + S) % 2 == 1) {
        return 0;
    }
    return subsetSum(nums, (sum + S) >>> 1);
}

private int subsetSum(int[] nums, int targetSum) {
    Arrays.sort(nums);
    int[] dp = new int[targetSum + 1];
    dp[0] = 1;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        for (int j = targetSum; j >= num; j--) {
            dp[j] = dp[j] + dp[j - num];
        }
    }
    return dp[targetSum];
}

public int findMaxForm(String[] strs, int m, int n) {
    if (strs == null || strs.length == 0) return 0;
    int l = strs.length;
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i < l; i++) {
        String s = strs[i];
        int ones = 0, zeros = 0;
        for (char c : s.toCharArray()) {
            if (c == '0') zeros++;
            else if (c == '1') ones++;
        }
        for (int j = m; j >= zeros; j--) {
            for (int k = n; k >= ones; k--) {
                if (zeros <= j && ones <= k) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zeros][k - ones] + 1);
                }
            }
        }
    }
    return dp[m][n];
}

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.length; j++) {
            if (coins[j] <= i) {
                dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 1; i <= target; i++) {
        for (int j = 0; j < nums.length; j++) {
            if(nums[j] <= i) {
                dp[i] += dp[i - nums[j]];
            }
        }
    }
    return dp[target];
}

public int maxProfit(int[] prices) {
    int firstBuy = Integer.MIN_VALUE, firstSell = 0;
    int secondBuy = Integer.MIN_VALUE, secondSell = 0;
    for (int curPrice : prices) {
        if (firstBuy < -curPrice) firstBuy = -curPrice;
        if (firstSell < firstBuy + curPrice) firstSell = firstBuy + curPrice;
        if (secondBuy < firstSell - curPrice) secondBuy = firstSell - curPrice;
        if (secondSell < secondBuy + curPrice) secondSell = secondBuy + curPrice;
    }
    return secondSell;
}

public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    if (k >= n/2) {
        int maxPro = 0;
        for (int i = 1; i < n; i++) {
            if (prices[i] > prices[i-1])
                maxPro += prices[i] - prices[i-1];
        }
        return maxPro;
    }
    int[][] dp = new int[k + 1][n];
    for (int i = 1; i <= k; i++) {
        int localMax = dp[i - 1][0] - prices[0];
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i][j - 1], prices[j] + localMax);
            localMax = Math.max(localMax, dp[i - 1][j] - prices[j]);
        }
    }
    return dp[k][n - 1];
}

class NumArray {

    int[] nums;

    public NumArray(int[] nums) {
        for(int i = 1; i < nums.length; i++)
            nums[i] += nums[i - 1];
        this.nums = nums;
    }

    public int sumRange(int i, int j) {
        return i == 0 ? nums[j] : nums[j] - nums[i - 1];
    }
}

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] sum = new int[n];
    sum[0] = nums[0];
    int max = sum[0];
    for(int i = 1; i < n; i++){
        sum[i] = (sum[i-1] > 0 ? sum[i-1] : 0) + nums[i];
        max = Math.max(max, sum[i]);
    }
    return max;
}

public int maxSubArray(int[] nums) {
    int max = nums[0];
    int oldsum = nums[0];
    for (int i = 1; i < nums.length; i++) {
        oldsum = (oldsum > 0 ? oldsum: 0) + nums[i];
        max = Math.max(max, oldsum);
    }
    return max;
}

public int numberOfArithmeticSlices(int[] A) {
    int n = A.length;
    int[] dp = new int[n];
    for(int i = 2; i < n; i++) {
        if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]) {
            dp[i] = dp[i - 1] + 1;
        }
    }
    int ret = 0;
    for(int cnt : dp) {
        ret += cnt;
    }
    return ret;
}

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) continue;
            dp[i][j] = word1.charAt(i - 1) == word2.charAt(j - 1) ? dp[i - 1][j - 1] + 1
                    : Math.max(dp[i][j - 1], dp[i - 1][j]);
        }
    }
    return m + n - 2 * dp[m][n];
}

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) return 0;
    int n = prices.length;
    int[] s0 = new int[n];
    int[] s1 = new int[n];
    int[] s2 = new int[n];
    s0[0] = 0;
    s1[0] = -prices[0];
    s2[0] = Integer.MIN_VALUE;
    for (int i = 1; i < n; i++) {
        s0[i] = Math.max(s0[i - 1], s2[i - 1]);
        s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i]);
        s2[i] = Math.max(s2[i - 1], s1[i - 1] + prices[i]);
    }
    return Math.max(s0[n - 1], s2[n - 1]);
}

    public int[] countBits(int num) {
        int[] ret = new int[num + 1];
        for(int i = 1; i <= num; i++){
            ret[i] = ret[i&(i-1)] + 1;
        }
        return ret;
    }

public int findLongestChain(int[][] pairs) {
    if(pairs == null || pairs.length == 0) {
        return 0;
    }
    Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
    int n = pairs.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(pairs[i][0] > pairs[j][1]){
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int ret = 0;
    for(int num : dp) {
        ret = Math.max(ret, num);
    }
    return ret;
}

public int maxProfit(int[] prices) {
    int n = prices.length;
    if(n == 0) return 0;
    int soFarMin = prices[0];
    int max = 0;
    for(int i = 1; i < n; i++){
        if(soFarMin > prices[i]) soFarMin = prices[i];
        else max = Math.max(max, prices[i] - soFarMin);
    }
    return max;
}

public int minSteps(int n) {
    int[] dp = new int[n + 1];
    for (int i = 2; i <= n; i++) {
        dp[i] = i;
        for (int j = i - 1; j >= 0; j--) {
            if (i % j == 0) {
                dp[i] = dp[j] + dp[i / j];
                break;
            }
        }
    }
    return dp[n];
}

public int minSteps(int n) {
    if (n == 1) return 0;
    for (int i = 2; i <= Math.sqrt(n); i++) {
        if (n % i == 0) return i + minSteps(n / i);
    }
    return n;
}

public int countPrimes(int n) {
    boolean[] notPrimes = new boolean[n + 1];
    int cnt = 0;
    for(int i = 2; i < n; i++){
        if(notPrimes[i]) continue;
        cnt++;
        // 从 i * i 开始，因为如果 k < i，那么 k * i 在之前就已经被去除过了
        for(long j = (long) i * i; j < n; j += i){
            notPrimes[(int) j] = true;
        }
    }
    return cnt;
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b){
    return a * b / gcd(a, b);
}

public String convertToBase7(int num) {
    if (num < 0) {
        return '-' + convertToBase7(-num);
    }
    if (num < 7) {
        return num + "";
    }
    return convertToBase7(num / 7) + num % 7;
}

public String toHex(int num) {
    char[] map = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
    if(num == 0) return "0";
    String ret = "";
    while(num != 0){
        ret = map[(num & 0b1111)] + ret;
        num >>>= 4;
    }
    return ret;
}

public int trailingZeroes(int n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5);
}

public String addBinary(String a, String b) {
    int i = a.length() - 1, j = b.length() - 1, carry = 0;
    String str = "";
    while(i >= 0 || j >= 0){
        if(i >= 0 && a.charAt(i--) == '1') carry++;
        if(j >= 0 && b.charAt(j--) == '1') carry++;
        str = (carry % 2) + str;
        carry /= 2;
    }
    if(carry == 1) str = "1" + str;
    return str;
}

public String addStrings(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    for(int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--){
        int x = i < 0 ? 0 : num1.charAt(i) - '0';
        int y = j < 0 ? 0 : num2.charAt(j) - '0';
        sb.append((x + y + carry) % 10);
        carry = (x + y + carry) / 10;
    }
    return sb.reverse().toString();
}

public int minMoves2(int[] nums) {
    Arrays.sort(nums);
    int ret = 0;
    int l = 0, h = nums.length - 1;
    while(l <= h) {
        ret += nums[h] - nums[l];
        l++;
        h--;
    }
    return ret;
}

public int minMoves2(int[] nums) {
    int ret = 0;
    int n = nums.length;
    int median = quickSelect(nums, 0, n - 1, n / 2 + 1);
    for(int num : nums) ret += Math.abs(num - median);
    return ret;
}

private int quickSelect(int[] nums, int start, int end, int k) {
    int l = start, r = end, privot = nums[(l + r) / 2];
    while(l <= r) {
        while(nums[l] < privot) l++;
        while(nums[r] > privot) r--;
        if(l >= r) break;
        swap(nums, l, r);
        l++; r--;
    }
    int left = l - start + 1;
    if(left > k) return quickSelect(nums, start, l - 1, k);
    if(left == k && l == r) return nums[l];
    int right = r - start + 1;
    return quickSelect(nums, r + 1, end, k - right);
}

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

public int majorityElement(int[] nums) {
    Arrays.sort(nums);
    return nums[nums.length / 2];
}

public int majorityElement(int[] nums) {
    int cnt = 0, majority = 0;
    for(int i = 0; i < nums.length; i++){
        if(cnt == 0) {
            majority = nums[i];
            cnt++;
        }
        else if(majority == nums[i]) cnt++;
        else cnt--;
    }
    return majority;
}

public boolean isPerfectSquare(int num) {
    int subNum = 1;
    while (num > 0) {
        num -= subNum;
        subNum += 2;
    }
    return num == 0;
}

public boolean isPowerOfThree(int n) {
    return n > 0 && (1162261467 % n == 0);
}

public int maximumProduct(int[] nums) {
    int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
    for (int n : nums) {
        if (n > max1) {
            max3 = max2;
            max2 = max1;
            max1 = n;
        } else if (n > max2) {
            max3 = max2;
            max2 = n;
        } else if (n > max3) {
            max3 = n;
        }

        if (n < min1) {
            min2 = min1;
            min1 = n;
        } else if (n < min2) {
            min2 = n;
        }
    }
    return Math.max(max1*max2*max3, max1*min1*min2);
}

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] ret = new int[n];
    ret[0] = 1;
    for(int i = 1; i < n; i++) {
        ret[i] = ret[i - 1] * nums[i - 1];
    }
    int right = 1;
    for(int i = n - 1; i >= 0; i--) {
        ret[i] *= right;
        right *= nums[i];
    }
    return ret;
}

class  MyQueue {
    private Stack<Integer> st = new Stack();

    public void push(int x) {
        Stack<Integer> temp = new Stack();
        while(!st.isEmpty()){
            temp.push(st.pop());
        }
        st.push(x);
        while(!temp.isEmpty()){
            st.push(temp.pop());
        }
    }

    public int pop() {
        return st.pop();
    }

    public int peek() {
        return st.peek();
    }

    public boolean empty() {
        return st.isEmpty();
    }
}

class  MyQueue {
    private Stack<Integer> in = new Stack();
    private Stack<Integer> out = new Stack();

    public void push(int x) {
        in.push(x);
    }

    public int pop() {
        in2out();
        return out.pop();
    }

    public int peek() {
        in2out();
        return out.peek();
    }

    private void in2out(){
        if(out.isEmpty()){
            while(!in.isEmpty()){
                out.push(in.pop());
            }
        }
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

class MyStack {

    private Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    public void push(int x) {
        queue.add(x);
        for(int i = 1; i < queue.size(); i++){ // 翻转
            queue.add(queue.remove());
        }
    }

    public int pop() {
        return queue.remove();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

class MinStack {

    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    private int min;

    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
        min = Integer.MAX_VALUE;
    }

    public void push(int x) {
        dataStack.add(x);
        if(x < min) {
            min = x;
        }
        minStack.add(min);
    }

    public void pop() {
        dataStack.pop();
        minStack.pop();
        if(!minStack.isEmpty()) {
            min = minStack.peek();
        } else{
            min = Integer.MAX_VALUE;
        }
    }

    public int top() {
        return dataStack.peek();
    }

    public int getMin() {
        return min;
    }
}

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();
    for(int i = 0; i < s.length(); i++){
        char c = s.charAt(i);
        if(c == '(' || c == '{' || c == '[') stack.push(c);
        else{
            if(stack.isEmpty()) return false;
            char cStack = stack.pop();
            if(c == ')' && cStack != '(' ||
              c == ']' && cStack != '[' ||
              c == '}' && cStack != '{' ) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] ret = new int[n];
    Stack<Integer> stack = new Stack<>();
    for(int i = 0; i < n; i++) {
        while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            ret[idx] = i - idx;
        }
        stack.add(i);
    }
    return ret;
}

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();
    for(int num : nums2){
        while(!stack.isEmpty() && num > stack.peek()){
            map.put(stack.pop(), num);
        }
        stack.add(num);
    }
    int[] ret = new int[nums1.length];
    for(int i = 0; i < nums1.length; i++){
        if(map.containsKey(nums1[i])) ret[i] = map.get(nums1[i]);
        else ret[i] = -1;
    }
    return ret;
}

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length, next[] = new int[n];
    Arrays.fill(next, -1);
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n * 2; i++) {
        int num = nums[i % n];
        while (!stack.isEmpty() && nums[stack.peek()] < num)
            next[stack.pop()] = num;
        if (i < n) stack.push(i);
    }
    return next;
}