def max_value(arr):
    '''给定一个数组，在arr[l...r]范围上，返回最大值'''
    return f(arr, 0, len(arr) - 1)

def f(arr, l, r):
    # arr[l...r] 范围上的最大值
    if l == r:
        # 递归基：当左右下标相等时，区间只有一个数，直接返回
        return arr[l]
    m = (l + r) // 2  # 找到中点
    lmax = f(arr, l, m)        # 递归求左半部分最大值
    rmax = f(arr, m + 1, r)    # 递归求右半部分最大值
    return max(lmax, rmax)     # 返回左右部分的最大值

# 归并排序：T(n) = 2*T(n/2) + O(n)
# a=2, b=2, c=1
# log₂(2) = 1 = c，所以复杂度为 O(n*logn)

# 二分查找：T(n) = 1*T(n/2) + O(1)  
# a=1, b=2, c=0
# log₂(1) = 0 = c，所以复杂度为 O(logn)

# 快速排序最好情况：T(n) = 2*T(n/2) + O(n)
# 结果同归并排序：O(n*logn)

MAXN = 100001
arr = [0] * MAXN      # 原数组
help_arr = [0] * MAXN # 辅助数组
n = 0                 # 数组长度

def mergeSort1(l, r):
    """
    归并排序递归版
    T(n) = 2 * T(n/2) + O(n)
    根据master公式，时间复杂度O(n * logn)
    空间复杂度O(n)
    """
    if l == r:  # 递归终止条件：只剩一个元素
        return
    m = (l + r) // 2  # 计算中点
    mergeSort1(l, m)      # 递归排序左半部分
    mergeSort1(m + 1, r)  # 递归排序右半部分
    merge(l, m, r)        # 合并

def merge(l, m, r):
    """
    合并两个有序区间 arr[l...m] 和 arr[m+1...r]
    时间复杂度O(n)，其中n = r - l + 1
    """
    i = l      # help数组写指针
    a = l      # 左侧起始指针
    b = m + 1  # 右侧起始指针
    
    # 双指针合并过程
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b] 
            b += 1
        i += 1
    
    # 处理剩余元素
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
        
    # 写回原数组
    for i in range(l, r + 1):
        arr[i] = help_arr[i]

def mergeSort2():
    """
    归并排序非递归版
    时间复杂度O(n * logn)：外层循环O(logn)，内层归并O(n)
    空间复杂度O(n)
    """
    global n
    step = 1  # 步长初始化为1
    
    while step < n:  # 外层控制步长，共O(logn)次
        l = 0  # 每轮从左端开始
        
        while l < n:  # 内层处理每一组
            m = l + step - 1      # 计算中点
            if m + 1 >= n:        # 右半部分越界，跳出
                break
            r = min(l + (step << 1) - 1, n - 1)  # 计算右边界
            merge(l, m, r)        # 合并
            l = r + 1             # 移动到下一组
            
        step <<= 1  # 步长翻倍

def merge(l, m, r):
    """
    合并过程详解：
    1. 双指针扫描：a指向左部分，b指向右部分
    2. 比较合并：较小值写入help_arr，对应指针右移
    3. 剩余处理：一边扫完后，另一边直接复制
    4. 写回原数组：完成排序合并
    """
    i = l      # help_arr写入位置
    a = l      # 左部分起点
    b = m + 1  # 右部分起点
    
    # 两两比较，选择较小值
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b]
            b += 1
        i += 1
    
    # 处理剩余元素（必有一边先结束）
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
    
    # 拷贝回原数组
    for idx in range(l, r + 1):
        arr[idx] = help_arr[idx]

def smallSum(l, r):
    """
    返回arr[l...r]范围上小和的累加和，同时让arr[l..r]变有序
    时间复杂度O(n * logn)
    """
    if l == r:
        return 0
    m = (l + r) // 2
    # 递归统计左右部分和跨区部分的小和
    return smallSum(l, m) + smallSum(m + 1, r) + merge(l, m, r)

def merge(l, m, r):
    """
    统计跨左右产生的小和，同时完成合并
    """
    ans = 0        # 累计小和
    i = l          # 左侧指针
    sum_left = 0   # 累计左侧小于等于当前右侧元素的和
    
    # 统计跨区贡献：对每个右侧元素，统计左侧贡献
    for j in range(m + 1, r + 1):
        # 左侧所有 <= arr[j] 的元素都对arr[j]有贡献
        while i <= m and arr[i] <= arr[j]:
            sum_left += arr[i]  # 累加左侧贡献
            i += 1
        ans += sum_left  # arr[j]的左侧贡献总和
    
    # 正常归并过程
    i = l
    a = l
    b = m + 1
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b]
            b += 1
        i += 1
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
    for idx in range(l, r + 1):
        arr[idx] = help_arr[idx]
    
    return ans

def reversePairs(arr):
    """统计翻转对的主函数"""
    return counts(arr, 0, len(arr) - 1)

def counts(arr, l, r):
    """
    统计l...r范围上翻转对的数量，同时让l...r范围变有序
    时间复杂度O(n * logn)
    """
    if l == r:
        return 0
    m = (l + r) // 2
    # 递归统计左右两边和跨区部分的翻转对数量
    return counts(arr, l, m) + counts(arr, m + 1, r) + merge(arr, l, m, r)

def merge(arr, l, m, r):
    """统计跨区翻转对并完成合并"""
    ans = 0  # 翻转对计数
    j = m + 1  # 右边数组起点
    
    # 统计跨区翻转对
    for i in range(l, m + 1):
        # 找到右侧第一个不满足 arr[i] > 2*arr[j] 的位置
        while j <= r and arr[i] > 2 * arr[j]:
            j += 1
        # 当前i能形成的翻转对数量 = j - (m+1)
        ans += j - m - 1
    
    # 正常merge过程（与归并排序相同）
    i = l
    a = l
    b = m + 1
    while a <= m and b <= r:
        if arr[a] <= arr[b]:
            help_arr[i] = arr[a]
            a += 1
        else:
            help_arr[i] = arr[b]
            b += 1
        i += 1
    while a <= m:
        help_arr[i] = arr[a]
        a += 1
        i += 1
    while b <= r:
        help_arr[i] = arr[b]
        b += 1
        i += 1
    for idx in range(l, r + 1):
        arr[idx] = help_arr[idx]
    
    return ans

def divide_conquer(l, r):
    if l == r:
        return base_case
    
    m = (l + r) // 2
    left_ans = divide_conquer(l, m)
    right_ans = divide_conquer(m + 1, r)
    cross_ans = merge_and_count(l, m, r)  # 关键：统计跨区答案
    
    return left_ans + right_ans + cross_ans

def merge_and_count(l, m, r):
    # 1. 利用左右有序性，统计跨区答案
    cross_count = 0
    # ... 统计逻辑
    
    # 2. 正常的归并排序merge过程
    # ... 合并逻辑
    
    return cross_count

class Solution:
    def sumOfSubMatrix(self, mat, n):
        """
        只需实现核心算法逻辑
        平台自动调用并验证结果
        """
        return self.maxSumSubmatrix(mat, n, n)
    
    def maxSumSubmatrix(self, mat, rows, cols):
        max_sum = float('-inf')
        for i in range(rows):
            arr = [0] * cols  # 辅助数组
            for j in range(i, rows):
                for k in range(cols):
                    arr[k] += mat[j][k]
                max_sum = max(max_sum, self.maxSumSubarray(arr))
        return max_sum
    
    def maxSumSubarray(self, arr):
        max_sum = float('-inf')
        cur = 0
        for num in arr:
            cur += num
            max_sum = max(max_sum, cur)
            cur = max(cur, 0)  # 负数时重置为0
        return max_sum

import sys

def main():
    """
    完整的输入输出处理
    需要自己解析数据格式
    """
    lines = sys.stdin.read().split()
    ptr = 0
    output = []
    
    while ptr < len(lines):
        n = int(lines[ptr])
        ptr += 1
        m = int(lines[ptr])
        ptr += 1
        
        # 构建矩阵
        mat = []
        for i in range(n):
            row = []
            for j in range(m):
                row.append(int(lines[ptr]))
                ptr += 1
            mat.append(row)
        
        # 计算结果
        result = maxSumSubmatrix(mat, n, m)
        output.append(str(result))
    
    # 批量输出
    print('\n'.join(output))

if __name__ == '__main__':
    main()

import sys

# 最高效：适用于已知数据量的场景
lines = sys.stdin.read().split()
ptr = 0

# 逐个解析数据
while ptr < len(lines):
    n = int(lines[ptr])
    ptr += 1
    # 处理数据...

# 适用：需要按行处理不同格式数据
for line in sys.stdin:
    parts = line.strip().split()
    total = sum(int(num) for num in parts)
    print(total)

# 效率低：类似Java的Scanner
n = int(input())  # 大数据时很慢
for i in range(n):
    x = int(input())  # 每次都要系统调用

# 收集所有结果，最后一次性输出
output = []
for i in range(n):
    result = solve(data[i])
    output.append(str(result))

print('\n'.join(output))  # 一次性输出

# 每次print都会刷新缓冲区，效率低
for i in range(n):
    print(solve(data[i]))  # 大数据时很慢

# 全局预分配，避免频繁内存分配
MAXN = 201
MAXM = 201
mat = [[0] * MAXM for _ in range(MAXN)]  # 静态矩阵
arr = [0] * MAXM  # 静态辅助数组

def solve():
    global n, m
    # 复用已分配的空间
    for i in range(n):
        for j in range(m):
            mat[i][j] = read_next_int()
    
    # 使用前先清空
    for i in range(m):
        arr[i] = 0

def solve():
    # 每次都重新分配内存
    mat = []  # 动态创建
    for i in range(n):
        row = []  # 每行都新建
        for j in range(m):
            row.append(read_next_int())
        mat.append(row)

class Code01_FillFunction:
    def sumOfSubMatrix(self, mat, n):
        """主方法，求n×n矩阵的最大子矩阵和"""
        return self.maxSumSubmatrix(mat, n, n)

    @staticmethod
    def maxSumSubmatrix(mat, n, m):
        """求子矩阵的最大累加和"""
        max_sum = float('-inf')
        
        # 枚举上边界
        for i in range(n):
            arr = [0] * m  # 辅助数组，每次重置
            
            # 枚举下边界（从i到n-1）
            for j in range(i, n):
                # 将第j行累加到辅助数组
                for k in range(m):
                    arr[k] += mat[j][k]
                
                # 求当前辅助数组的最大子数组和
                max_sum = max(max_sum, Code01_FillFunction.maxSumSubarray(arr, m))
        
        return max_sum

    @staticmethod
    def maxSumSubarray(arr, m):
        """Kadane算法求最大子数组和"""
        max_sum = float('-inf')
        cur = 0
        
        for i in range(m):
            cur += arr[i]
            max_sum = max(max_sum, cur)
            cur = 0 if cur < 0 else cur  # 负数时重置
        
        return max_sum

import sys

# 静态空间分配，避免频繁内存分配
MAXN = 201
MAXM = 201
mat = [[0] * MAXM for _ in range(MAXN)]
arr = [0] * MAXM
n = m = 0

def main():
    global n, m
    tokens = sys.stdin.read().split()
    idx = 0
    output = []
    
    while idx < len(tokens):
        n = int(tokens[idx])
        idx += 1
        m = int(tokens[idx])
        idx += 1
        
        # 读取矩阵数据到静态空间
        for i in range(n):
            for j in range(m):
                mat[i][j] = int(tokens[idx])
                idx += 1
        
        # 计算结果并收集输出
        output.append(str(maxSumSubmatrix()))
    
    # 批量输出所有结果
    print('\n'.join(output))

def maxSumSubmatrix():
    """使用静态空间的子矩阵最大和算法"""
    max_sum = float('-inf')
    
    for i in range(n):
        # 清空辅助数组（复用静态空间）
        for x in range(m):
            arr[x] = 0
            
        for j in range(i, n):
            # 累加第j行到辅助数组
            for k in range(m):
                arr[k] += mat[j][k]
            max_sum = max(max_sum, maxSumSubarray())
    
    return max_sum

def maxSumSubarray():
    """一维最大子数组和"""
    max_sum = float('-inf')
    cur = 0
    
    for i in range(m):
        cur += arr[i]
        max_sum = max(max_sum, cur)
        cur = 0 if cur < 0 else cur
    
    return max_sum

if __name__ == '__main__':
    main()

import sys

class FastReader:
    def __init__(self, file=sys.stdin):
        self.file = file
        self.buffer = ""
        self.idx = 0

    def _read(self):
        """一次性读取8KB数据到缓冲区"""
        self.buffer = self.file.read(8192)
        self.idx = 0

    def readByte(self):
        """读取下一个字节"""
        if self.idx >= len(self.buffer):
            self._read()
            if self.buffer == "":
                return -1
        byte = self.buffer[self.idx]
        self.idx += 1
        return ord(byte)

    def readInt(self):
        """快速读取整数"""
        num = 0
        minus = False
        b = self.readByte()
        
        # 跳过非数字字符
        while b != -1 and (b < ord('0') or b > ord('9')) and b != ord('-'):
            b = self.readByte()
            
        if b == ord('-'):
            minus = True
            b = self.readByte()
            
        # 读取数字
        while b != -1 and (ord('0') <= b <= ord('9')):
            num = num * 10 + (b - ord('0'))
            b = self.readByte()
            
        return -num if minus else num

    def readLong(self):
        """读取长整数（Python中与int相同）"""
        return self.readInt()

import sys

class FastWriter:
    def __init__(self, file=sys.stdout):
        self.file = file
        self.buffer = []

    def write(self, s):
        """写入字符串到缓冲区"""
        self.buffer.append(str(s))
        return self  # 支持链式调用

    def writeln(self, s=""):
        """写入一行"""
        self.buffer.append(str(s) + "\n")
        return self

    def println(self, s=""):
        """兼容Java习惯的方法名"""
        return self.writeln(s)

    def flush(self):
        """刷新缓冲区，实际写入文件"""
        if self.buffer:
            self.file.write("".join(self.buffer))
            self.file.flush()
            self.buffer = []

    def close(self):
        """关闭写入器"""
        self.flush()
        if self.file != sys.stdout:
            self.file.close()

import sys
from typing import Optional

class Kattio:
    """
    高效IO类，适用于特殊格式输入
    效率略低于FastReader，但兼容性更好
    """
    def __init__(self, input_stream=sys.stdin, output_stream=sys.stdout):
        self.input = input_stream
        self.output = output_stream
        self.buffer = []
        self.idx = 0

    def _fill_buffer(self):
        """填充缓冲区"""
        line = self.input.readline()
        if line == '':
            return
        self.buffer = line.strip().split()
        self.idx = 0

    def next(self) -> Optional[str]:
        """读取下一个字符串"""
        while self.idx >= len(self.buffer):
            self._fill_buffer()
            if not self.buffer:
                return None
        result = self.buffer[self.idx]
        self.idx += 1
        return result

    def nextInt(self) -> int:
        """读取下一个整数"""
        return int(self.next())

    def nextLong(self) -> int:
        """读取下一个长整数"""
        return int(self.next())

    def nextDouble(self) -> float:
        """读取下一个浮点数"""
        return float(self.next())

    def println(self, s):
        """输出一行"""
        print(s, file=self.output)

    def close(self):
        """关闭IO流"""
        if self.input != sys.stdin:
            self.input.close()
        if self.output != sys.stdout:
            self.output.close()

from collections import deque, defaultdict
import bisect

# 列表（动态数组）
arr = [1, 2, 3]
arr.append(4)              # O(1) 尾部添加
arr.insert(0, 0)           # O(n) 头部插入
arr.pop()                  # O(1) 尾部删除
arr.pop(0)                 # O(n) 头部删除
print(arr[1])              # O(1) 随机访问

# 双端队列（可当栈或队列）
dq = deque()
dq.append(1)               # 队尾入队
dq.appendleft(2)           # 队首入队
dq.pop()                   # 队尾出队
dq.popleft()               # 队首出队

# 集合操作
s1 = {1, 2, 3}
s2 = {2, 3, 4}
print(s1 | s2)             # 并集
print(s1 & s2)             # 交集
print(s1 - s2)             # 差集

# 字典操作
d = defaultdict(int)       # 默认值为0
d["key"] += 1              # 自动初始化并自增

# 排序
arr = [3, 1, 4, 1, 5]
arr.sort()                           # 原地升序排序
arr.sort(reverse=True)               # 原地降序排序
sorted_arr = sorted(arr)             # 返回新的排序数组
custom_sorted = sorted(arr, key=lambda x: -x)  # 自定义排序

# 二分查找
arr = [1, 2, 4, 7, 9]  # 必须有序
idx = bisect.bisect_left(arr, 4)     # 查找插入位置
idx = bisect.bisect_right(arr, 4)    # 查找插入位置（右侧）

# Python原生支持任意精度整数
big_num = 10**100                    # 10的100次方
result = big_num * big_num           # 自动处理大整数运算

# 高精度除法
import decimal
decimal.getcontext().prec = 50       # 设置精度
a = decimal.Decimal('1') / decimal.Decimal('3')

# 1. 避免在循环中重复计算
# 错误写法
for i in range(n):
    for j in range(len(arr)):  # 每次都计算len(arr)
        pass

# 正确写法  
arr_len = len(arr)
for i in range(n):
    for j in range(arr_len):
        pass

# 2. 使用局部变量访问全局数据
# 错误写法
def process():
    for i in range(n):
        result += global_data[i]  # 每次都查找全局变量

# 正确写法
def process():
    local_data = global_data  # 本地化全局变量
    for i in range(n):
        result += local_data[i]

# 3. 字符串拼接优化
# 错误写法
s = ""
for i in range(n):
    s += str(i)  # 每次都创建新字符串

# 正确写法
parts = []
for i in range(n):
    parts.append(str(i))
s = "".join(parts)

# 1. 递归深度限制
import sys
sys.setrecursionlimit(10000)  # 设置递归深度限制

# 2. 浮点数精度问题
import math
def is_equal(a, b, eps=1e-9):
    return abs(a - b) < eps

# 3. 列表初始化陷阱
# 错误：所有行共享同一个列表
matrix = [[0] * m] * n

# 正确：每行都是独立的列表
matrix = [[0] * m for _ in range(n)]

# 4. 字典默认值
from collections import defaultdict
# 使用defaultdict避免KeyError
count = defaultdict(int)
count[key] += 1  # 自动初始化为0

# 条件编译式调试
DEBUG = False

def debug_print(*args):
    if DEBUG:
        print("DEBUG:", *args)

# 输入输出重定向（本地测试）
import sys
if DEBUG:
    sys.stdin = open('input.txt', 'r')
    sys.stdout = open('output.txt', 'w')

# 计时器
import time
start_time = time.time()
# ... 算法代码 ...
print(f"执行时间: {time.time() - start_time:.3f}秒")

class TreeNode:
    def __init__(self, v):
        self.val = v         # 节点的值
        self.left = None     # 左子节点
        self.right = None    # 右子节点

def f(head):
    if head is None:
        return
    # 第1次到达该节点 - 刚进入该节点
    f(head.left)   # 递归处理左子树
    # 第2次到达该节点 - 左子树处理完毕
    f(head.right)  # 递归处理右子树
    # 第3次到达该节点 - 右子树处理完毕

@staticmethod
def preOrder(head):
    """
    先序遍历：在第1次到达节点时处理
    应用场景：复制二叉树、表达式树求值、目录树打印
    测试链接LeetCode 144. 二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/
    """
    if head is None:
        return
    print(head.val, end=" ")  # 先处理当前节点
    BinaryTreeTraversalRecursion.preOrder(head.left)   # 再遍历左子树
    BinaryTreeTraversalRecursion.preOrder(head.right)  # 最后遍历右子树

@staticmethod
def inOrder(head):
    """
    中序遍历：在第2次到达节点时处理
    应用场景：二叉搜索树排序（得到有序序列）、表达式树转中缀表达式
    测试链接LeetCode 94. 二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/
    """
    if head is None:
        return
    BinaryTreeTraversalRecursion.inOrder(head.left)   # 先遍历左子树
    print(head.val, end=" ")  # 再处理当前节点
    BinaryTreeTraversalRecursion.inOrder(head.right)  # 最后遍历右子树

@staticmethod
def posOrder(head):
    """
    后序遍历：在第3次到达节点时处理
    应用场景：计算目录大小、删除二叉树、表达式树计算
    测试链接LeetCode 145. 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/
    """
    if head is None:
        return
    BinaryTreeTraversalRecursion.posOrder(head.left)   # 先遍历左子树
    BinaryTreeTraversalRecursion.posOrder(head.right)  # 再遍历右子树
    print(head.val, end=" ")  # 最后处理当前节点

# 复制二叉树示例
def copyTree(root):
    if root is None:
        return None
    # 先创建新节点（先序特点）
    newNode = TreeNode(root.val)
    newNode.left = copyTree(root.left)    # 递归复制左子树
    newNode.right = copyTree(root.right)  # 递归复制右子树
    return newNode

# 验证二叉搜索树示例
def isValidBST(root):
    def inorder(node, values):
        if node is None:
            return
        inorder(node.left, values)
        values.append(node.val)  # 中序收集值
        inorder(node.right, values)
    
    values = []
    inorder(root, values)
    # 检查是否严格递增
    return all(values[i] < values[i+1] for i in range(len(values)-1))

# 计算二叉树高度示例
def maxDepth(root):
    if root is None:
        return 0
    # 先计算左右子树高度（后序特点）
    leftHeight = maxDepth(root.left)
    rightHeight = maxDepth(root.right)
    # 再计算当前树高度
    return max(leftHeight, rightHeight) + 1

@staticmethod
def preOrder(head):
    """
    先序遍历非递归实现
    核心思路：使用一个栈。每次先访问节点本身，再依次压入右、左子节点（注意顺序，先右后左），这样弹栈时总是优先处理左子树，实现“中-左-右”顺序
    时间复杂度：O(n)，每个节点进栈出栈各一次
    空间复杂度：O(h)，h为树的高度
    测试链接LeetCode 144. 二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/
    """
    if head is not None:
        stack = []
        stack.append(head)
        while stack:
            head = stack.pop()        # 弹出栈顶节点
            print(head.val, end=" ")  # 立即打印（先序特点）
            # 关键：先压右子节点，再压左子节点
            # 这样弹栈时就是先处理左子树，再处理右子树
            if head.right is not None:
                stack.append(head.right)
            if head.left is not None:
                stack.append(head.left)
        print()

@staticmethod
def inOrder(head):
    """
    中序遍历非递归实现
    核心思路：用一个栈模拟递归。每次不断沿左子树走到底，并将沿途所有节点入栈；遇到空节点就弹出栈顶节点，访问它，然后转向其右子树。如此反复，完整地实现“左-中-右”顺序。
    测试链接LeetCode 94. 二叉树的中序遍历：https://leetcode.cn/problems/binary-tree-inorder-traversal/
    """
    if head is not None:
        stack = []
        while stack or head is not None:
            if head is not None:
                # 当前节点不为空，压栈并继续向左
                stack.append(head)
                head = head.left
            else:
                # 当前节点为空，说明左子树遍历完毕
                head = stack.pop()        # 弹出栈顶节点
                print(head.val, end=" ")  # 打印节点值（中序特点）
                head = head.right         # 转向右子树
        print()

@staticmethod
def posOrderTwoStacks(head):
    """
    后序遍历非递归实现 - 双栈法
    核心思路：第一个栈实现"中-右-左"遍历，结果压入第二个栈
    最后弹出第二个栈得到"左-右-中"的后序遍历结果
    即：用一个栈模拟递归。每次不断沿左子树走到底，并将沿途所有节点入栈；遇到空节点就弹出栈顶节点，访问它，然后转向其右子树。如此反复，完整地实现“左-中-右”顺序。
    测试链接LeetCode 145. 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/
    """
    if head is not None:
        stack = []      # 主栈：用于遍历
        collect = []    # 收集栈：用于收集结果
        stack.append(head)
        
        while stack:
            head = stack.pop()
            collect.append(head)      # 收集节点到第二个栈
            # 注意：这里先压左子节点，再压右子节点
            # 这样遍历顺序就是"中-右-左"
            if head.left is not None:
                stack.append(head.left)
            if head.right is not None:
                stack.append(head.right)
        
        # 反向弹出收集栈，得到"左-右-中"顺序
        while collect:
            print(collect.pop().val, end=" ")
        print()

@staticmethod
def posOrderOneStack(h):
    """
    后序遍历非递归实现 - 单栈法
    核心思路：通过记录最近访问的节点，确保每个节点在其左右子树都被访问后才访问自己，从而严格实现“左-右-中”的后序遍历。
    每个节点最多入栈两次，效率更高
    测试链接LeetCode 145. 二叉树的后序遍历：https://leetcode.cn/problems/binary-tree-postorder-traversal/
    """
    if h is not None:
        stack = []
        stack.append(h)
        # h的含义：最近一次处理（打印）的节点
        
        while stack:
            cur = stack[-1]  # 查看栈顶元素但不弹出
            
            # 情况1：有左子树且左子树未被处理过
            if cur.left is not None and h != cur.left and h != cur.right:
                stack.append(cur.left)
            # 情况2：有右子树且右子树未被处理过
            elif cur.right is not None and h != cur.right:
                stack.append(cur.right)
            # 情况3：左右子树都没有或都已处理完毕
            else:
                print(cur.val, end=" ")
                h = stack.pop()  # 更新h为刚刚处理的节点
        print()

from collections import deque

class Queue1:
    """
    基于Python内置deque实现的队列
    内部使用双向链表，常数操作较慢但使用简单
    """
    def __init__(self):
        self.queue = deque()  # 内部存储使用deque（双端队列）

    def is_empty(self):
        """判断队列是否为空"""
        return not self.queue

    def offer(self, num):
        """向队列中加入元素，加到队尾"""
        self.queue.append(num)

    def poll(self):
        """从队列头部弹出元素"""
        return self.queue.popleft()

    def peek(self):
        """返回队列头的元素但不弹出"""
        return self.queue[0]

    def size(self):
        """返回队列中元素个数"""
        return len(self.queue)

class Queue2:
    """
    基于固定数组实现的队列
    适用于已知加入操作总次数上限的场景
    常数时间性能更好，是实际刷题中最常用的方式
    """
    def __init__(self, n):
        """
        初始化队列
        参数: n - 加入操作的总次数上限
        """
        self.queue = [0] * n  # 固定大小数组
        self.l = 0  # 队首指针
        self.r = 0  # 队尾指针

    def is_empty(self):
        """判断队列是否为空"""
        return self.l == self.r

    def offer(self, num):
        """入队操作"""
        self.queue[self.r] = num  # 在队尾位置插入元素
        self.r += 1  # 队尾指针后移

    def poll(self):
        """出队操作"""
        num = self.queue[self.l]  # 取队首元素
        self.l += 1  # 队首指针后移
        return num

    def head(self):
        """返回队首元素"""
        return self.queue[self.l]

    def tail(self):
        """返回队尾元素"""
        return self.queue[self.r - 1]

    def size(self):
        """队列当前元素个数，区间[l, r)"""
        return self.r - self.l

class Stack1:
    """
    基于Python内置列表实现的栈
    使用动态数组，常数时间不是最优但使用简单
    """
    def __init__(self):
        self.stack = []  # 用列表模拟栈

    def is_empty(self):
        """判断栈是否为空"""
        return len(self.stack) == 0

    def push(self, num):
        """压栈操作"""
        self.stack.append(num)

    def pop(self):
        """弹栈操作"""
        return self.stack.pop()

    def peek(self):
        """返回栈顶元素但不弹出"""
        return self.stack[-1]

    def size(self):
        """返回栈的大小"""
        return len(self.stack)

class Stack2:
    """
    基于固定数组实现的栈
    适用于已知同时在栈里元素个数上限的场景
    常数时间性能更好，空间可以复用
    """
    def __init__(self, n):
        """
        初始化栈
        参数: n - 同时在栈里的元素个数上限
        """
        self.stack = [0] * n  # 固定大小数组
        self.size_ = 0  # 当前栈元素个数

    def is_empty(self):
        """判断栈是否为空"""
        return self.size_ == 0

    def push(self, num):
        """压栈操作"""
        self.stack[self.size_] = num  # 在当前size位置插入
        self.size_ += 1  # 元素个数+1

    def pop(self):
        """弹栈操作"""
        self.size_ -= 1  # 元素个数-1，先减后取值
        return self.stack[self.size_]  # 返回弹出的元素

    def peek(self):
        """返回栈顶元素但不弹出"""
        return self.stack[self.size_ - 1]

    def size(self):
        """返回栈大小"""
        return self.size_

class MyCircularQueue:
    """
    循环队列实现
    测试链接: https://leetcode.cn/problems/design-circular-queue/
    """
    def __init__(self, k):
        """
        初始化循环队列
        参数: k - 队列容量上限
        """
        self.queue = [0] * k  # 固定大小数组
        self.l = 0  # 队首指针
        self.r = 0  # 队尾指针
        self.size = 0  # 当前元素个数
        self.limit = k  # 容量上限

    def enQueue(self, value):
        """
        入队操作
        返回: 成功返回True，队列满返回False
        """
        if self.isFull():
            return False  # 队列已满
        else:
            self.queue[self.r] = value  # 队尾插入元素
            # 队尾指针循环移动
            self.r = 0 if self.r == self.limit - 1 else self.r + 1
            self.size += 1  # 元素个数+1
            return True

    def deQueue(self):
        """
        出队操作
        返回: 成功返回True，队列空返回False
        """
        if self.isEmpty():
            return False  # 队列为空
        else:
            # 队首指针循环移动
            self.l = 0 if self.l == self.limit - 1 else self.l + 1
            self.size -= 1  # 元素个数-1
            return True

    def Front(self):
        """返回队首元素，队列为空返回-1"""
        if self.isEmpty():
            return -1
        else:
            return self.queue[self.l]

    def Rear(self):
        """返回队尾元素，队列为空返回-1"""
        if self.isEmpty():
            return -1
        else:
            # 计算队尾指针的实际位置
            last = self.limit - 1 if self.r == 0 else self.r - 1
            return self.queue[last]

    def isEmpty(self):
        """判断队列是否为空"""
        return self.size == 0

    def isFull(self):
        """判断队列是否已满"""
        return self.size == self.limit

class MyQueue:
    """
    用栈实现队列
    测试链接: https://leetcode.cn/problems/implement-queue-using-stacks/
    时间复杂度: 均摊O(1)
    """
    def __init__(self):
        self.in_stack = []     # 输入栈，负责push
        self.out_stack = []    # 输出栈，负责pop/peek

    def inToOut(self):
        """
        倒数据操作：从输入栈将数据倒入输出栈
        核心规则：
        1) 输出栈空了，才能倒数据
        2) 如果倒数据，输入栈必须倒完
        """
        if not self.out_stack:                     # 只有输出栈为空才能倒
            while self.in_stack:                   # 输入栈必须倒完
                self.out_stack.append(self.in_stack.pop())

    def push(self, x: int):
        """入队操作：新元素加入输入栈"""
        self.in_stack.append(x)                    # 新元素压入输入栈
        self.inToOut()                             # 检查是否需要倒数据

    def pop(self) -> int:
        """出队操作：从输出栈弹出元素"""
        self.inToOut()                             # 确保输出栈有数据
        return self.out_stack.pop()                # 弹出队首元素

    def peek(self) -> int:
        """查看队首元素：不移除，只查看"""
        self.inToOut()                             # 确保输出栈有数据
        return self.out_stack[-1]                  # 返回栈顶即队首

    def empty(self) -> bool:
        """判断队列是否为空"""
        return not self.in_stack and not self.out_stack  # 两个栈都空才是空队列