#include "bits/stdc++.h" using namespace std; using namespace std::chrono; typedef long long ll; #define _overload4(_1,_2,_3,_4,name,...) name #define _overload3(_1,_2,_3,name,...) name #define _overload2(_1,_2,name,...) name #define _re(n) _rep(i,n) #define _rep(i,n) _repi(i,0,n) #define _repi(i,a,b) for(ll i=a;i=a;i--) #define _rrepc(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c) #define rrep(...) _overload4(__VA_ARGS__,_rrepc,_rrepi,_rrep,_rre)(__VA_ARGS__) #define rbr(i,a) for(auto&& i:a) #define sum(...) accumulate(range(__VA_ARGS__),0) #define _range(i) (i).begin(),(i).end() #define _rangek(i,k) (i).begin(),(i).begin()+k #define range(...) _overload2(__VA_ARGS__,_rangek,_range)(__VA_ARGS__) #define LINF ll(1000000000000000000) #define MOD ll(1000000007) #define MODD ll(998244353) #define INF int(1000000007) #define Yes(i) out(i?"Yes":"No") #define YES(i) out(i?"YES":"NO") #define elif else if #define START auto start=system_clock::now() #define END auto end=system_clock::now();cerr<(end-start).count()<<" ms\n" #define INT(...) int __VA_ARGS__;in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__;in(__VA_ARGS__) #define STR(...) string __VA_ARGS__;in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__;in(__VA_ARGS__) #define DBL(...) double __VA_ARGS__;in(__VA_ARGS__) #define vec(type,name,size) vector name(size); #define VEC(type,name,size) vector name(size);in(name) #define vi(name,size,value) vectorname(size,value) #define vv(type,name,h,w,value) vector>name(h,vector(w,value)) #define pll pair struct aaa{aaa(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout< inline constexpr T gcd (T a,T b) {if(a==b)return a;else return gcd(b,(a-1)%b+1);} inline void in() {} template istream& operator >> (istream& is, vector& vec); template istream& operator >> (istream& is, array& vec); template istream& operator >> (istream& is, pair& p); template ostream& operator << (ostream& os, vector& vec); template ostream& operator << (ostream& os, pair& p); template istream& operator >> (istream& is, vector& vec){for(T& x: vec) is >> x;return is;} template istream& operator >> (istream& is, pair& p){is >> p.first;is >> p.second;return is;} template ostream& operator << (ostream& os, vector& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;} template ostream& operator << (ostream& os, pair& p){os << p.first << " " << p.second;return os;} template inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);} template inline void out(T t){cout< inline void out(Head head,Tail... tail){cout<