盼望着，盼望着，最后一题AC了，集训结束的脚步近了。

一切都像刚解脱的样子，欣欣然张开了眼。代码提交上去了，评测队列清空了，老师的血压降下来了。

神兽们悄悄地从机房里钻出来，嫩嫩的，绿绿的。电脑前，过道间，瞧去，一大片一大片满是的。坐着的，趴着的，调两个bug，交几发代码，对几组数据，争几句复杂度。键盘脆生生的，他们的争论声闹哄哄的。

DFS,BFS，贪心二分，你不让我，我不让你，都摆好了封存架势。红的像RE，紫的像MLE，绿的像AC。OJ上带着"Accepted"的甜味儿；闭了眼，耳边仿佛已经没有了"老师我RE了"、"老师我TLE了"的呼喊。千百份代码在评测机里嗡嗡地跑着，大小的提交记录在屏幕上一行行滚过。题解遍地是：杂样儿，有贪心的，有DP的，有图论的，散在文件夹里，像星星，像萤火虫，还眨呀眨的。

"吹面不寒空调风"，不错的，像机房十六度的冷气抚摸着你。风里带来些集训结束的气息，混着脚臭味儿，还有花露水的香，都在微微湿润的空气里酝酿。我将牌子摘下来，高兴起来了，把手机铃声调到最大，播一首摇滚，跟机箱的风扇声应和着。投影仪关机的"嘀"一声，这时候也成天嘹亮地响。

调代码是最寻常的，一调就是三四个小时。可别恼。看，像死循环，像数组越界，像指针乱飞，密密地纠缠着，屏幕上全笼着一层迷雾。数据却弱得发亮，样例也水得逼你的眼。深夜时候，开台灯了，一点点黄晕的光，烘托出一片安静而执拗的夜。在走廊，楼梯口，机房门外，有默默收拾着外设的老师，还有刚讲完最后一节强化课的主讲，合上笔记本，拔掉U盘。他们的身影稀稀疏疏的，在凌晨里静默着。

明天起，OJ的提交数渐渐少了，老师的微信群也安静了。五湖四海，各家各校，神兽们也赶趟儿似的，一个个都拖着箱子出来了。收拾收拾键盘，清空清空缓存，各回各的家去。"一年之计在于夏"，集训刚收尾，有的是奖牌，有的是希望。

暑假像刚AC的代码，从头到脚都是绿的，它通过着。

暑假像评测机上的绿条，亮闪闪的，跑着，跳着。

暑假像卸了任的老师，有铁一般的睡眠，和说不出的、自由的、安静的、属于自己的——日子。

夫二维数组者，其形若棋局，其理类阡陌。横为行，纵为列，数以位次而列，理以经纬而明。初习之，余常困于位次之辨，遍历之法，每有越界之虞，屡试屡踬，心甚苦之。及练之既久，方悟其道： 位次者，数据之定位也。或从零始，或从一始，随题而异，不可不察。若位次错乱，则数据淆乱，虽有良法，亦难奏效。余尝因一念之差，致全题皆错，悔之晚矣。 遍历者，解题之根基也。有行优先、列优先之异，亦有对角、螺旋之变。行优先者，先逐行而进，每行之内再逐列而巡；列优先者，则反之。至于螺旋遍历，则需明其以为序之理，层层深入，方可无遗。 边界者，安危之关隘也。数组之首尾，乃程序之险地。若不设限，则必生越界之误，致程序崩毁。余每遇此题，必先画其疆界，标其起止，而后方敢下笔，慎之慎之。 题型者，万变不离其宗也。或求转置，或寻极值，或做运算，其理一也。转置者，易其行列之位也；极值者，周行全域而较其大小也；运算者，恪守对应之则也。明其理，则万变可应。 嗟乎！编程之道，非止于技，亦进乎道。二维数组之学，初看似繁，实则有序。余今总结于此，非敢示人，亦以自警。愿与同道共勉，避坑前行，臻于熟练之境。

P1 【例2.1】Hello World满分代码

#include <bits/stdc++.h>
#define suing using
#define naemsacpe namespace
#define sdt std
#define itn int
#define mian main
#define boat_du return 
#define con cin
#define feropen freopen
#define sdtin stdin 
#define sdtout stdout
#define cotu cout
#define QY2002 "hello"
#define sharpland "world"
suing naemsacpe sdt;

itn mian() 
{
//	feropen(".in","r",sdtin);
//	feropen(".out","w",sdtout);
	cotu<<QY2002<<" "<<sharpland;
	boat_du 0;
}

饺子皮

#include <bits\stdc++,h>
using namspace std;

1nt ma1n（） 
{
	
	
	
	return o;
}

快读快写

ios::sync_with_stdio(false);
cin.tie(NULL);

网站入口

172.20.6.60

快速幂

const int mod = 1e9 + 7;
long long fast_pow(long long a,long long b)
{
	if(b == 0) return 1;
	long long res = fast_pow(a,b/2);
	if(b%2==0) return res*res%mod;
	else return res*res%mod*a%mod;
}

辗转相除法

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

优先队列

priority_queueq;声明一个存储类型为int的堆
priority_queue< int, vector< int >, greater< int > > q:小根堆
priority_queue< int, vector< int >, less< int > > q:大根堆

q.push(1);放进去元素

q.top();有返回值的函数，返回堆里的最大值，不删掉

q.pop() 没有返回值，删掉堆里的最大值。

q.size()返回值为当前堆的大小（堆内元素数量）

q.empty()当堆内元素数量为0时，返回值为1。如果元素数量大于0，返回值为0

要注意，只有堆里有东西的时候才能top和pop。没东西的时候执行top和pop是未定义行为，一般会导致re

怎么看有没有东西：q.size()或者q.empty()

（1）基础内置函数

一、数值计算类 （ 头文件）

// 基础数学运算
abs(int x);       // int类型绝对值
labs(long x);     // long类型绝对值
llabs(long long x); // long long类型绝对值
fabs(double x);   // double类型浮点绝对值
fabsf(float x);   // float类型浮点绝对值
fabsl(long double x); // long double类型浮点绝对值
 
// 取整相关
ceil(double x);   // 向上取整（如ceil(2.1)=3, ceil(-2.1)=-2）
ceilf(float x);   // float版向上取整
ceill(long double x); // long double版向上取整
floor(double x);  // 向下取整（如floor(2.9)=2, floor(-2.9)=-3）
floorf(float x);  // float版向下取整
floorl(long double x); // long double版向下取整
round(double x);  // 四舍五入（如round(2.5)=3, round(-2.5)=-3）
roundf(float x);  // float版四舍五入
roundl(long double x); // long double版四舍五入
trunc(double x);  // 截断小数部分（如trunc(2.9)=2, trunc(-2.9)=-2）
 
// 平方根/幂运算
sqrt(double x);   // double类型平方根
sqrtf(float x);   // float类型平方根
sqrtl(long double x); // long double类型平方根
pow(double a, double b); // 计算a的b次方（a^b）
powf(float a, float b);  // float版幂运算
powl(long double a, long double b); // long double版幂运算
 
// 指数/对数
exp(double x);    // 自然指数e^x
log(double x);    // 自然对数ln(x)
log10(double x);  // 以10为底的对数log10(x)
 
// 三角函数（参数为弧度）
sin(double x);    // 正弦
cos(double x);    // 余弦
tan(double x);    // 正切
asin(double x);   // 反正弦
acos(double x);   // 反余弦
atan(double x);   // 反正切
 
// 最值/余数
fmod(double a, double b); // 浮点余数（a除以b的余数）
fmax(double a, double b); // 取两个数的最大值
fmin(double a, double b); // 取两个数的最小值

二、字符串 操作类（ 头文件）

// 基础属性
s.length();       // 获取字符串长度（同size()）
s.size();         // 获取字符串长度
s.empty();        // 判断字符串是否为空（空返回true）
s.clear();        // 清空字符串内容
 
// 子串/查找
s.substr(pos, len); // 截取子串：从pos位置开始，截取len个字符（len省略则到末尾）
s.find(str);      // 查找子串str首次出现的位置，找不到返回string::npos
s.rfind(str);     // 从后往前查找子串str首次出现的位置
s.find_first_of(str); // 查找str中任意字符首次出现的位置
s.find_last_of(str);  // 查找str中任意字符最后出现的位置
s.find_first_not_of(str); // 查找首个不在str中的字符位置
 
// 拼接/替换/插入/删除
s.append(str);    // 在字符串末尾拼接str
s.replace(pos, len, str); // 从pos位置开始，替换len个字符为str
s.insert(pos, str); // 在pos位置插入str
s.erase(pos, len);  // 从pos位置开始，删除len个字符（len省略则删到末尾）
 
// 比较
s.compare(str);   // 比较字符串与str：相等返回0，s大返回正数，小返回负数
s == str;         // 直接比较字符串是否相等（运算符重载，更常用）
s > str;          // 比较字符串大小（按ASCII码）
 
// 字符访问
s.at(pos);        // 访问pos位置的字符（带越界检查）
s[pos];           // 访问pos位置的字符（无越界检查，更常用）

三、类型转换类

// 字符串转数值（<string> 头文件）
stoi(str);        // 字符串转int型整数
stol(str);        // 字符串转long型整数
stoll(str);       // 字符串转long long型整数
stof(str);        // 字符串转float型浮点数
stod(str);        // 字符串转double型浮点数
stold(str);       // 字符串转long double型浮点数
 
// 数值转字符串（<string> 头文件）
to_string(int x); // int转字符串
to_string(long x); // long转字符串
to_string(long long x); // long long转字符串
to_string(float x); // float转字符串
to_string(double x); // double转字符串
 
// 字符判断/转换（<cctype> 头文件）
isalpha(char c);  // 判断字符是否为字母（a-z/A-Z）
isdigit(char c);  // 判断字符是否为数字（0-9）
isalnum(char c);  // 判断字符是否为字母或数字
islower(char c);  // 判断字符是否为小写字母
isupper(char c);  // 判断字符是否为大写字母
isspace(char c);  // 判断字符是否为空白符（空格、换行、制表符等）
toupper(char c);  // 字符转大写（非字母则不变）
tolower(char c);  // 字符转小写（非字母则不变）
```echarts

四、算法类（ 头文件 ）

// 排序/反转
sort(arr.begin(), arr.end()); // 升序排序（容器/数组）
sort(arr.begin(), arr.end(), greater<int>()); // 降序排序
reverse(arr.begin(), arr.end()); // 反转容器/数组内容
 
// 查找/最值
find(arr.begin(), arr.end(), val); // 查找值val的位置，找不到返回end()
max_element(arr.begin(), arr.end()); // 查找最大值的迭代器
min_element(arr.begin(), arr.end()); // 查找最小值的迭代器
binary_search(arr.begin(), arr.end(), val); // 二分查找（需先排序）
 
// 去重/交换
unique(arr.begin(), arr.end()); // 去除相邻重复元素（需先排序）
swap(a, b); // 交换两个变量的值
 
// 填充/替换
fill(arr.begin(), arr.end(), val); // 将容器/数组全部填充为val
replace(arr.begin(), arr.end(), old_val, new_val); // 替换所有old_val为new_val
 
// 计数/合并
count(arr.begin(), arr.end(), val); // 统计val出现的次数
merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), res.begin()); // 合并两个有序容器

五、容器基础操作（以 vector 为例， 头文件）

v.push_back(val); // 尾部添加元素
v.pop_back();     // 尾部删除元素
v.begin();        // 返回首元素迭代器
v.end();          // 返回尾后迭代器（最后一个元素的下一个位置）
v.size();         // 获取容器元素个数
v.empty();        // 判断容器是否为空
v.clear();        // 清空容器
v.resize(n);      // 调整容器大小为n
v.at(pos);        // 访问pos位置元素（带越界检查）
v[pos];           // 访问pos位置元素（无越界检查）
v.insert(iter, val); // 在迭代器iter位置插入元素val
v.erase(iter);    // 删除迭代器iter位置的元素

六、输入输出类（ 头文件）

cin >> var;       // 从标准输入读取数据到变量var
cout << var;      // 将变量var输出到标准输出
cin.get();        // 读取单个字符（包括换行符）
cin.getline(str, len); // 读取一行字符串（最多len个字符）
getline(cin, s);  // 读取一行字符串到string对象s（更常用）
cout << endl;     // 输出换行并刷新缓冲区
cout << flush;    // 刷新输出缓冲区

（2）常用STL（stack，queue，map，list，vector）内置函数：

一、vector（动态数组， 头文件）

// 基础属性
v.size(); // 获取元素个数
v.empty(); // 判断是否为空（空返回true）
v.capacity(); // 获取当前已分配内存可容纳的元素数
v.max_size(); // 获取容器最大可容纳的元素数（系统限制）
v.reserve(n); // 预分配至少n个元素的内存（仅扩容，不改变size）
v.resize(n); // 调整容器大小为n，不足补默认值，超出则删除末尾元素
v.clear(); // 清空所有元素（size=0，capacity不变）
 
// 元素访问
v[pos]; // 访问第pos个元素（无越界检查，效率高）
v.at(pos); // 访问第pos个元素（有越界检查，抛out_of_range异常）
v.front(); // 获取第一个元素
v.back(); // 获取最后一个元素
v.data(); // 返回指向底层数组的指针（C++11）
 
// 增删元素
v.push_back(val); // 尾部添加元素
v.pop_back(); // 尾部删除元素（无返回值）
v.insert(iter, val); // 在迭代器iter位置插入val
v.insert(iter, n, val); // 在iter位置插入n个val
v.insert(iter, begin, end); // 在iter位置插入[begin,end)区间元素
v.erase(iter); // 删除iter位置的元素
v.erase(begin, end); // 删除[begin,end)区间元素
v.emplace_back(args); // 尾部原地构造元素（比push_back高效）
v.emplace(iter, args); // 在iter位置原地构造元素
v.swap(v2); // 交换两个vector的内容（高效，仅交换内部指针）
v.assign(n, val); // 赋值n个val（覆盖原有内容）
v.assign(begin, end); // 赋值[begin,end)区间元素（覆盖原有内容）

二、list（双向链表， 头文件）

// 基础属性
l.size(); // 获取元素个数
l.empty(); // 判断是否为空
l.max_size(); // 获取最大可容纳元素数
l.clear(); // 清空所有元素
 
// 元素访问
l.front(); // 获取第一个元素
l.back(); // 获取最后一个元素
// 注意：list无[]/at访问，只能通过迭代器遍历
 
// 增删元素
l.push_front(val); // 头部添加元素
l.pop_front(); // 头部删除元素（无返回值）
l.push_back(val); // 尾部添加元素
l.pop_back(); // 尾部删除元素（无返回值）
l.insert(iter, val); // 在iter位置插入val
l.insert(iter, n, val); // 在iter位置插入n个val
l.insert(iter, begin, end); // 在iter位置插入[begin,end)区间元素
l.erase(iter); // 删除iter位置的元素
l.erase(begin, end); // 删除[begin,end)区间元素
l.emplace_front(args); // 头部原地构造元素
l.emplace_back(args); // 尾部原地构造元素
l.emplace(iter, args); // 在iter位置原地构造元素
l.remove(val); // 删除所有值为val的元素
l.remove_if(pred); // 删除满足pred条件的元素
l.unique(); // 删除相邻重复元素（需先排序）
l.unique(pred); // 按pred条件删除相邻重复元素
 
// 排序/反转/合并
l.sort(); // 升序排序（list专属，比algorithm的sort高效）
l.sort(comp); // 按自定义规则comp排序
l.reverse(); // 反转链表
l.merge(l2); // 合并两个已排序的list（l2被清空）
l.merge(l2, comp); // 按自定义规则合并已排序的list
l.splice(iter, l2); // 将l2所有元素插入到iter位置（l2被清空）
l.splice(iter, l2, iter2); // 将l2的iter2位置元素插入到iter位置

三、map（有序键值对，红黑树， 头文件）

// 基础属性
m.size(); // 获取键值对个数
m.empty(); // 判断是否为空
m.max_size(); // 获取最大可容纳元素数
m.clear(); // 清空所有键值对
 
// 元素访问
m[key]; // 访问/插入键key对应的值（无key则插入默认值）
m.at(key); // 访问键key的值（无key抛out_of_range异常）
m.begin(); // 返回指向第一个元素的迭代器
m.end(); // 返回指向尾后位置的迭代器
m.rbegin(); // 返回反向迭代器（指向最后一个元素）
m.rend(); // 返回反向尾后迭代器
 
// 增删元素
m.insert({key, val}); // 插入键值对（key已存在则不覆盖）
m.insert(pair<K,V>(key, val)); // 插入键值对（等价上式）
m.insert(iter, {key, val}); // 提示迭代器位置插入（提高效率）
m.emplace(key, val); // 原地构造键值对（比insert高效）
m.emplace_hint(iter, key, val); // 提示位置原地构造
m.erase(key); // 删除键key对应的键值对（返回删除个数）
m.erase(iter); // 删除迭代器指向的键值对
m.erase(begin, end); // 删除[begin,end)区间的键值对
m.swap(m2); // 交换两个map的内容
 
// 查找/统计
m.find(key); // 查找key，返回迭代器（找到）或m.end()（未找到）
m.count(key); // 统计key是否存在（map中返回0或1）
m.lower_bound(key); // 返回第一个≥key的键值对迭代器
m.upper_bound(key); // 返回第一个>key的键值对迭代器
m.equal_range(key); // 返回pair（lower_bound, upper_bound）

四、stack（栈，LIFO， 头文件）

// 基础属性
st.size(); // 获取栈中元素个数
st.empty(); // 判断栈是否为空（空返回true）
 
// 元素访问
st.top(); // 获取栈顶元素（栈空调用未定义）
 
// 增删元素
st.push(val); // 栈顶添加元素
st.emplace(args); // 栈顶原地构造元素（比push高效）
st.pop(); // 弹出栈顶元素（无返回值，栈空调用未定义）
st.swap(st2); // 交换两个栈的内容

五、queue（队列，FIFO ， 头文件）

// 基础属性
q.size(); // 获取队列中元素个数
q.empty(); // 判断队列是否为空（空返回true）
 
// 元素访问
q.front(); // 获取队首元素（队空调用未定义）
q.back(); // 获取队尾元素（队空调用未定义）
 
// 增删元素
q.push(val); // 队尾添加元素
q.emplace(args); // 队尾原地构造元素（比push高效）
q.pop(); // 弹出队首元素（无返回值，队空调用未定义）
q.swap(q2); // 交换两个队列的内容
```echarts

（3）结构体 基础

一、构造函数（初始化 结构体对象）

// 1. 无参构造函数
struct Person {
    string name;
    int age;
    Person(); // 声明无参构造
};
Person::Person() { // 定义：初始化成员为默认值
    name = "未知";
    age = 0;
}
// 作用：创建对象时自动调用，初始化成员（如 Person p; 会执行此函数）
 
// 2. 带参构造函数
struct Person {
    string name;
    int age;
    Person(string n, int a); // 声明带参构造
};
Person::Person(string n, int a) : name(n), age(a) {} // 初始化列表方式（更高效）
// 作用：创建对象时传参初始化（如 Person p("张三", 20);）
 
// 3. 拷贝构造函数
struct Person {
    string name;
    int age;
    Person(const Person& other); // 声明拷贝构造
};
Person::Person(const Person& other) {
    name = other.name;
    age = other.age;
}
// 作用：用已有对象初始化新对象（如 Person p2 = p1; 或 Person p2(p1);）

二、析构函数（释放资源）

struct Student {
    string* info; // 动态分配内存的成员
    // 构造函数
    Student(string s) {
        info = new string(s); // 分配内存
    }
    // 析构函数
    ~Student(); // 声明析构函数
};
Student::~Student() {
    delete info; // 释放动态分配的内存
    info = nullptr;
}
// 作用：对象销毁时自动调用，释放结构体占用的资源（如动态内存、文件句柄等）

三、普通成员函数（操作结构体数据）

struct Circle {
    double radius;
    // 成员函数：计算面积
    double getArea(); // 声明
    // 成员函数：设置半径
    void setRadius(double r); // 声明
};
// 定义成员函数
double Circle::getArea() {
    return 3.14159 * radius * radius;
}
void Circle::setRadius(double r) {
    if (r > 0) radius = r; // 加合法性校验
}
// 作用：封装结构体的操作逻辑，访问/修改成员变量（如 Circle c; c.setRadius(5); cout << c.getArea();）

四、运算符重载（自定义结构体运算规则）

struct Point {
    int x, y;
    // 重载 + 运算符：两个点相加
    Point operator+(const Point& other);
    // 重载 == 运算符：判断两个点是否相等
    bool operator==(const Point& other);
    // 重载 << 运算符：支持cout输出（友元函数）
    friend ostream& operator<<(ostream& os, const Point& p);
};
// 定义 + 重载
Point Point::operator+(const Point& other) {
    return {x + other.x, y + other.y};
}
// 定义 == 重载
bool Point::operator==(const Point& other) {
    return x == other.x && y == other.y;
}
// 定义 << 重载（友元函数）
ostream& operator<<(ostream& os, const Point& p) {
    os << "(" << p.x << "," << p.y << ")";
    return os;
}
// 作用：让结构体支持运算符操作（如 Point p1{1,2}, p2{3,4}; Point p3 = p1 + p2; if (p1 == p2) {...}; cout << p1;）

五、静态成员函数（属于结构体，而非对象）

struct Counter {
    static int count; // 静态成员变量
    // 静态成员函数
    static void addCount(); // 声明
    static int getCount(); // 声明
};
// 初始化静态成员变量
int Counter::count = 0;
// 定义静态成员函数
void Counter::addCount() {
    count++; // 访问静态成员变量（无需对象）
}
int Counter::getCount() {
    return count;
}
// 作用：无需创建对象即可调用，操作静态成员（如 Counter::addCount(); cout << Counter::getCount();）

六、常成员函数（保证不修改成员变量）

struct Book {
    string title;
    int pages;
    // 常成员函数：读取成员，不能修改
    string getTitle() const; // 声明时加const
};
string Book::getTitle() const {
    // title = "新标题"; // 编译错误：常函数不能修改成员
    return title;
}
// 作用：保证函数不会修改结构体成员，可被const对象调用（如 const Book b{"C++", 500}; b.getTitle();）
 
完整示例（综合所有核心函数）
#include <iostream>
#include <string>
using namespace std;
 
struct Person {
    // 成员变量
    string name;
    int age;
    string* address;
 
    // 1. 无参构造
    Person() : name("未知"), age(0), address(new string("未填写")) {
        cout << "无参构造调用" << endl;
    }
 
    // 2. 带参构造
    Person(string n, int a, string addr) : name(n), age(a), address(new string(addr)) {
        cout << "带参构造调用" << endl;
    }
 
    // 3. 拷贝构造
    Person(const Person& other) {
        name = other.name;
        age = other.age;
        address = new string(*(other.address)); // 深拷贝
        cout << "拷贝构造调用" << endl;
    }
 
    // 4. 析构函数
    ~Person() {
        delete address; // 释放动态内存
        address = nullptr;
        cout << "析构函数调用" << endl;
    }
 
    // 5. 普通成员函数
    void showInfo() const { // 常成员函数
        cout << "姓名：" << name << "，年龄：" << age << "，地址：" << *address << endl;
    }
 
    // 6. 运算符重载（赋值运算符）
    Person& operator=(const Person& other) {
        if (this == &other) return *this; // 防止自赋值
        // 释放当前资源
        delete address;
        // 深拷贝
        name = other.name;
        age = other.age;
        address = new string(*(other.address));
        cout << "赋值运算符调用" << endl;
        return *this;
    }
};
 
int main() {
    Person p1("张三", 25, "北京市");
    p1.showInfo();
 
    Person p2 = p1; // 拷贝构造
    p2.showInfo();
 
    Person p3; // 无参构造
    p3 = p1; // 赋值运算符
    p3.showInfo();
 
    return 0;
}

RE状态对应

Return 3221226356：Segmentation Fault 访问非法内存。

Return 3221225477：指向空地址（scanf() 没加 &）。

Return 3221225725：死循环 / 数组开过大。

Return 3221225620：除以 0

火车头加速

namespace io {
	class In {
		public:
			template<typename T>
			inline In &operator>>(T &x) {
				x=0; bool f=0; char c=getchar();
				while(c<'0'||c>'9') f|=(c=='-'),c=getchar();
				while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
				if(c=='.') {
					c=getchar(); double dot=0.1;
					while(c>='0'&&c<='9') x+=(c-'0')*dot,dot*=0.1,c=getchar();
				} return (f?x=-x:x),*this;
			}
			inline In &operator>>(char &x) {while(isspace(x=getchar())); return *this;}
			inline In &operator>>(char *x) {
				char c=getchar(); while(isspace(c)) c=getchar(); while(!isspace(c)&&~c) *(x++)=c,c=getchar();
				return *x=0,*this;
			}
			inline In &operator>>(string &x) {
				char c=getchar(); x.clear();
				while(isspace(c)) c=getchar(); while(!isspace(c)&&~c) x.push_back(c),c=getchar();
				return *this;
			}
			inline In &operator>>(In &in) { return in;}
	};
	class Out {
		private:
			char buf[35]; short dot=6,top=0;
		public:
			template<typename T>
			inline Out &operator<<(T x) {
				if(x<0) putchar('-'),x=-x;
				do { buf[++top]=x%10,x/=10;} while(x);
				while(top) putchar(buf[top--]|'0'); return *this;
			}
			inline Out &operator<<(char c) {return putchar(c),*this;}
			inline Out &operator<<(string x) {for(auto c:x) putchar(c); return *this;}
			inline Out &operator<<(char *x) {while(*x) putchar(*(x++)); return *this;}
			inline Out &operator<<(const char *x) {while(*x) putchar(*(x++)); return *this;}
			inline Out &operator<<(double x) {snprintf(buf,sizeof(buf),"%.*lf",dot,x); return (*this)<<buf;}
			inline Out &operator<<(Out &out) {return out;}
			inline Out &setdot(const int n) {return dot=n,*this;}
	};
	In fin;
	Out fout;
	inline Out &setdot(const int n,Out& out=fout) {return fout.setdot(n),out;}
	inline In &getline(char *x,In& in=fin) {
		char c=getchar();
		while(!(c==' '||!isspace(c))) c=getchar(); while(c==' '||!isspace(c)) (*x++)=c,c=getchar();
		return *x=0,in;
	}
	inline In &getline(string &x,In& in=fin) {
		char c=getchar(); x.clear();
		while(!(c==' '||!isspace(c))) c=getchar(); while(c==' '||!isspace(c)) x.push_back(c),c=getchar();
		return in;
	}
}
using namespace io;
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("avx,avx2,fma")

//依旧那咋子
//AC：Answer Coarse，粗劣的答案
//CE：Compile Easily，轻松通过编译
//PC：Perfect Compile，完美的编译
//WA：Wonderful Answer，好答案
//RE：Run Excellently，完美运行
//TLE：Time Limit Enough，时间充裕
//MLE：Memory Limit Enough，内存充裕
//OLE：Output Limit Enough，输出合法
//UKE：Unbelievably Keep Enough Score，难以置信地保持足够的分数
/*
                           _ooOoo_
                          o8888888o
                          88" . "88
                          (| -_- |)
                          O\  =  /O
                       ____/`---'\____
                     .'  \\|     |//  `.
                    /  \\|||  :  |||//  \
                   /  _||||| -:- |||||-  \
                   |   | \\\  -  /// |   |
                   | \_|  ''\---/''  |   |
                   \  .-\__  `-`  ___/-. /
                 ___`. .'  /--.--\  `. . __
              ."" '<  `.___\_<|>_/___.'  >'"".
             | | :  `- \`.;`\ _ /`;.`/ - ` : | |
             \  \ `-.   \_ __\ /__ _/   .-` /  /
        ======`-.____`-.___\_____/___.-`____.-'======
                           `=---='
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                 佛祖保佑       永无BUG
*/