class Solution {
    public int search(int[] nums, int target) {
        // left / right：当前搜索闭区间两端
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1); // 防溢出的中点
            if (nums[mid] == target) {
                int ans = mid;
                return ans;
            }
            if (nums[mid] < target) {
                left = mid + 1; // target 只可能在右半
            } else {
                right = mid - 1; // target 只可能在左半
            }
        }
        return -1;
    }
}

int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

class Solution {
    public int removeElement(int[] nums, int val) {
        // slow：下一个「保留元素」应写入的下标，也是当前有效长度
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast]; // 保留该元素
                slow++;
            }
            // nums[fast] == val：跳过，相当于删除
        }
        int ans = slow;
        return ans;
    }
}

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        // left / right：原数组两端；write：结果从后往前填
        int left = 0;
        int right = n - 1;
        int write = n - 1;
        while (left <= right) {
            int leftAbs = Math.abs(nums[left]);
            int rightAbs = Math.abs(nums[right]);
            if (leftAbs > rightAbs) {
                ans[write] = leftAbs * leftAbs;
                left++;
            } else {
                ans[write] = rightAbs * rightAbs;
                right--;
            }
            write--;
        }
        return ans;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        // left：窗口左端；windowSum：当前窗口 [left, right] 元素和
        int left = 0;
        int windowSum = 0;
        for (int right = 0; right < n; right++) {
            windowSum += nums[right];
            while (windowSum >= target) {
                ans = Math.min(ans, right - left + 1); // 当前合法窗口长度
                windowSum -= nums[left];
                left++; // 尽量缩短窗口
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        // top/bottom/left/right：当前未填完的矩形边界
        int top = 0;
        int bottom = n - 1;
        int left = 0;
        int right = n - 1;
        int k = 1; // 下一个要填的数字

        while (true) {
            // 上边：左 → 右
            for (int i = left; i <= right; i++) {
                ans[top][i] = k++;
            }
            if (++top > bottom) {
                break; // 上下边界交错，整圈结束
            }

            // 右边：上 → 下
            for (int i = top; i <= bottom; i++) {
                ans[i][right] = k++;
            }
            if (--right < left) {
                break;
            }

            // 下边：右 → 左
            for (int i = right; i >= left; i--) {
                ans[bottom][i] = k++;
            }
            if (--bottom < top) {
                break;
            }

            // 左边：下 → 上
            for (int i = bottom; i >= top; i--) {
                ans[i][left] = k++;
            }
            if (++left > right) {
                break;
            }
        }
        return ans;
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        // prefix[i] = arr[0] + ... + arr[i-1]；prefix[0] = 0，方便区间差分
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }

        // 区间 [a, b]（含端点）的和 = prefix[b+1] - prefix[a]
        while (sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int ans = prefix[b + 1] - prefix[a];
            System.out.println(ans);
        }
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        // rowSum[i]：第 i 行元素之和；colSum[j]：第 j 列元素之和
        int[] rowSum = new int[n];
        int[] colSum = new int[m];
        int total = 0; // 整块土地总价值

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int v = sc.nextInt();
                rowSum[i] += v;
                colSum[j] += v;
                total += v;
            }
        }

        int ans = Integer.MAX_VALUE;

        // 横切：在第 i 行与第 i+1 行之间切开（上半含 [0..i]）
        int prefix = 0;
        for (int i = 0; i < n - 1; i++) {
            prefix += rowSum[i];
            ans = Math.min(ans, Math.abs(total - 2 * prefix)); // |total-prefix - prefix|
        }

        // 纵切：在第 j 列与第 j+1 列之间切开（左半含 [0..j]）
        prefix = 0;
        for (int j = 0; j < m - 1; j++) {
            prefix += colSum[j];
            ans = Math.min(ans, Math.abs(total - 2 * prefix));
        }

        System.out.println(ans);
    }
}

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head); // 便于删除原头节点
        ListNode prev = dummy;
        ListNode curr = dummy.next;

        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next; // 跳过当前节点
                curr = prev.next;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }

        ListNode ans = dummy.next;
        return ans;
    }
}

class MyLinkedList {
    // 双向链表节点
    private static class Node {
        int val;
        Node prev;
        Node next;

        Node(int val) {
            this.val = val;
        }
    }

    private final Node head; // 头哨兵，不存数据
    private final Node tail; // 尾哨兵，不存数据
    private int size; // 真实节点个数

    public MyLinkedList() {
        head = new Node(0);
        tail = new Node(0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    // 返回下标 index 处的真实节点；约定调用方保证 0 <= index < size
    // 从更近的一端走，减少平均步数
    private Node getNode(int index) {
        Node curr;
        if (index < size / 2) {
            curr = head.next;
            for (int i = 0; i < index; i++) {
                curr = curr.next;
            }
        } else {
            curr = tail.prev;
            for (int i = size - 1; i > index; i--) {
                curr = curr.prev;
            }
        }
        return curr;
    }

    // 在节点 curr 之前插入值为 val 的新节点
    private void insertBefore(Node curr, int val) {
        Node node = new Node(val);
        Node prev = curr.prev;
        // prev <-> node <-> curr
        prev.next = node;
        node.prev = prev;
        node.next = curr;
        curr.prev = node;
        size++;
    }

    // 删除节点 curr（已保证是真实节点）
    private void remove(Node curr) {
        curr.prev.next = curr.next;
        curr.next.prev = curr.prev;
        size--;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        int ans = getNode(index).val;
        return ans;
    }

    public void addAtHead(int val) {
        insertBefore(head.next, val); // 插在第一个真实节点前（或 tail 前）
    }

    public void addAtTail(int val) {
        insertBefore(tail, val); // O(1) 尾插
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {
            return; // 越界不插入
        }
        if (index < 0) {
            index = 0; // 题意：负下标视为插到头部（约束下通常不会出现）
        }
        if (index == size) {
            insertBefore(tail, val); // 追加到末尾
        } else {
            insertBefore(getNode(index), val);
        }
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        remove(getNode(index));
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        // prev：已反转部分的头；初始 null 表示新链表为空
        ListNode prev = null;
        ListNode curr = head; // 当前待处理节点

        while (curr != null) {
            ListNode next = curr.next; // 先存后继，改指针后才能继续往后走
            curr.next = prev; // 当前节点头插到已反转链表
            prev = curr;
            curr = next;
        }

        ListNode ans = prev; // 扫完后 prev 指向原末节点，即新头
        return ans;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        // dummy：哑结点，方便交换前两个节点时改「头」
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy; // 当前待交换对的前驱
        ListNode curr = dummy.next; // 对中第一个节点

        while (curr != null && curr.next != null) {
            ListNode nextNode = curr.next; // 对中第二个节点
            // 交换：prev -> nextNode -> curr -> (原 nextNode 之后)
            prev.next = nextNode;
            curr.next = nextNode.next;
            nextNode.next = curr;
            // 移动到下一对：此时 curr 已是交换后的第二个节点
            prev = curr;
            curr = curr.next;
        }

        ListNode ans = dummy.next;
        return ans;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // dummy：便于删除头节点时统一改指针
        ListNode dummy = new ListNode(0, head);
        ListNode slow = dummy; // 最终停在待删节点的前驱
        ListNode fast = dummy;

        // 快指针先走 n 步，使快慢间距为 n
        while (n > 0) {
            fast = fast.next;
            n--;
        }

        // 同步前进；fast 到末节点时，slow 的 next 即倒数第 n 个
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next; // 跳过待删节点
        ListNode ans = dummy.next;
        return ans;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;

        // 不相交时会在 null 处相遇并退出；相交时在第一个公共节点相遇
        while (pA != pB) {
            // 走完本链后切换到另一条，对齐「独有段」长度差
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        ListNode ans = pA; // 交点，或 null
        return ans;
    }
}

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        // 第一阶段：判断是否有环；相遇点在环内某处
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 第二阶段：一指针回起点，同步前进找入口
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                ListNode ans = slow; // 环入口
                return ans;
            }
        }
        return null; // 无环
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false; // 长度不同必不是异位词
        }

        int[] cnt = new int[26]; // cnt[c-'a']：字母 c 在 s 中比 t 中多出的次数
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
            cnt[t.charAt(i) - 'a']--;
        }

        for (int c : cnt) {
            if (c != 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums1) {
            set.add(num); // nums1 中出现过的数
        }

        Set<Integer> ansSet = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                ansSet.add(num); // 两边都有，Set 保证唯一
            }
        }

        // HashSet 无法直接转 int[]，逐个拆箱写入
        int[] ans = new int[ansSet.size()];
        int i = 0;
        for (int num : ansSet) {
            ans[i++] = num;
        }
        return ans;
    }
}

class Solution {
    // 计算各位数字的平方和
    private int getNext(int n) {
        int sum = 0;
        while (n > 0) {
            int d = n % 10;
            sum += d * d;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = getNext(n);

        // 快慢相遇：要么都到 1，要么在非 1 的环里
        while (fast != 1 && slow != fast) {
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return fast == 1;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // map：数值 -> 下标（只存当前下标左侧的元素）
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (map.containsKey(need)) {
                int[] ans = new int[]{map.get(need), i};
                return ans;
            }
            map.put(nums[i], i); // 当前数留给后面的元素匹配
        }
        return new int[]{-1, -1}; // 题保证有解，不会走到这
    }
}

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        // sum12 -> 该两数之和出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int a : nums1) {
            for (int b : nums2) {
                int sum = a + b;
                cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
            }
        }

        int ans = 0;
        for (int c : nums3) {
            for (int d : nums4) {
                // 需要 a+b == -(c+d)
                ans += cnt.getOrDefault(-(c + d), 0);
            }
        }
        return ans;
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false; // 赎金信更长则必不够用
        }

        int[] cnt = new int[26]; // magazine 中各字母剩余次数
        for (char ch : magazine.toCharArray()) {
            cnt[ch - 'a']++;
        }
        for (char ch : ransomNote.toCharArray()) {
            if (--cnt[ch - 'a'] < 0) {
                return false; // 该字母用超了
            }
        }
        return true;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 2; i++) {
            // 最小的三个数都 > 0，后面更大，不可能再有和为 0
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            // 相同的第一个数只枚举一次，避免重复三元组
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 当前数即使配上最大的两个数仍 < 0，换更大的 nums[i]
            if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {
                continue;
            }

            int left = i + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    // 跳过与刚加入解相同的左右值，保证不重复
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }
        return ans;
    }
}

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;

        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // 第一个数去重
            }
            // 最小四数和已超过 target，后面更大，结束
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            // 当前 nums[i] 配上最大三数仍不够，换更大的 i
            if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
                continue;
            }

            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue; // 第二个数去重
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
                    continue;
                }

                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    // 必须先把其中一个扩成 long，避免 int 溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return ans;
    }
}

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        int n = ch.length;
        // 每 2k 一段，只处理该段前 k 个（或不足 k 的剩余）
        for (int start = 0; start < n; start += 2 * k) {
            int end = Math.min(start + k - 1, n - 1);
            reverse(ch, start, end);
        }
        return new String(ch); // char[] → String
    }

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

class Solution {
    // 经典：空格 → %20
    public String replaceSpace(String s) {
        int spaceCnt = 0;
        for (char c : s.toCharArray()) {
            if (c == ' ') {
                spaceCnt++;
            }
        }

        // 每个空格多占 2 格（' ' → "%20"）
        char[] ch = new char[s.length() + spaceCnt * 2];
        int i = s.length() - 1; // 原串从后往前
        int j = ch.length - 1;  // 新数组从后往前填，避免覆盖

        while (i >= 0) {
            char c = s.charAt(i);
            if (c == ' ') {
                ch[j--] = '0';
                ch[j--] = '2';
                ch[j--] = '%';
            } else {
                ch[j--] = c;
            }
            i--;
        }
        return new String(ch);
    }
}

class Solution {
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        // 1. 清除多余空格，返回有效长度
        int len = removeSpace(arr);
        // 2. 反转整个有效区间
        reverse(arr, 0, len - 1);
        // 3. 再反转每个单词
        int slow = 0;
        for (int fast = 0; fast < len; fast++) {
            if (arr[fast] == ' ') {
                reverse(arr, slow, fast - 1);
                slow = fast + 1;
            }
        }
        reverse(arr, slow, len - 1); // 最后一个单词

        return new String(arr, 0, len);
    }

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

    // 原地压缩：单词之间只保留一个空格，去掉首尾空格；返回新长度
    private int removeSpace(char[] arr) {
        int n = arr.length;
        int slow = 0;
        int fast = 0;
        while (fast < n) {
            while (fast < n && arr[fast] == ' ') {
                fast++; // 跳过空格
            }
            if (fast >= n) {
                break;
            }
            if (slow > 0) {
                arr[slow++] = ' '; // 单词之间补一个空格
            }
            while (fast < n && arr[fast] != ' ') {
                arr[slow++] = arr[fast++]; // 拷贝单词
            }
        }
        return slow;
    }
}

class Solution {
    // 经典接口；LCR 182 可把方法名改成 dynamicPassword，参数同理
    public String reverseLeftWords(String s, int k) {
        char[] ch = s.toCharArray();
        int n = ch.length;
        // 整串反转 → 反转前 n-k → 反转后 k，等价于左旋 k
        reverse(ch, 0, n - 1);
        reverse(ch, 0, n - k - 1);
        reverse(ch, n - k, n - 1);
        return new String(ch);
    }

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

class Solution {
    public int strStr(String haystack, String needle) {
        int m = needle.length();
        if (m == 0) {
            return 0; // 空模式约定返回 0（现约束下通常不会出现）
        }

        // next[i]：needle[0..i] 的最长相等前后缀长度（不减一）
        int[] next = new int[m];
        for (int right = 1, left = 0; right < m; right++) {
            while (left > 0 && needle.charAt(left) != needle.charAt(right)) {
                left = next[left - 1]; // 前后缀继续缩短
            }
            if (needle.charAt(left) == needle.charAt(right)) {
                left++;
            }
            next[right] = left;
        }

        // i 扫 haystack，j 表示当前已匹配到 needle 的长度
        for (int i = 0, j = 0; i < haystack.length(); i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                int ans = i - m + 1; // 匹配起点
                return ans;
            }
        }
        return -1;
    }
}

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        // next[i]：s[0..i] 的最长相等前后缀长度
        int[] next = new int[n];
        for (int right = 1, left = 0; right < n; right++) {
            while (left > 0 && s.charAt(left) != s.charAt(right)) {
                left = next[left - 1];
            }
            if (s.charAt(left) == s.charAt(right)) {
                left++;
            }
            next[right] = left;
        }

        int longest = next[n - 1]; // 整串最长相等前后缀
        int period = n - longest;   // 最小周期长度
        // 能由子串重复构成 ⟺ 存在周期 period，且 period 整除 n，且不是「整串自身」
        return longest > 0 && n % period == 0;
    }
}

class MyQueue {
    private final Deque<Integer> in;  // 入队栈
    private final Deque<Integer> out; // 出队栈

    public MyQueue() {
        in = new ArrayDeque<>();
        out = new ArrayDeque<>();
    }

    // 只往 in 压，对应队列尾
    public void push(int x) {
        in.push(x);
    }

    // out 为空时，把 in 倒入 out，此时 out 栈顶即队首
    private void transfer() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) {
                out.push(in.pop());
            }
        }
    }

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

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

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

class MyStack {
    private final Deque<Integer> q; // 只用队列的入队尾 / 出队首

    public MyStack() {
        q = new ArrayDeque<>();
    }

    // 新元素入队后，把旧元素轮转到后面，使队首 = 栈顶
    public void push(int x) {
        int n = q.size();
        q.offer(x);
        for (int i = 0; i < n; i++) {
            q.offer(q.poll());
        }
    }

    public int pop() {
        return q.poll(); // 队首即栈顶
    }

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

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

class MyStack {
    private Deque<Integer> q1; // 始终存放「完整栈」，队首为栈顶
    private Deque<Integer> q2; // 辅助队列，push 时暂存

    public MyStack() {
        q1 = new ArrayDeque<>();
        q2 = new ArrayDeque<>();
    }

    public void push(int x) {
        q2.offer(x); // 新元素先进入空的辅助队列（成为队首）
        while (!q1.isEmpty()) {
            q2.offer(q1.poll()); // 旧元素接到新元素后面
        }
        // 交换：让 q1 重新指向完整栈
        Deque<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
    }

    public int pop() {
        return q1.poll();
    }

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

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

class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(')'); // 压入期望的右括号
            } else if (ch == '[') {
                stack.push(']');
            } else if (ch == '{') {
                stack.push('}');
            } else {
                // 右括号：栈空或与期望不符
                if (stack.isEmpty() || stack.pop() != ch) {
                    return false;
                }
            }
        }
        return stack.isEmpty(); // 全部匹配完才合法
    }
}

class Solution {
    public String removeDuplicates(String s) {
        StringBuilder stack = new StringBuilder(); // 栈顶 = 末尾字符
        for (char ch : s.toCharArray()) {
            int n = stack.length();
            if (n > 0 && stack.charAt(n - 1) == ch) {
                stack.deleteCharAt(n - 1); // 与栈顶相同，消掉一对
            } else {
                stack.append(ch);
            }
        }
        return stack.toString();
    }
}

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            // 数字：长度>1（如 -11）或首字符是数字
            if (token.length() > 1 || Character.isDigit(token.charAt(0))) {
                stack.push(Integer.parseInt(token));
                continue;
            }
            int right = stack.pop(); // 后弹出的是右操作数
            int left = stack.pop();
            switch (token) {
                case "+":
                    stack.push(left + right);
                    break;
                case "-":
                    stack.push(left - right);
                    break;
                case "*":
                    stack.push(left * right);
                    break;
                case "/":
                    stack.push(left / right); // 向零截断，Java int 除法即如此
                    break;
                default:
                    break;
            }
        }
        int ans = stack.peek();
        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        // 存下标；对应值单调递减，队首为窗口最大值
        Deque<Integer> deque = new ArrayDeque<>();

        for (int j = 0; j < n; j++) {
            // 新元素更大则挤掉队尾更小的候选
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[j]) {
                deque.pollLast();
            }
            deque.offerLast(j);

            int left = j - k + 1; // 当前窗口左端
            if (left < 0) {
                continue; // 窗口尚未成型
            }
            // 队首下标已滑出窗口则丢弃
            while (deque.peekFirst() < left) {
                deque.pollFirst();
            }
            ans[left] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        // buckets[f]：出现次数恰好为 f 的所有数值；下标最大为 n
        List<Integer>[] buckets = new List[nums.length + 1];
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            int f = e.getValue();
            if (buckets[f] == null) {
                buckets[f] = new ArrayList<>();
            }
            buckets[f].add(e.getKey());
        }

        int[] ans = new int[k];
        int idx = 0;
        // 从高频到低频取
        for (int f = buckets.length - 1; f >= 0 && idx < k; f--) {
            if (buckets[f] == null) {
                continue;
            }
            for (int num : buckets[f]) {
                ans[idx++] = num;
                if (idx == k) {
                    return ans;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        // 小根堆：堆顶是当前堆中频次最小的；大小超过 k 就丢掉它
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            pq.offer(new int[]{e.getKey(), e.getValue()});
            if (pq.size() > k) {
                pq.poll();
            }
        }

        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            ans[i] = pq.poll()[0]; // 弹出顺序是频次升序，倒着填可略好看
        }
        return ans;
    }
}