#include<bits/stdc++.h> // 万能头文件，几乎包含所有标准库头文件（竞赛常用）
#include<iostream> // 标准输入输出，提供cin、cout等
#include<string> // 字符串处理，提供string类及相关操作
#include<vector> // 动态数组容器，可自动扩容的数组
#include<algorithm> // 通用算法库，提供sort、max、min等函数
#include<cmath> // 数学函数库，提供floor、ceil、sqrt、pow等
#include<fstream> // 文件流操作，用于读写文件
#include<cstdio> // C风格输入输出，提供printf、scanf等
#include<cstdlib> // 通用工具库，提供rand、srand、exit等
#include<ctime> // 时间相关函数，用于获取系统时间、生成随机数种子
#include<cstring> // C风格字符串处理，提供strlen、strcpy等
#include<limits> // 数据类型极值，获取int、double等的最大/最小值
#include<numeric> // 数值算法，提供accumulate（求和）等函数
#include<stack> // 栈容器，后进先出（LIFO）结构
#include<queue> // 队列容器，先进先出（FIFO）结构
#include<map> // 键值对映射容器，有序关联存储
#include<set> // 集合容器，存储不重复的有序元素
#include<unordered_map> // 哈希无序键值对，查询插入平均 O (1)
#include<unordered_set> // 哈希无序集合，去重查找速度更快
#include<deque> // 双端队列，首尾均可快速插入删除，滑动窗口常用
#include<list> // 双向链表，任意位置插入删除高效，不支持随机访问
#include<forward_list> // 单向链表，内存占用更小，仅能从前遍历
#include<array> // 固定大小数组容器，封装普通数组，支持 STL 接口
#include<tuple> // 多元组，存储多个不同类型数据
#include<pair> // 二元组，存储一组键值数据，map 默认存储单元
#include<utility> // 通用工具函数，swap 交换、move 移动语义
#include<bitset> // 定长二进制位存储，快速位运算、状态压缩
#include<complex> // 复数运算，支持复数加减乘除、极坐标转换
#include<valarray> // 数值数组，批量数学运算，适合科学计算
#include<random> // C11 新标准随机数库，高质量随机生成器
#include<ratio> // 编译期有理数计算，用于 chrono 时间单位换算
#include<chrono> // 高精度时间库，计时、时间间隔计算
#include<typeinfo> // 运行时类型识别，typeid 获取变量类型
#include<type_traits> // 编译期类型判断，模板元编程工具
#include<memory> // 智能指针，unique_ptr、shared_ptr 自动管理内存
#include<scoped_allocator> // 分层内存分配器，容器嵌套内存管理
#include<allocator> // STL 容器默认内存分配器
#include<functional> // 可调用对象封装，function、bind、lambda 包装
#include<iterator> // 迭代器工具，迭代器适配器、遍历辅助函数
#include<locale> // 本地化语言、字符编码处理
#include<codecvt> // 字符编码转换，utf8、utf16、gbk 互转
#include<sstream> // 字符串流，数字与 string 互相转换
#include<iomanip> // 输出格式控制，setw、setprecision、fixed 保留小数
#include<ios> // IO 流基础属性设置，同步开关、进制设置
#include<iosfwd> // IO 流前置声明，减少头文件依赖
#include<streambuf> // 底层 IO 缓冲区封装，自定义输入输出缓冲区
#include<cstdint> // 固定宽度整数类型，int64_t、uint32_t 等
#include<cstddef> // 标准基础类型，size_t、nullptr_t
#include<cstdarg> // 可变参数函数支持，不定数量参数读取
#include<cctype> // 字符判断函数，isdigit、isalpha、isspace
#include<cwctype> // 宽字符判断函数，宽字符数字、字母识别
#include<cwchar> // 宽字符串操作，wchar_t 相关处理函数
#include<climits> // C 语言整数极值，INT_MAX、LLONG_MIN
#include<cfloat> // 浮点类型极值，FLT_MAX、DBL_EPSILON 精度误差
#include<cassert> // 断言调试，运行时校验条件，出错终止程序
#include<cerrno> // 系统错误码，读取 IO、文件操作失败原因
#include<clocale> // C 语言本地化设置，全局字符区域配置
#include<ciso646> // 兼容老式逻辑运算符，and/or/not 等价 &&||!
#include<atomic> // 原子变量，多线程无锁并发安全读写
#include<thread> // C 标准线程库，创建、管理多线程
#include<mutex> // 互斥锁，多线程资源竞争保护
#include<shared_mutex> // 读写锁，多读单写提升并发效率
#include<condition_variable> // 线程条件变量，线程等待与唤醒
#include<future> // 异步任务，获取线程返回结果
#include<stop_token> // 线程终止标记，安全中断后台线程
#include<semaphore> // 信号量，控制并发线程数量
#include<latch> // 线程同步栅栏，等待全部线程到达同步点
#include<barrier> // 循环同步屏障，多轮线程同步
#include<filesystem> // 文件系统操作，遍历文件夹、创建删除文件路径
#include<regex> // 正则表达式，字符串匹配、提取、替换
#include<variant> // 类型联合体，存储多种可选类型其一
#include<any> // 任意类型容器，可存放任意 C++ 对象
#include<optional> // 可选值容器，标记数据是否存在有效值
#include<compare> // 三路比较运算符，简化自定义大小比较
#include<numbers> // 标准数学常量，π、e、sqrt2 等高精度常数
#include<format> // C20 新式格式化输出，替代 sprintf
#include<source_location> // 获取代码行号、文件名、函数名，调试定位
#include<flat_map> // 有序扁平映射，连续内存，比 map 更快
#include<flat_set> // 有序扁平集合，连续数组存储，查询效率高
#include // 数组视图，不拷贝只读访问连续内存
#include<ranges> // C20 范围库，简化容器遍历、过滤、变换
#include<mdspan> // 多维数组视图，多维矩阵轻量化处理
#include<syncstream> // 线程安全输出流，多线程 cout 不乱序
#include<cuchar> // Unicode 字符类型，char8_t、char16_t、char32_t
#include<strstream> // 老式字符流，现已基本被 sstream 替代
#include<ext/pb_ds/assoc_container.hpp> // GNU 扩展平衡树基础头文件
#include<ext/pb_ds/tree_policy.hpp> // 有序树 policy_tree，求第 k 大、前驱后继
#include<ext/pb_ds/hash_policy.hpp> // GNU 高性能哈希表，比 unordered_map 更快
#include<ext/pb_ds/priority_queue.hpp> // 可配对堆优先队列，替代 std::priority_queue
#include<ext/rope> // 可持久化字符串，区间修改、区间查询字符串
#include<cstdbool> // C 标准布尔类型 bool、true、false
#include<cstdalign> // 内存对齐相关宏与函数
#include<cfenv> // 浮点运算环境，控制浮点异常、舍入模式
#include<cinttypes> // 固定宽度整数格式化宏，配合 printf 输出 int64_t
#include<stacktrace> // C23 堆栈打印，崩溃时输出调用栈
#include<print> // C23 简化控制台输出，无需 cout 格式化
#include<tgmath.h> // 泛型数学宏，自动适配 float/double/long double
#include<cxxabi.h> // GCC 底层 ABI 工具，函数名解析 demangle
#include<signal.h> // Linux 系统信号，捕获 ctrl+c、程序崩溃信号
#include<unistd.h> // Linux 系统调用，sleep、read、write、getpid
#include<sys/time.h> // Linux 高精度时间，gettimeofday 微秒计时
#include<pthread.h> // Linux 原生 POSIX 线程，底层多线程 API
#include<sys/stat.h> // 获取文件属性，大小、创建时间、权限
#include<sys/mman.h> // 内存映射文件，大文件高速读写
#include<fcntl.h> // 文件控制，打开文件、设置非阻塞 IO
#include<arpa/inet.h> // 网络字节序转换，IP 地址转换
#include<sys/socket.h> // 套接字网络编程，创建 TCP/UDP 通信
#include<errno.h> // Linux 系统调用错误码查询
#include<sys/wait.h> // 进程等待，回收子进程资源
#include<dirent.h> // 遍历系统文件夹，读取目录下文件列表
#include<sys/types.h> // Linux 系统基础类型，pid_t、uid_t 等
#include<sys/resource.h> // 进程资源限制，内存、CPU 占用上限设置
#include<sys/utsname.h> // 获取操作系统内核、主机硬件信息
#include<sys/select.h> // IO 多路复用，同时监听多个文件描述符
#include<sys/ioctl.h> // 设备控制，终端窗口大小、硬件参数读取
#include<termios.h> // 终端属性配置，关闭回车回显、原始输入
#include<pwd.h> // 读取系统用户信息，用户名、家目录
#include<grp.h> // 读取系统用户分组信息
#include<utime.h> // 修改文件访问、修改时间戳
#include<glob.h> // 通配符匹配文件路径，*.txt 批量匹配
#include<syslog.h> // 系统日志输出，写入系统日志服务
#include<wchar.h> // 宽字符标准库，宽字符串 IO 操作
#include<wctype.h> // 宽字符分类判断函数
#include<iconv.h> // 系统字符集转码，gb2312、utf8 互转
#include<sys/uio.h> // 分散聚合 IO，一次读写多块内存缓冲区
#include<aio.h> // Linux 异步文件 IO，后台读写不阻塞程序
#include<semaphore.h> // POSIX 信号量，进程 / 线程间同步
#include<mqueue.h> // 进程消息队列，跨进程数据通信
#include<sys/msg.h> // System V 消息队列，传统进程通信
#include<sys/shm.h> // System V 共享内存，多进程高速共享数据
#include<sys/sem.h> // System V 信号量，进程互斥同步
#include<sys/poll.h> // IO 多路复用 poll，替代 select 处理大量文件描述符
#include<sys/epoll.h> // Linux 高性能 IO 多路复用，高并发网络服务器专用
#include<sys/eventfd.h> // 事件通知文件描述符，线程间简单通知
#include<sys/timerfd.h> // 定时器文件描述符，高精度定时触发事件
#include<sys/inotify.h> // 文件监控，监听文件夹新增、删除、修改文件
#include<sys/random.h> // 系统真随机数，获取加密安全随机数据
#include<sys/sysinfo.h> // 获取系统运行信息，内存、负载、开机时长
#include<sys/statvfs.h> // 查询磁盘分区剩余空间、总容量
#include<sys/poll.h> // IO 轮询多路复用接口
#include<sys/signalfd.h> // 将系统信号转为文件描述符，统一事件监听
#include<sys/perf_event.h> // Linux 性能监控，CPU 缓存、指令计数采集
#include<sys/seccomp.h> // 系统调用过滤，限制程序可调用系统函数
#include<sys/ptrace.h> // 进程调试，读取修改其他进程内存、寄存器