//EYEHEAD VERSION 5 POWERED BY BADCAT [URL: https://hmgc.ct.ws/]
//
// /@@@@@@ /@@@@@@ /@@@@@ /@@@@@@ /@@@@@@ /@@@@@@@
// /@ /@ /@////@ /@////@ /@///// /@////@ ///@///
// /@@@@ /@ /@ /@ /@ /@ /@ /@ /@
// /@@@@@ /@@@@@@ /@ /@ /@ /@@@@@@ /@
// /@ /@ /@////@ /@ /@ /@ /@////@ /@
// BY /@@@@@@ /@ /@ /@@@@@ /@@@@@@ /@ /@ /@
//
// (c)BADCAT FACTORY CO' LTD 2025
// 由洛谷BadCatFactory（即badcat）自主制作，仅许使用，谢绝转载
// 大神Edsger Dijkstra
//
// # # #
// i i i
// i i i
// i i i
// i i i
// i i i
// iii
//
// 烧高香，拜大神，求AC！辟邪辟WA！
// Badcat被Hank盗号与Hank势不两立！
//import head files
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <unistd.h>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
//#include <windows.h> //Microsoft Windows Lib
//#include <winternl.h> //Microsoft WinNT Lib
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
//using namespace
using namespace std;
//defines
#define li long
#define ll long long
#define fl float
#define db double
#define bl bool
#define ldb long double
#define vi void
#define cr char
#define cs const
#define sg string
#define im INT_MAX
#define iw INT_MIN
#define null NULL
#define endl '\n'
#define gl(a) getline(cin,a)
#define rt return
#define rn return 0
#define mx max
#define mi min
#define co cout
#define ci cin
#define fr for
#define wl while
#define endt '\0'
#define sortdown(a,b) sort(a,b),reverse(a,b)
#define m_func int main
#define it int
#define fst ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mf_h it argc, cr** argv
#define te true
#define fe false
#define sq sqrt
#define sd signed
#define ce continue
#define bk break
#define inl inline
#define sw switch
#define ca case
#define dt default
#define fd fixed
#define set_p setprecision
#define sk stack
#define ps push
#define qe queue
#define ep empty
#define ft front
#define bc back
#define pp pop
#define to top
#define su struct
#define ue unsigned
#define sz size
#define ee else
#define infinity 0x7fffffff
#define INF infinity
#define del delete
#define nptr nullptr
#define vect vector
// 简化容器操作
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define cl(a) a.clear()
#define bg(a) a.begin()
#define ed(a) a.end()
#define rbg(a) a.rbegin()
#define red(a) a.rend()
#define fst_ first
#define snd_ second
// 简化数学运算
#define abs(a) ((a)<0?-(a):(a))
#define mid(a,b) ((a)+(b)>>1) // 取中间值（整除）
#define lowb(x) (x&-x) // 二进制最低位1
#define mod(a,b) ((a)%(b)+(b))%(b) // 取模（保证非负）
#define updmin(a,b) (a=min(a,b)) // 更新最小值
#define updmax(a,b) (a=max(a,b)) // 更新最大值
// 简化循环与条件
#define rep(i,a,b) for(int i=(a);i<=(b);i++) // 正向循环
#define rrep(i,a,b) for(int i=(a);i>=(b);i--) // 反向循环
#define each(i,a) for(auto &i:a) // 遍历容器元素
#define all(a) bg(a),ed(a) // 容器全部元素范围
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
// 简化位运算
#define setbit(x,i) (x|=(1<<i)) // 置位第i位
#define clrbit(x,i) (x&=~(1<<i)) // 清除第i位
#define chkbit(x,i) (x&(1<<i)) // 检查第i位是否为1
#define flipbit(x,i) (x^=(1<<i)) // 翻转第i位
// 简化数据结构定义
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define umii unordered_map<int,int>
#define umll unordered_map<ll,ll>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
// 补充宏定义
#define mem(a,b) memset(a,b,sizeof(a)) // 内存初始化
#define forin(i,a,n) for(int i=a;i<n;i++) // [a,n)区间循环
#define forni(i,n,a) for(int i=n-1;i>=a;i--) // (n,a]反向循环
#define cmin(a,b) ((a)=(a)<(b)?(a):(b)) // 自更新最小值
#define cmax(a,b) ((a)=(a)>(b)?(a):(b)) // 自更新最大值
#define isodd(x) ((x)&1) // 判断奇数
#define iseven(x) (!((x)&1)) // 判断偶数
#define dbg(x) cout<<#x<<"="<<x<<endl // 调试输出
#define filein(x) freopen(x,"r",stdin) // 读文件
#define fileout(x) freopen(x,"w",stdout) // 写文件
#define elif else if // 简化条件判断
// 补充数据结构
#define piii pair<pair<int,int>,int> // 三维pair
#define plll pair<pair<ll,ll>,ll> // 长整型三维pair
#define sti set<int>
#define stll set<ll>
#define ust unordered_set<int>
#define ustll unordered_set<ll>
#define dq deque<int>
#define dqll deque<ll>
#define pq priority_queue<int> // 大根堆
#define pqmin priority_queue<int,vector<int>,greater<int>> // 小根堆
// ===== 补充宏定义（控制流与操作）=====
#define repe(i,a,b) for(int i=(a);i<=(b);i++,i++) // 步长2循环
#define rep3(i,a,b) for(int i=(a);i<=(b);i+=3) // 步长3循环
#define breakif(cond) if(cond)break // 条件中断
#define continueif(cond) if(cond)continue // 条件继续
#define returnif(cond,val) if(cond)return val // 条件返回
#define inrange(x,l,r) ((x)>=(l)&&(x)<=(r)) // 判断在区间内
#define between(x,a,b) (min(a,b)<=x&&x<=max(a,b)) // 无序区间判断
#define bitlen(x) (32-__builtin_clz(x)) // 二进制长度（32位int）
#define llbitlen(x) (64-__builtin_clzll(x)) // 二进制长度（64位ll）
#define max3(a,b,c) max(a,max(b,c)) // 三数最大值
#define min3(a,b,c) min(a,min(b,c)) // 三数最小值
#define sum3(a,b,c) (a+b+c) // 三数之和
#define swap3(a,b,c) {auto t=a;a=b;b=c;c=t;} // 三变量交换
#define xchg(a,b) {auto t=a;a=b;b=t;} // 通用交换（替代swap_val）
#define maxn(a,n) {for(int i=1;i<n;i++)a[0]=max(a[0],a[i]);} // 数组最大值存a[0]
#define sgn(x) ((x)>0?1:((x)<0?-1:0)) // 符号函数
// ===== 补充宏定义（输入输出）=====
#define readi(a) cin>>(a)
#define readl(a) cin>>(a)
#define readc(a) cin>>(a)
#define reads(a) cin>>(a)
#define printi(a) cout<<(a)
#define printl(a) cout<<(a)
#define printc(a) cout<<(a)
#define prints(a) cout<<(a)
#define println(a) cout<<(a)<<endl
#define printsp(a) cout<<(a)<<" "
#define readarr(a,n) for(int i=0;i<n;i++)cin>>(a[i])
#define printarr(a,n) for(int i=0;i<n;i++)cout<<a[i]<<" "
#define printarrln(a,n) {printarr(a,n);cout<<endl;}
// ===== 补充数据结构（基础）=====
#define piiii pair<piii,int> // 四维pair
#define vvvi vector<vvi> // 三维int向量
#define vvvl vector<vvl> // 三维ll向量
#define stpii set<pii>
#define stpll set<pll>
#define mipii map<int,pii>
#define mplll map<ll,pll>
#define umpii unordered_map<int,pii>
#define umpll unordered_map<ll,pll>
#define ststi set<set<int>>
#define vsti vector<set<int>>
#define dqpii deque<pii>
#define dqpll deque<pll>
#define pqll priority_queue<ll>
#define pqllmin priority_queue<ll,vector<ll>,greater<ll>>
//functions
ll cf(ll a,ll b){ll x=1;fr(ll i=0;i<b;i++)x*=a;rt x;}//求次方
inl bl is_p(ll a){if(a==1){rt fe;}bl x=te;fr(ll j=2;j<=sq(a);j++){if(a%j==0)x=fe;}rt x;}//判断质数
it int_dx(it n){it s=0;wl(n){s=s*10+n%10;n/=10;}rt s;}//整数倒序
bl str_hw(cr *str){it len=strlen(str);fr(it i=0,j=len-1;i<j;i++,j--){if(str[i]!=str[j])rt fe;}rt te;}//判断回文字符串
bl int_hw(it n){it x=0,t=n;fr(it i=0;i<20;i++){if(n==0)bk;x*=10;x+=n%10;n/=10;}if(x==t)rt 1;rt 0;}//判断回文数
it atoi(sg s,it r){it a=0;fr(it i=0;i<s.sz();i++){cr t=s[i];if(t>='0'&&t<='9')a=a*r+t-'0';ee a=a*r+t-'a'+10;}rt a;}//R进制转换10进制
inl ll gcd(ll a, ll b) { wl(b) { a %= b; swap(a, b); } rt a; }// 计算a和b的最大公约数（欧几里得算法）
inl ll lcm(ll a, ll b) { rt a / gcd(a, b) * b; }// 计算a和b的最小公倍数（基于最大公约数）
inl ll qpow(ll a, ll b, ll mod) { ll res = 1; a %= mod; wl(b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } rt res; }// 快速幂：计算a^b % mod（高效求幂取模）
inl ll euler(ll n) { ll res = n; fr(ll i = 2; i * i <= n; i++) if (n % i == 0) { while (n % i == 0) n /= i; res -= res / i; } if (n > 1) res -= res / n; rt res; }// 计算区间[1,n]中与n互质的数的个数（欧拉函数）
inl bl is_leap(it y) { rt (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0); }// 检查是否为闰年（年份y）
inl sg to_lower(sg s) { fr(it i = 0; i < s.sz(); i++) s[i] = tolower(s[i]); rt s; }// 字符串转小写
inl ll prefix_sum(vect<ll>& a, it l, it r) { ll res = 0; fr(it i = l; i <= r; i++) res += a[i]; rt res; }// 求前缀和（数组a从l到r的和，0-based）
inl ll mul_mod(ll a, ll b, ll mod) { ll res = 0; a %= mod; wl(b) { if (b & 1) res = (res + a) % mod; a = (a << 1) % mod; b >>= 1; } rt res; }// 计算a*b%mod（处理大整数乘法防止溢出）
inl bl is_square(ll n) { ll x = sq(n); rt x * x == n || (x + 1) * (x + 1) == n; }// 判断数n是否为完全平方数
inl it max_idx(vect<ll>& a) { it idx = 0; fr(it i = 1; i < a.sz(); i++) if (a[i] > a[idx]) idx = i; rt idx; }// 求数组最大值下标（0-based）
inl ll comb(ll n, ll k) { if (k > n) rt 0; if (k == 0 || k == n) rt 1; k = mi(k, n - k); ll res = 1; fr(ll i = 1; i <= k; i++) res = res * (n - k + i) / i; rt res; }// 求组合数C(n,k)（n>=k>=0）
inl bl overlap(it l1, it r1, it l2, it r2) { rt mi(r1, r2) >= mx(l1, l2); }// 检查两个区间是否重叠（[l1,r1]与[l2,r2]）
inl it digit_cnt(ll n) { it cnt = 0; wl(n) { cnt++; n /= 10; } rt cnt ? cnt : 1; } // 计算n的位数
inl vi swap_val(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; } // 交换两个变量的值（通过引用）
inl ll arith_sum(ll l, ll r) { rt (r - l + 1) * (l + r) / 2; }// 计算区间[l,r]的和（等差数列）
inl it bit_count(ll x) { it cnt = 0; wl(x) { cnt += x & 1; x >>= 1; } rt cnt; }// 二进制中1的个数
//vars, custom functions, structs and arrays
cs ldb PI = 3.14159;
cs ldb E = 2.71828;
su vec2{ldb x,y;};
su vec3{ldb x,y,z;};
su vec2_int{it x,y;};
su vec3_int{it x,y,z;};
// 补充常量定义
const int MOD = 1e9+7; // 常用模值
const int MOD2 = 998244353; // 另一个常用模值
const int BASE = 131; // 字符串哈希基数
const int MAXN = 1e5+5; // 常用数组大小上限
const int MAXM = 1e6+5; // 大数组大小上限
const ll LLINF = 1e18; // long long类型无穷大
const double EPS = 1e-8; // 浮点数精度
const int DIR4[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 四方向
const int DIR8[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; // 八方向
// 链表节点结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 二叉树节点结构
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 图的边结构
struct Edge {
int to, w; // 目标节点、权重
Edge(int t, int _w) : to(t), w(_w) {}
};
// 带权值的pair（用于优先队列）
struct WPair {
ll w; int v;
WPair(ll _w, int _v) : w(_w), v(_v) {}
bool operator<(const WPair& other) const {
return w > other.w; // 小根堆
}
};
// ===== 补充常量定义 =====
const int inv2 = 500000004; // MOD=1e9+7下的2逆元
const int inv3 = 333333336; // MOD=1e9+7下的3逆元
const int inv5 = 200000001; // MOD=1e9+7下的5逆元
const ll BASE2 = 911382629; // 备用哈希基数
const ll MOD3 = 1e18+3; // 大模数
const int MAXK = 20; // 常用于log2(MAXN)的大小
const int MAXT = 1e3+5; // 测试用例数量上限
const int nullval = -1e9; // 空值标记
const double PI2 = PI*2; // 2π
const double PID2 = PI/2; // π/2
const double EPS2 = 1e-6; // 较高精度
const double INF_D = 1e18; // 浮点无穷大
const int DIR6[6][3] = {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}}; // 三维方向
// ===== 补充数据结构（算法专用）=====
// 线段树(区间和+单点更新)
struct SegTree {
vector<ll> tree;
int n;
SegTree(int sz) {
n=1; while(n<sz)n<<=1;
tree.resize(2*n);
}
void update(int pos, ll val) {
pos+=n; tree[pos]=val;
for(pos>>=1;pos>=1;pos>>=1)
tree[pos]=tree[2*pos]+tree[2*pos+1];
}
ll query(int l, int r) { // [l,r)
l+=n; r+=n; ll res=0;
while(l<r) {
if(l&1) res+=tree[l++];
if(r&1) res+=tree[--r];
l>>=1; r>>=1;
}
return res;
}
};
// 树状数组(Fenwick Tree)
struct BIT {
vector<ll> tr;
int n;
BIT(int sz) : n(sz), tr(sz+1) {}
void add(int x, ll v) {
for(;x<=n;x+=lowb(x)) tr[x]+=v;
}
ll sum(int x) {
ll res=0;
for(;x>0;x-=lowb(x)) res+=tr[x];
return res;
}
ll range_sum(int l, int r) {
return sum(r)-sum(l-1);
}
};
// 字符串哈希结构
struct StrHash {
vector<ll> hash, pow;
int n;
StrHash(string s) {
n=s.size();
hash.resize(n+1);
pow.resize(n+1);
pow[0]=1;
for(int i=0;i<n;i++) {
hash[i+1] = hash[i] * BASE + s[i];
pow[i+1] = pow[i] * BASE;
}
}
ll get_hash(int l, int r) { // [l,r] 1-based
return hash[r] - hash[l-1] * pow[r-l+1];
}
};
// ===== 宏定义（控制流增强）=====
#define loop(i,a,b) for(decltype(b) i=(a);i<(b);++i)
#define loopr(i,a,b) for(decltype(b) i=(b)-1;i>=(a);--i)
#define loop_eq(i,a,b) for(decltype(b) i=(a);i<=(b);++i)
#define loopr_eq(i,a,b) for(decltype(b) i=(b);i>=(a);--i)
#define loop_var(i,var) for(auto& i : var)
#define loop_cond(i,a,b,cond) for(decltype(b) i=(a);i<(b)&&(cond);++i)
#define break_unless(cond) if(!(cond))break
#define continue_unless(cond) if(!(cond))continue
#define return_unless(cond,val) if(!(cond))return val
#define repeat(n) for(int i=0;i<(n);++i)
#define repeat2(n) for(int i=0;i<(n);++i)for(int j=0;j<(n);++j)
#define repeat3(n) for(int i=0;i<(n);++i)for(int j=0;j<(n);++j)for(int k=0;k<(n);++k)
#define until(cond) while(!(cond))
#define times(n) for(int _=0;_<(n);++_)
#define forever for(;;)
// ===== 宏定义（数值操作）=====
#define square(x) ((x)*(x))
#define cube(x) ((x)*(x)*(x))
#define pow4(x) ((x)*(x)*(x)*(x))
#define avg(a,b) ((a)+(b))/2.0
#define avg3(a,b,c) ((a)+(b)+(c))/3.0
#define clamp(x,a,b) ((x)<(a)?(a):((x)>(b)?(b):(x)))
#define inc(x) (++(x))
#define dec(x) (--(x))
#define inc_val(x,v) ((x)+=(v))
#define dec_val(x,v) ((x)-=(v))
#define mul_val(x,v) ((x)*=(v))
#define div_val(x,v) ((x)/=(v))
#define mod_val(x,v) ((x)%=(v))
#define bit_set(x) __builtin_popcount(x)
#define bit_setll(x) __builtin_popcountll(x)
#define bit_parity(x) __builtin_parity(x)
#define bit_leading_zero(x) __builtin_clz(x)
#define bit_trailing_zero(x) __builtin_ctz(x)
#define bit_leading_zeroll(x) __builtin_clzll(x)
#define bit_trailing_zeroll(x) __builtin_ctzll(x)
#define rotl(x,n) ((x)<<(n)|(x)>>(sizeof(x)*8-(n)))
#define rotr(x,n) ((x)>>(n)|(x)<<(sizeof(x)*8-(n)))
#define is_pow2(x) ((x)&&!((x)&(x)-1))
#define next_pow2(x) (1<<(32-__builtin_clz((x)-1)))
#define prev_pow2(x) (1<<(31-__builtin_clz(x)))
// ===== 宏定义（容器操作）=====
#define push_all(a,b) for(auto& x:b)a.pb(x)
#define pop_all(a) while(!a.empty())a.pop()
#define clear_all(...) void(0);va_list vl;va_start(vl,__VA_ARGS__);while(1){auto*p=va_arg(vl,void*);if(!p)break;((vector<int>*)p)->clear();};va_end(vl)
#define reverse_all(a) reverse(bg(a),ed(a))
#define sort_all(a) sort(bg(a),ed(a))
#define sort_all_desc(a) sort(bg(a),ed(a),greater<decltype(a[0])>())
#define sort_by(a,func) sort(bg(a),ed(a),[](auto&x,auto&y){return func(x)<func(y);})
#define find_in(a,x) find(bg(a),ed(a),x)!=ed(a)
#define count_in(a,x) count(bg(a),ed(a),x)
#define sum_all(a) accumulate(bg(a),ed(a),0LL)
#define max_all(a) *max_element(bg(a),ed(a))
#define min_all(a) *min_element(bg(a),ed(a))
#define erase_val(a,x) a.erase(remove(bg(a),ed(a),x),ed(a))
#define unique_all(a) a.erase(unique(bg(a),ed(a)),ed(a))
#define resize_all(a,n) a.resize(n)
#define reserve_all(a,n) a.reserve(n)
// ===== 宏定义（输入输出增强）=====
#define readall(...) void(0);va_list vl;va_start(vl,__VA_ARGS__);while(1){auto*p=va_arg(vl,void*);if(!p)break;cin>>*((int*)p);};va_end(vl)
#define printall(...) void(0);va_list vl;va_start(vl,__VA_ARGS__);while(1){auto*p=va_arg(vl,void*);if(!p)break;cout<<*((int*)p)<<" ";};va_end(vl);cout<<endl
#define readpair(a,b) cin>>(a)>>(b)
#define printpair(a,b) cout<<(a)<<" "<<(b)<<endl
#define readtuple(a,b,c) cin>>(a)>>(b)>>(c)
#define printtuple(a,b,c) cout<<(a)<<" "<<(b)<<" "<<(c)<<endl
#define readline(s) getline(cin,s)
#define printdebug(...) fprintf(stderr,__VA_ARGS__)
#define eprint(...) cout<<__VA_ARGS__<<endl
#define eprintsp(...) cout<<__VA_ARGS__<<" "
#define read_ll(a) scanf("%lld",&(a))
#define print_ll(a) printf("%lld",(a))
#define print_lln(a) printf("%lld\n",(a))
#define read_d(a) scanf("%lf",&(a))
#define print_d(a) printf("%lf",(a))
#define print_dn(a) printf("%lf\n",(a))
// ===== 常量定义（扩展）=====
// 更多模值
const int MOD4 = 1e9+9;
const int MOD5 = 1e8+7;
const int MOD6 = 19260817;
const int MOD7 = 20040301;
const ll MOD8 = 1e18+7;
const ll MOD9 = 9223372036854775783LL;
// 更多逆元（基于MOD=1e9+7）
const int inv4 = 250000002;
const int inv6 = 166666668;
const int inv7 = 142857144;
const int inv8 = 125000001;
const int inv9 = 111111112;
const int inv10 = 100000001;
// 更多哈希基数
const ll BASE3 = 1000003;
const ll BASE4 = 972663749;
const ll BASE5 = 35714285;
// 数组大小常量
const int MAXN2 = 2e5+5;
const int MAXN3 = 5e5+5;
const int MAXN4 = 1e6+5;
const int MAXN5 = 2e6+5;
const int MAXN6 = 5e6+5;
const int MAXN7 = 1e7+5;
// 其他常量
const int BITS = 32;
const int BITS64 = 64;
const int LOG = 20;
const int LOG2 = 17;
const int PHI = 4294967296; // 2^32的欧拉函数值
const double GOLD = (1.0+sqrt(5.0))/2.0; // 黄金比例
const double EPS3 = 1e-9;
const double EPS4 = 1e-12;
const long double LDEPS = 1e-18;
const int MONTH[] = {31,28,31,30,31,30,31,31,30,31,30,31}; // 月份天数
const int MONTH_LEAP[] = {31,29,31,30,31,30,31,31,30,31,30,31}; // 闰年月份天数
// 方向数组扩展
const int DIR4X[] = {-1,1,0,0};
const int DIR4Y[] = {0,0,-1,1};
const int DIR8X[] = {-1,-1,-1,0,0,1,1,1};
const int DIR8Y[] = {-1,0,1,-1,1,-1,0,1};
const int DIR16[16][2] = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1},
{-1,-1},{-1,1},{1,-1},{1,1},{0,-2},{0,2},{-2,0},{2,0}}; // 马走日+邻接
const int DIR6X[] = {-1,1,0,0,0,0};
const int DIR6Y[] = {0,0,-1,1,0,0};
const int DIR6Z[] = {0,0,0,0,-1,1};
// ===== 数据结构（扩展）=====
// 高级pair类型
#define pii4 pair<pii,pii>
#define pll2 pair<ll,ll>
#define pll3 pair<pll2,ll>
#define pll4 pair<pll2,pll2>
#define pdd pair<double,double>
#define pdd3 pair<pdd,double>
#define pdd4 pair<pdd,pdd>
#define pdi pair<double,int>
#define pid pair<int,double>
#define pli pair<int,ll>
#define pil pair<ll,int>
// 高级容器类型
#define vvvi2 vector<vvvi> // 4维int向量
#define vvvl2 vector<vvvl> // 4维ll向量
#define vd vector<double>
#define vvd vector<vd>
#define vvvd vector<vvd>
#define vvvvd vector<vvvd>
#define vs vector<string>
#define vvs vector<vs>
#define vvvs vector<vvs>
#define msi map<string,int>
#define mis map<int,string>
#define mss map<string,string>
#define umsi unordered_map<string,int>
#define umis unordered_map<int,string>
#define umss unordered_map<string,string>
#define sti2 set<set<int>>
#define sti3 set<sti2>
#define stll2 set<set<ll>>
#define vsti2 vector<vsti>
#define mpq map<pair<int,int>,queue<int>>
#define spq set<pair<int,queue<int>>>
// 链表结构扩展
struct DListNode { // 双向链表
int val;
DListNode *prev, *next;
DListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};
// 树结构扩展
struct TreeEdge { // 树的边
int to, w;
TreeEdge(int t, int _w=1) : to(t), w(_w) {}
};
struct TrieNode { // 字典树节点
int cnt;
TrieNode* children[26];
TrieNode() : cnt(0) {
memset(children, 0, sizeof(children));
}
};
struct AhoNode { // Aho-Corasick自动机节点
int fail, cnt;
AhoNode* children[26];
AhoNode() : fail(0), cnt(0) {
memset(children, 0, sizeof(children));
}
};
// 图结构扩展
struct GraphEdge { // 带属性的图边
int from, to, w;
GraphEdge(int f, int t, int _w=1) : from(f), to(t), w(_w) {}
bool operator<(const GraphEdge& other) const {
return w < other.w;
}
};
struct FlowEdge { // 网络流边
int to, rev;
ll cap;
FlowEdge(int t, int r, ll c) : to(t), rev(r), cap(c) {}
};
// 算法专用结构
struct Matrix { // 矩阵
int n, m;
vector<vector<ll>> data;
Matrix(int _n, int _m) : n(_n), m(_m), data(_n, vector<ll>(_m, 0)) {}
Matrix operator*(const Matrix& other) const {
Matrix res(n, other.m);
loop(i,0,n) loop(j,0,other.m) loop(k,0,m)
res.data[i][j] = (res.data[i][j] + data[i][k] * other.data[k][j]) % MOD;
return res;
}
};
struct Line { // 二维直线
double a, b, c; // ax + by + c = 0
Line(double x1, double y1, double x2, double y2) {
a = y2 - y1;
b = x1 - x2;
c = x2*y1 - x1*y2;
}
};
struct Circle { // 圆
double x, y, r;
Circle(double _x, double _y, double _r) : x(_x), y(_y), r(_r) {}
};
// ===== 高级数据结构实现 =====
// 扩展线段树（区间更新+区间查询）
struct SegTreeEx {
struct Node {
ll sum, lazy;
Node() : sum(0), lazy(0) {}
};
vector<Node> tree;
int n;
SegTreeEx(int sz) {
n = 1;
while (n < sz) n <<= 1;
tree.resize(2 * n);
}
void push(int pos, int l, int r) {
if (tree[pos].lazy == 0) return;
int mid = (l + r) / 2;
tree[2*pos].sum += tree[pos].lazy * (mid - l + 1);
tree[2*pos].lazy += tree[pos].lazy;
tree[2*pos+1].sum += tree[pos].lazy * (r - mid);
tree[2*pos+1].lazy += tree[pos].lazy;
tree[pos].lazy = 0;
}
void update_range(int pos, int l, int r, int ul, int ur, ll val) {
if (ur < l || ul > r) return;
if (ul <= l && r <= ur) {
tree[pos].sum += val * (r - l + 1);
tree[pos].lazy += val;
return;
}
push(pos, l, r);
int mid = (l + r) / 2;
update_range(2*pos, l, mid, ul, ur, val);
update_range(2*pos+1, mid+1, r, ul, ur, val);
tree[pos].sum = tree[2*pos].sum + tree[2*pos+1].sum;
}
ll query_range(int pos, int l, int r, int ql, int qr) {
if (qr < l || ql > r) return 0;
if (ql <= l && r <= qr) return tree[pos].sum;
push(pos, l, r);
int mid = (l + r) / 2;
return query_range(2*pos, l, mid, ql, qr) +
query_range(2*pos+1, mid+1, r, ql, qr);
}
void update(int l, int r, ll val) {
update_range(1, 0, n-1, l, r, val);
}
ll query(int l, int r) {
return query_range(1, 0, n-1, l, r);
}
};
// 可持久化线段树
struct PersistentSegTree {
struct Node {
int l, r, cnt;
Node *left, *right;
Node(int _l, int _r) : l(_l), r(_r), cnt(0), left(nullptr), right(nullptr) {}
};
Node* build(int l, int r) {
Node* node = new Node(l, r);
if (l == r) return node;
int mid = (l + r) / 2;
node->left = build(l, mid);
node->right = build(mid+1, r);
return node;
}
Node* update(Node* prev, int pos, int val) {
Node* node = new Node(prev->l, prev->r);
node->left = prev->left;
node->right = prev->right;
node->cnt = prev->cnt + val;
if (prev->l == prev->r) return node;
int mid = (prev->l + prev->r) / 2;
if (pos <= mid) node->left = update(prev->left, pos, val);
else node->right = update(prev->right, pos, val);
return node;
}
int query(Node* node, int l, int r) {
if (node->r < l || node->l > r) return 0;
if (l <= node->l && node->r <= r) return node->cnt;
return query(node->left, l, r) + query(node->right, l, r);
}
};
// 带权并查集
struct WeightedDSU {
vector<int> fa, sz, w;
WeightedDSU(int n) : fa(n+1), sz(n+1, 1), w(n+1, 0) {
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
if (fa[x] != x) {
int f = fa[x];
fa[x] = find(fa[x]);
w[x] += w[f];
}
return fa[x];
}
bool merge(int x, int y, int c) { // x比y重c
int fx = find(x), fy = find(y);
if (fx == fy) return false;
if (sz[fx] < sz[fy]) {
swap(fx, fy);
swap(x, y);
c = -c;
}
fa[fy] = fx;
sz[fx] += sz[fy];
w[fy] = w[x] - w[y] - c;
return true;
}
int get_weight(int x) {
find(x);
return w[x];
}
};
// 单调栈
struct MonotonicStack {
stack<int> st;
void push(int val) {
while (!st.empty() && st.top() < val) st.pop();
st.push(val);
}
void pop() {
if (!st.empty()) st.pop();
}
int top() {
return st.top();
}
bool empty() {
return st.empty();
}
int size() {
return st.size();
}
};
// 网络流（Dinic算法）
struct Dinic {
vector<vector<FlowEdge>> g;
vector<int> level, iter;
int n;
Dinic(int _n) : n(_n), g(_n), level(_n), iter(_n) {}
void add_edge(int from, int to, ll cap) {
g[from].emplace_back(to, g[to].size(), cap);
g[to].emplace_back(from, g[from].size()-1, 0);
}
void bfs(int s) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front(); q.pop();
for (auto& e : g[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int& i = iter[v]; i < g[v].size(); ++i) {
FlowEdge& e = g[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
g[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
ll max_flow(int s, int t) {
ll flow = 0;
while (true) {
bfs(s);
if (level[t] < 0) return flow;
fill(iter.begin(), iter.end(), 0);
ll f;
while ((f = dfs(s, t, LLINF)) > 0) {
flow += f;
}
}
}
};
// 字符串后缀自动机
struct SuffixAutomaton {
struct State {
int len, link;
map<char, int> next;
};
vector<State> st;
int last;
SuffixAutomaton() {
st.emplace_back();
st[0].len = 0;
st[0].link = -1;
last = 0;
}
void extend(char c) {
int p = last;
int curr = st.size();
st.emplace_back();
st[curr].len = st[last].len + 1;
while (p != -1 && !st[p].next.count(c)) {
st[p].next[c] = curr;
p = st[p].link;
}
if (p == -1) {
st[curr].link = 0;
} else {
int q = st[p].next[c];
if (st[p].len + 1 == st[q].len) {
st[curr].link = q;
} else {
int clone = st.size();
st.push_back(st[q]);
st[clone].len = st[p].len + 1;
while (p != -1 && st[p].next[c] == q) {
st[p].next[c] = clone;
p = st[p].link;
}
st[q].link = clone;
st[curr].link = clone;
}
}
last = curr;
}
};
// ===== 工具函数（扩展）=====
// 数论函数
inl ll mod_pow(ll a, ll b, ll mod) { // 带模快速幂
ll res = 1;
a %= mod;
while (b) {
if (b & 1) res = (__int128)res * a % mod;
a = (__int128)a * a % mod;
b >>= 1;
}
return res;
}
inl ll mod_inv(ll a, ll mod) { // 模逆元（费马小定理）
return mod_pow(a, mod - 2, mod);
}
inl ll crt(const vector<ll>& a, const vector<ll>& m) { // 中国剩余定理
ll M = 1, res = 0;
loop(i,0,a.size()) M *= m[i];
loop(i,0,a.size()) {
ll Mi = M / m[i];
ll inv = mod_inv(Mi, m[i]);
res = (res + a[i] * Mi % M * inv % M) % M;
}
return res;
}
inl void factorize(ll n, vector<ll>& res) { // 质因数分解
if (n % 2 == 0) {
res.pb(2);
while (n % 2 == 0) n /= 2;
}
for (ll i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
res.pb(i);
while (n % i == 0) n /= i;
}
}
if (n > 1) res.pb(n);
}
inl ll pollards_rho(ll n) { // Pollard's Rho算法（大整数分解）
if (n % 2 == 0) return 2;
if (n % 3 == 0) return 3;
if (n % 5 == 0) return 5;
while (true) {
ll c = rand() % (n - 1) + 1;
auto f = [&](ll x) { return ((__int128)x * x + c) % n; };
ll x = 2, y = 2, d = 1;
ll q = 1;
int steps = 0, max_steps = 1 << 20;
while (d == 1 && steps < max_steps) {
x = f(x);
y = f(f(y));
d = gcd(abs(x - y), n);
steps++;
}
if (d != 1 && d != n) return d;
}
}
// 组合数学
inl void precompute_factorials(vector<ll>& fact, vector<ll>& inv_fact, int n, ll mod) {
fact.resize(n + 1);
inv_fact.resize(n + 1);
fact[0] = 1;
loop(i,1,n+1) fact[i] = fact[i-1] * i % mod;
inv_fact[n] = mod_inv(fact[n], mod);
loopr(i,0,n-1) inv_fact[i] = inv_fact[i+1] * (i+1) % mod;
}
inl ll comb_mod(ll n, ll k, const vector<ll>& fact, const vector<ll>& inv_fact, ll mod) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % mod * inv_fact[n - k] % mod;
}
inl ll lucas(ll n, ll k, ll mod, const vector<ll>& fact, const vector<ll>& inv_fact) {
if (k == 0) return 1;
return comb_mod(n % mod, k % mod, fact, inv_fact, mod) *
lucas(n / mod, k / mod, mod, fact, inv_fact) % mod;
}
// 字符串函数
inl vector<int> kmp_prefix(const string& s) { // KMP前缀函数
int n = s.size();
vector<int> pi(n);
loop(i,1,n) {
int j = pi[i-1];
while (j > 0 && s[i] != s[j]) j = pi[j-1];
if (s[i] == s[j]) j++;
pi[i] = j;
}
return pi;
}
inl vector<int> z_function(const string& s) { // Z函数
int n = s.size();
vector<int> z(n);
int l = 0, r = 0;
loop(i,1,n) {
if (i <= r) z[i] = min(r - i + 1, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
z[0] = n;
return z;
}
inl int edit_distance(const string& a, const string& b) { // 编辑距离
int n = a.size(), m = b.size();
vector<vector<int>> dp(n+1, vector<int>(m+1));
loop(i,0,n) dp[i][0] = i;
loop(i,0,m) dp[0][i] = i;
loop(i,1,n+1) loop(j,1,m+1) {
dp[i][j] = min3(dp[i-1][j]+1, dp[i][j-1]+1,
dp[i-1][j-1] + (a[i-1] != b[j-1]));
}
return dp[n][m];
}
// 几何函数
inl double distance(double x1, double y1, double x2, double y2) {
return sqrt(square(x1-x2) + square(y1-y2));
}
inl double cross(double x1, double y1, double x2, double y2) { // 叉积
return x1 * y2 - x2 * y1;
}
inl double dot(double x1, double y1, double x2, double y2) { // 点积
return x1 * x2 + y1 * y2;
}
inl bool is_point_on_segment(double x, double y, double x1, double y1, double x2, double y2) {
if (min(x1, x2) - EPS > x || x > max(x1, x2) + EPS) return false;
if (min(y1, y2) - EPS > y || y > max(y1, y2) + EPS) return false;
return fabs(cross(x1 - x, y1 - y, x2 - x, y2 - y)) < EPS;
}
// 动态规划辅助函数
inl void precompute_1d_dp(vector<ll>& dp, int n, ll init_val) {
dp.resize(n+1);
fill(all(dp), init_val);
dp[0] = 0; // 默认边界条件
}
inl void precompute_2d_dp(vector<vector<ll>>& dp, int n, int m, ll init_val) {
dp.resize(n+1, vector<ll>(m+1, init_val));
dp[0][0] = 0; // 默认边界条件
}
// 排序与搜索
inl int lower_bound_idx(const vector<ll>& a, ll x) {
int l = 0, r = a.size();
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] < x) l = mid + 1;
else r = mid;
}
return l;
}
inl int upper_bound_idx(const vector<ll>& a, ll x) {
int l = 0, r = a.size();
while (l < r) {
int mid = (l + r) / 2;
if (a[mid] <= x) l = mid + 1;
else r = mid;
}
return l;
}
inl void radix_sort(vector<int>& a) { // 基数排序
int n = a.size();
int max_val = max_all(a);
for (int exp = 1; max_val / exp > 0; exp *= 10) {
vector<int> output(n), count(10, 0);
loop(i,0,n) count[(a[i]/exp)%10]++;
loop(i,1,10) count[i] += count[i-1];
loopr(i,0,n-1) {
output[count[(a[i]/exp)%10]-1] = a[i];
count[(a[i]/exp)%10]--;
}
a = output;
}
}
// 其他实用函数
inl vector<int> generate_primes(int n) { // 埃氏筛生成质数
vector<bool> is_prime(n+1, true);
vector<int> primes;
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
primes.pb(i);
for (int j = 2*i; j <= n; j += i)
is_prime[j] = false;
}
}
return primes;
}
inl string int_to_string(ll x) { // 整数转字符串
if (x == 0) return "0";
bool neg = false;
if (x < 0) { neg = true; x = -x; }
string s;
while (x > 0) {
s += (x % 10) + '0';
x /= 10;
}
if (neg) s += '-';
reverse(all(s));
return s;
}
inl void random_shuffle(vector<int>& a) { // 随机打乱
srand(time(0));
loop(i,0,a.size()) {
int j = rand() % (a.size() - i) + i;
swap(a[i], a[j]);
}
}
// ===== 额外宏定义 =====
#define is_negative(x) ((x) < 0)
#define is_positive(x) ((x) > 0)
#define is_zero(x) ((x) == 0)
#define abs_diff(a,b) abs((a)-(b))
#define sum_sq(a,b) (square(a)+square(b))
#define sum_cu(a,b) (cube(a)+cube(b))
#define max_abs(a,b) max(abs(a),abs(b))
#define min_abs(a,b) min(abs(a),abs(b))
#define mid3(a,b,c) (a+b+c-max3(a,b,c)-min3(a,b,c)) // 三数中间值
#define between_val(x,a,b) (min(a,b)<=x&&x<=max(a,b))
#define in_range_val(x,l,r) ((x)>=l&&(x)<=r)
#define is_inf(x) ((x)==INF||(x)==-INF)
#define is_nan(x) (x!=x)
#define swap_arr(a,i,j) {auto t=a[i];a[i]=a[j];a[j]=t;}
#define reverse_arr(a,l,r) {for(int i=l,j=r;i<j;i++,j--)swap_arr(a,i,j);}
#define fill_arr(a,l,r,val) {for(int i=l;i<=r;i++)a[i]=val;}
#define copy_arr(a,b,l,r) {for(int i=l;i<=r;i++)a[i]=b[i];}
#define equal_arr(a,b,l,r) {bool f=1;for(int i=l;i<=r;i++)if(a[i]!=b[i]){f=0;break;}f;}
// ===== 补充常量 =====
const int PRIME1 = 2;
const int PRIME2 = 3;
const int PRIME3 = 5;
const int PRIME4 = 7;
const int PRIME5 = 11;
const int HASH_OFF = 911382629; // 哈希偏移量
const int FIB[] = {1,1,2,3,5,8,13,21,34,55,89,144}; // 斐波那契数列
const double ANGLE_30 = PI/6;
const double ANGLE_45 = PI/4;
const double ANGLE_60 = PI/3;
const double ANGLE_90 = PI/2;
const double ANGLE_180 = PI;
const double ANGLE_270 = 3*PI/2;
const double ANGLE_360 = 2*PI;
const int WEEK_DAYS = 7;
const int MONTHS = 12;
const int HOURS = 24;
const int MINUTES = 60;
const int SECONDS = 60;
// ===== 数据结构补充 =====
// 区间结构
struct Interval {
int l, r;
Interval(int _l, int _r) : l(_l), r(_r) {}
bool operator<(const Interval& other) const {
return l < other.l || (l == other.l && r < other.r);
}
int length() const { return r - l + 1; }
bool contains(int x) const { return l <= x && x <= r; }
bool intersects(const Interval& other) const {
return max(l, other.l) <= min(r, other.r);
}
};
// 分数结构
struct Fraction {
ll num, den; // 分子,分母
Fraction(ll n=0, ll d=1) {
ll g = gcd(abs(n), abs(d));
num = n / g;
den = d / g;
if (den < 0) { num *= -1; den *= -1; }
}
Fraction operator+(const Fraction& f) const {
return Fraction(num*f.den + f.num*den, den*f.den);
}
Fraction operator-(const Fraction& f) const {
return Fraction(num*f.den - f.num*den, den*f.den);
}
Fraction operator*(const Fraction& f) const {
return Fraction(num*f.num, den*f.den);
}
Fraction operator/(const Fraction& f) const {
return Fraction(num*f.den, den*f.num);
}
bool operator<(const Fraction& f) const {
return num * f.den < f.num * den;
}
double to_double() const {
return (double)num / den;
}
};
// 多项式结构
struct Polynomial {
vector<ll> coeff; // 系数,coeff[i]是x^i的系数
Polynomial(int n=0) : coeff(n+1, 0) {}
int degree() const {
int d = coeff.size() - 1;
while (d >= 0 && coeff[d] == 0) d--;
return d;
}
Polynomial operator+(const Polynomial& p) const {
int d = max(degree(), p.degree());
Polynomial res(d);
for (int i = 0; i <= d; i++) {
res.coeff[i] = (i < coeff.size() ? coeff[i] : 0) +
(i < p.coeff.size() ? p.coeff[i] : 0);
}
return res;
}
Polynomial operator*(const Polynomial& p) const {
int d = degree() + p.degree();
Polynomial res(d);
for (int i = 0; i <= degree(); i++) {
for (int j = 0; j <= p.degree(); j++) {
res.coeff[i+j] += coeff[i] * p.coeff[j];
}
}
return res;
}
};
// 栈结构扩展
template<typename T>
struct Stack {
vector<T> data;
void push(T x) { data.push_back(x); }
void pop() { data.pop_back(); }
T top() { return data.back(); }
bool empty() { return data.empty(); }
int size() { return data.size(); }
T get(int idx) { return data[idx]; }
void clear() { data.clear(); }
};
// 队列结构扩展
template<typename T>
struct Queue {
vector<T> data;
int front_idx;
Queue() : front_idx(0) {}
void push(T x) { data.push_back(x); }
void pop() { front_idx++; }
T front() { return data[front_idx]; }
bool empty() { return front_idx >= data.size(); }
int size() { return data.size() - front_idx; }
void clear() { data.clear(); front_idx = 0; }
};
// ===== 算法实现补充 =====
// 最长公共前缀
string longest_common_prefix(const vector<string>& strs) {
if (strs.empty()) return "";
string res = strs[0];
for (const string& s : strs) {
int i = 0;
while (i < res.size() && i < s.size() && res[i] == s[i]) {
i++;
}
res = res.substr(0, i);
if (res.empty()) break;
}
return res;
}
// 辅助函数: 中心扩展
int expand_around_center(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return right - left - 1;
}
// 最长递增子序列(LIS)
vector<int> longest_increasing_subsequence(const vector<int>& a) {
vector<int> tails, prev(a.size(), -1), index(a.size());
for (int i = 0; i < a.size(); i++) {
int x = a[i];
int pos = lower_bound(tails.begin(), tails.end(), x) - tails.begin();
if (pos == tails.size()) {
tails.push_back(x);
} else {
tails[pos] = x;
}
index[pos] = i;
if (pos > 0) prev[i] = index[pos - 1];
}
// 重构LIS
vector<int> res;
int cur = index[tails.size() - 1];
while (cur != -1) {
res.push_back(a[cur]);
cur = prev[cur];
}
reverse(res.begin(), res.end());
return res;
}
// 最长公共子序列(LCS)
vector<int> longest_common_subsequence(const vector<int>& a, const vector<int>& b) {
int n = a.size(), m = b.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// 重构LCS
vector<int> res;
int i = n, j = m;
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) {
res.push_back(a[i - 1]);
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
reverse(res.begin(), res.end());
return res;
}
// 矩阵快速幂
Matrix matrix_pow(Matrix a, ll power) {
Matrix res(a.n, a.n);
// 初始化单位矩阵
for (int i = 0; i < a.n; i++) {
res.data[i][i] = 1;
}
while (power > 0) {
if (power % 2 == 1) {
res = res * a;
}
a = a * a;
power /= 2;
}
return res;
}
// 前缀函数应用: KMP匹配
vector<int> kmp_search(const string& text, const string& pattern) {
string s = pattern + "#" + text;
vector<int> pi = kmp_prefix(s);
vector<int> res;
for (int i = pattern.size() + 1; i < s.size(); i++) {
if (pi[i] == pattern.size()) {
res.push_back(i - 2 * pattern.size());
}
}
return res;
}
// 素数判定优化版(Miller-Rabin)
bool is_prime(ll n) {
if (n <= 1) return false;
if (n <= 3) return true;
if (n % 2 == 0) return false;
// 写成n-1 = d*2^s
ll d = n - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
// 测试几个基
vector<ll> bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (ll a : bases) {
if (a >= n) continue;
ll x = mod_pow(a, d, n);
if (x == 1 || x == n - 1) continue;
bool ok = false;
for (int i = 0; i < s - 1; i++) {
x = (__int128)x * x % n;
if (x == n - 1) {
ok = true;
break;
}
}
if (!ok) return false;
}
return true;
}
// 大整数质因数分解
void factorize_large(ll n, vector<ll>& res) {
if (n == 1) return;
if (is_prime(n)) {
res.push_back(n);
return;
}
ll d = pollards_rho(n);
factorize_large(d, res);
factorize_large(n / d, res);
}
// 辅助函数: 归并排序计算逆序对
ll merge_sort_inversion(const vector<int>& a, int l, int r) {
if (l >= r) return 0;
int mid = (l + r) / 2;
ll cnt = merge_sort_inversion(a, l, mid) + merge_sort_inversion(a, mid + 1, r);
vector<int> temp;
int i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) {
temp.push_back(a[i++]);
} else {
temp.push_back(a[j++]);
cnt += mid - i + 1;
}
}
while (i <= mid) temp.push_back(a[i++]);
while (j <= r) temp.push_back(a[j++]);
return cnt;
}
// 区间合并
vector<Interval> merge_intervals(vector<Interval>& intervals) {
if (intervals.empty()) return {};
sort(intervals.begin(), intervals.end());
vector<Interval> res;
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i].l <= res.back().r) {
res.back().r = max(res.back().r, intervals[i].r);
} else {
res.push_back(intervals[i]);
}
}
return res;
}
// 区间交集
vector<Interval> interval_intersection(const vector<Interval>& a, const vector<Interval>& b) {
vector<Interval> res;
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
int l = max(a[i].l, b[j].l);
int r = min(a[i].r, b[j].r);
if (l <= r) {
res.emplace_back(l, r);
}
if (a[i].r < b[j].r) {
i++;
} else {
j++;
}
}
return res;
}
// 生成全排列
void generate_permutations(vector<int>& a, int pos, vector<vector<int>>& res) {
if (pos == a.size()) {
res.push_back(a);
return;
}
for (int i = pos; i < a.size(); i++) {
swap(a[pos], a[i]);
generate_permutations(a, pos + 1, res);
swap(a[pos], a[i]);
}
}
// 生成组合
void generate_combinations(int n, int k, int start, vector<int>& curr, vector<vector<int>>& res) {
if (curr.size() == k) {
res.push_back(curr);
return;
}
for (int i = start; i <= n; i++) {
curr.push_back(i);
generate_combinations(n, k, i + 1, curr, res);
curr.pop_back();
}
}
// 检查两个矩形是否相交
bool rectangles_intersect(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
return !(x2 < x3 || x4 < x1 || y2 < y3 || y4 < y1);
}
// 计算两个矩形的交集面积
int intersection_area(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
if (!rectangles_intersect(x1, y1, x2, y2, x3, y3, x4, y4)) {
return 0;
}
int x_left = max(x1, x3);
int x_right = min(x2, x4);
int y_bottom = max(y1, y3);
int y_top = min(y2, y4);
return (x_right - x_left) * (y_top - y_bottom);
}
// 辅助函数: 计算自纪元以来的天数
int days_since_epoch(int y, int m, int d) {
int days = 0;
for (int i = 1; i < y; i++) {
days += is_leap(i) ? 366 : 365;
}
for (int i = 1; i < m; i++) {
days += is_leap(y) ? MONTH_LEAP[i-1] : MONTH[i-1];
}
days += d - 1;
return days;
}
// 检查点是否在多边形内
bool point_in_polygon(double x, double y, const vector<pdd>& poly) {
int n = poly.size();
bool inside = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
double xi = poly[i].first, yi = poly[i].second;
double xj = poly[j].first, yj = poly[j].second;
bool intersect = ((yi > y) != (yj > y)) &&
(x < (xj - xi) * (y - yi) / (yj - yi) + xi);
if (intersect) inside = !inside;
}
return inside;
}
// 快速排序实现
template<typename T>
void quick_sort(vector<T>& a, int l, int r) {
if (l >= r) return;
T pivot = a[(l + r) / 2];
int i = l, j = r;
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
quick_sort(a, l, j);
quick_sort(a, i, r);
}
// 桶排序
void bucket_sort(vector<double>& a) {
int n = a.size();
vector<vector<double>> buckets(n);
// 将元素分配到桶中
for (double x : a) {
int idx = n * x;
buckets[idx].push_back(x);
}
// 对每个桶排序
for (auto& bucket : buckets) {
sort(bucket.begin(), bucket.end());
}
// 合并桶
int idx = 0;
for (auto& bucket : buckets) {
for (double x : bucket) {
a[idx++] = x;
}
}
}
// 计算字符串哈希值
ll string_hash(const string& s, ll base, ll mod) {
ll hash = 0;
for (char c : s) {
hash = (hash * base + c) % mod;
}
return hash;
}
// 双哈希（减少碰撞概率）
pair<ll, ll> double_hash(const string& s) {
return {string_hash(s, BASE, MOD), string_hash(s, BASE2, MOD2)};
}
// 最长不重复子串
int length_of_longest_substring(const string& s) {
unordered_set<char> st;
int left = 0, max_len = 0;
for (int right = 0; right < s.size(); right++) {
while (st.count(s[right])) {
st.erase(s[left]);
left++;
}
st.insert(s[right]);
max_len = max(max_len, right - left + 1);
}
return max_len;
}
// 字符串轮转检查
bool is_rotation(const string& s1, const string& s2) {
if (s1.size() != s2.size()) return false;
return (s1 + s1).find(s2) != string::npos;
}
// 检查括号是否有效
bool is_valid_parentheses(const string& s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
st.push(c);
} else {
if (st.empty()) return false;
char top = st.top();
st.pop();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return st.empty();
}
//classes and objects
//none
//main function
m_func(mf_h){
fst;
//begin
//end
rn;
}
0 条评论
目前还没有评论...
