#line 1 "main.cpp" /*#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops")//*/ //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #line 2 "/home/wa_haya_exe/CP_Library/C++/template.hpp" #ifndef TEMPLATE #define TEMPLATE #endif #pragma GCC diagnostic ignored "-Wunused-parameter" #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wdeprecated-copy" #include #include #include namespace VvyLw { inline void wa_haya_exe() noexcept { std::cin.tie(nullptr) -> sync_with_stdio(false); } void solve(); } // VvyLw namespace zia_qu { inline bool isdigit(const std::string &s); } std::mt19937 EhaL(std::hash()("Huitloxopetl")); std::mt19937 Random() { std::random_device seed_gen; std::mt19937 engine {seed_gen()}; return engine; } #line 2 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp" #line 5 "/home/wa_haya_exe/CP_Library/C++/core/timer.hpp" using Timer = std::chrono::system_clock::time_point; [[maybe_unused]] Timer start, stop; #if local void now(Timer &t){ t = std::chrono::system_clock::now(); } void time(const Timer &t1, const Timer &t2){ std::cerr << std::chrono::duration_cast(t2 - t1).count() << "ms\n"; } #else [[maybe_unused]] void now(Timer &t){ void(0); } [[maybe_unused]] void time(const Timer &t1, const Timer &t2){ void(0); } #endif /** * @brief タイマー */ #line 26 "/home/wa_haya_exe/CP_Library/C++/template.hpp" #define overload4(_1,_2,_3,_4,name,...) name #define overload3(_1,_2,_3,name,...) name #define rep1(n) for(ll i=0; i<(n); ++i) #define rep2(i,n) for(ll i=0; i<(n); ++i) #define rep3(i,a,b) for(ll i=(a); i<=(b); ++i) #define rep4(i,a,b,c) for(ll i=(a); i<=(b); i+=(c)) #define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define rvp1(n) for(ll i=(n); --i>=0;) #define rvp2(i,n) for(ll i=(n); --i>=0;) #define rvp3(i,a,b) for(ll i=(a); i>=(b); i--) #define rvp4(i,a,b,c) for(ll i=(a); i>=(b); i-=(c)) #define rvp(...) overload4(__VA_ARGS__,rvp4,rvp3,rvp2,rvp1)(__VA_ARGS__) #define all1(v) v.begin(),v.end() #define all2(v,a) v.begin(),v.begin()+a #define all3(v,a,b) v.begin()+a,v.begin()+b #define all(...) overload3(__VA_ARGS__,all3,all2,all1)(__VA_ARGS__) #define rall1(v) v.rbegin(),v.rend() #define rall2(v,a) v.rbegin(),v.rbegin()+a #define rall3(v,a,b) v.rbegin()+a,v.rbegin()+b #define rall(...) overload3(__VA_ARGS__,rall3,rall2,rall1)(__VA_ARGS__) #define each1(elem,v) for(auto &elem: v) #define each2(x,y,v) for(auto &[x,y]: v) #define each3(x,y,z,v) for(auto &[x,y,z]: v) #define each(...) overload4(__VA_ARGS__,each3,each2,each1)(__VA_ARGS__) #define sqrp1(n) for(ll i=0; i*i<(n); ++i) #define sqrp2(i,n) for(ll i=0; i*i<(n); ++i) #define sqrp3(i,a,b) for(ll i=(a); i*i<=(b); ++i) #define sqrp(...) overload3(__VA_ARGS__,sqrp3,sqrp2,sqrp1)(__VA_ARGS__) using ll = long long; using ld = long double; using uint = unsigned; using ul = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; #line 2 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp" #line 2 "/home/wa_haya_exe/CP_Library/C++/core/constance.hpp" #line 4 "/home/wa_haya_exe/CP_Library/C++/core/constance.hpp" #ifndef TEMPLATE using ll = long long; using ld = long double; #endif template using L = std::numeric_limits; constexpr int dx[] = {0, 0, 0, -1, 1, -1, -1, 1, 1}; constexpr int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1}; constexpr int MOD = 0x3b800001; constexpr int M0D = 1e9 + 7; constexpr int INF = 1 << 30; constexpr ll LINF = (1LL << 61) - 1; constexpr ld DINF = L::infinity(); template constexpr T LIM = L::max(); #if __cplusplus >= 202100L #include constexpr ld PI = std::numbers::pi; constexpr ld E = std::numbers::e; #else #include const ld PI = std::acos(-1); const ld E = 2.718281828459045; #endif /** * @brief 定数 */ #line 2 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp" #line 4 "/home/wa_haya_exe/CP_Library/C++/core/myvector.hpp" #ifndef TEMPLATE typedef long long ll; typedef unsigned long long ul; typedef long double ld; #endif namespace vectors { template using V = std::vector; using vi = V; using vu = V
    ; using vd = V; using vc = V; using vs = V; using vb = V; using wi = V; using wu = V; using wd = V; using wc = V; using ws = V; using wb = V; template inline V ndiv(T&& n, U&& v) noexcept { return V(std::forward(n), std::forward(v)); } template inline decltype(auto) ndiv(T&& n, Ts&&... v) noexcept { return V(v)...))>(std::forward(n), ndiv(std::forward(v)...)); } template constexpr V& operator++(V& v) noexcept { for(auto &el: v) el++; return v; } template constexpr V& operator--(V& v) noexcept { for(auto &el: v) el--; return v; } template constexpr V& operator+=(V& v, const U x) noexcept { for(auto &el: v) el+=x; return v; } template constexpr V& operator-=(V& v, const U x) noexcept { for(auto &el: v) el-=x; return v; } template constexpr V& operator*=(V& v, const U x) noexcept { for(auto &el: v) el*=x; return v; } template constexpr V& operator/=(V& v, const U x) noexcept { for(auto &el: v) el/=x; return v; } template constexpr V& operator%=(V& v, const U x) noexcept { for(auto &el: v) el%=x; return v; } template constexpr V operator+(const V& v, const U x) noexcept { V res = v; res+=x; return res; } template constexpr V operator-(const V& v, const U x) noexcept { V res = v; res-=x; return res; } template constexpr V operator*(const V& v, const U x) noexcept { V res = v; res*=x; return res; } template constexpr V operator/(const V& v, const U x) noexcept { V res = v; res/=x; return res; } template constexpr V operator%(const V& v, const U x) noexcept { V res = v; res%=x; return res; } } // vectors #line 10 "/home/wa_haya_exe/CP_Library/C++/core/mypair.hpp" namespace pairs { template using P = std::pair; template using PP = P; using pi = PP; using pd = PP; using pc = PP; using ps = PP; template constexpr PP operator+(const PP& a, const PP& b) noexcept { return {a.first + b.first, a.second + b.second}; } template constexpr PP operator-(const PP& a, const PP& b) noexcept { return {a.first - b.first, a.second - b.second}; } template constexpr PP operator-(const PP& a) noexcept { return {-a.first, -a.second}; } template constexpr PP operator*(const PP& a, const U& b) noexcept { return {a.first * b, a.second * b}; } template constexpr PP operator/(const PP& a, const U& b) noexcept { return {a.first / b, a.second / b}; } template constexpr PP& operator+=(PP& a, const PP& b) noexcept { return a = a + b; } template constexpr PP& operator-=(PP& a, const PP& b) noexcept { return a = a - b; } template constexpr PP& operator*=(PP& a, const U& b) noexcept { return a = a * b; } template PP& operator/=(PP& a, const U& b) noexcept { return a = a / b; } template constexpr bool operator==(const PP &p, const PP &q) noexcept { return p.first==q.first && p.second==q.second; } template constexpr bool operator!=(const PP &p, const PP &q) noexcept { return !(p==q); } template constexpr bool operator<(const PP &p, const PP &q) noexcept { if(p.first==q.first) return p.second constexpr bool operator<=(const PP &p, const PP &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first constexpr bool operator>(const PP &p, const PP &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; } template constexpr bool operator>=(const PP &p, const PP &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; } template constexpr bool operator==(const P &p, const P &q) noexcept { return p.first==q.first && p.second==q.second; } template constexpr bool operator!=(const P &p, const P &q) noexcept { return !(p==q); } template constexpr bool operator<(const P &p, const P &q) noexcept { if(p.first==q.first) return p.second constexpr bool operator<=(const P &p, const P &q) noexcept { if(p.first==q.first) return p.second<=q.second; return p.first constexpr bool operator>(const P &p, const P &q) noexcept { if(p.first==q.first) return p.second>q.second; return p.first>q.first; } template constexpr bool operator>=(const P &p, const P &q) noexcept { if(p.first==q.first) return p.second>=q.second; return p.first>q.first; } template inline PP rotate(const PP& a){ return {-a.second, a.first}; } // 90 degree ccw template inline pd rotate(const PP& a, const int ang) { assert(0<=ang && ang<360); const ld rad=PI*ang/180; return {a.first*std::cos(rad)-a.second*std::sin(rad), a.first*std::sin(rad)+a.second*std::cos(rad)}; } template inline T dot(const PP& a, const PP& b){ return a.first * b.first + a.second * b.second; } template inline T cross(const PP& a, const PP& b){ return dot(rotate(a), b); } template inline T square(const PP& a){ return dot(a, a); } template inline ld grad(const PP& a){ assert(a.first); return 1.0L * a.second / a.first; } template inline ld abs(const PP& a){ return std::hypotl(a.first, a.second); } template inline T lcm(const PP& a){ return std::lcm(a.first, a.second); } template inline T gcd(const PP& a){ return std::gcd(a.first, a.second); } template inline PP extgcd(const PP &p) { T x=1,y=0,t1=0,t2=0,t3=1,a,b; std::tie(a,b)=p; while(b) { t1=a/b,a-=t1*b; std::swap(a,b); x-=t1*t2; std::swap(x,t2); y-=t1*t3; std::swap(y,t3); } return {x,y}; } template inline PP normalize(PP a) { if(a == PP{}) return a; a /= gcd(a); if(a < PP{}) a = -a; return a; } template inline P swap(const P &p){ P ret={p.second,p.first}; return ret; } template inline vectors::V> swap(const vectors::V> &vp) { vectors::V> ret; for(const auto &el: vp) ret.emplace_back(swap(el)); return ret; } template inline vectors::V first(const vectors::V> &vp) { vectors::V res; for(const auto &el: vp) res.emplace_back(el.first); return res; } template inline vectors::V second(const vectors::V> &vp) { vectors::V res; for(const auto &el: vp) res.emplace_back(el.second); return res; } } // pairs #line 64 "/home/wa_haya_exe/CP_Library/C++/template.hpp" using namespace vectors; using namespace pairs; template using ti = std::array; using tri = ti<3>; template using pq = std::priority_queue; template using pqr = std::priority_queue,std::greater>; template using Tree = __gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template using TREE = __gnu_pbds::tree,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>; template inline bool chmax(T& a, const U& b){ if(a inline bool chmin(T& a, const U& b){ if(a>b){ a=b; return 1; } return 0; } template inline bool overflow_if_add(const T a, const U b){ return (LIM-a) inline bool overflow_if_mul(const T a, const U b){ return (LIM/a) std::istream& operator>>(std::istream &is, pairs::P &p){ is >> p.first >> p.second; return is; } template std::istream& operator>>(std::istream &is, std::array &a){ for(auto &el: a) is >> el; return is; } template std::istream& operator>>(std::istream &is, vectors::V &v){ for(auto &el: v) is >> el; return is; } template std::istream& operator>>(std::istream &is, std::deque &dq){ for(auto &el: dq) is >> el; return is; } template inline bool in(T& x){ std::cin >> x; return 1; } template inline bool in(Head& head, Tail&... tail){ in(head); in(tail...); return 1; } inline i128 to_i128(const std::string &s) { assert(zia_qu::isdigit(s)); bool neg=s.front()=='-'; i128 ret = 0; for(const auto &el: s) { if(neg) { neg=0; continue; } ret = 10 * ret + el - '0'; } if(s.front()=='-') ret=-ret; return ret; } #define INT(...) int __VA_ARGS__; in(__VA_ARGS__) #define LL(...) ll __VA_ARGS__; in(__VA_ARGS__) #define UL(...) ul __VA_ARGS__; in(__VA_ARGS__) #define LD(...) ld __VA_ARGS__; in(__VA_ARGS__) #define CHR(...) char __VA_ARGS__; in(__VA_ARGS__) #define STR(...) std::string __VA_ARGS__; in(__VA_ARGS__) #define VEC(type,name,size) vectors::V name(size); in(name) #define WEC(type,name,h,w) vectors::V> name(h,vectors::V(w)); in(name) } // IO /** * @brief 入力 */ #line 2 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp" #line 9 "/home/wa_haya_exe/CP_Library/C++/core/io/output.hpp" #ifndef TEMPLATE using i128 = __int128_t; using u128 = __uint128_t; #endif namespace IO { std::ostream &operator<<(std::ostream &dest, const i128 &value) { std::ostream::sentry s(dest); if(s) { u128 tmp = value < 0 ? -value : value; char buffer[128]; char *d = std::end(buffer); do { --d; *d = "0123456789"[tmp % 10]; tmp /= 10; } while(tmp != 0); if(value < 0) { --d; *d = '-'; } int len = std::end(buffer) - d; if(dest.rdbuf() -> sputn(d, len) != len) { dest.setstate(std::ios_base::badbit); } } return dest; } template std::ostream& operator<<(std::ostream &os, const std::pair &p){ os << p.first << ' ' << p.second; return os; } template std::ostream& operator<<(std::ostream &os, const std::array &a){ if(a.size()){ os << a.front(); for(auto i=a.begin(); ++i!=a.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::vector &v){ if(v.size()){ os << v.front(); for(auto i=v.begin(); ++i!=v.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::map &m){ if(m.size()){ os << m.begin()->first << ' ' << m.begin()->second; for(auto i=m.begin(); ++i!=m.end();){ os << '\n' << i->first << ' ' << i->second; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::set &st){ if(st.size()){ os << *st.begin(); for(auto i=st.begin(); ++i!=st.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::multiset &ms){ if(ms.size()){ os << *ms.begin(); for(auto i=ms.begin(); ++i!=ms.end();){ os << ' ' << *i; } } return os; } template std::ostream& operator<<(std::ostream &os, const std::deque &dq){ if(dq.size()){ os << dq.front(); for(auto i=dq.begin(); ++i!=dq.end();){ os << ' ' << *i; } } return os; } inline void out(){ std::cout << '\n'; } template inline void out(const T& x){ std::cout << x << '\n'; if(flush) std::cout.flush(); } template inline void out(const Head& head, const Tail&... tail){ std::cout << head << ' '; out(tail...); } template inline void vout(const T& v){ std::cout << v << '\n'; if(flush) std::cout.flush(); } template inline void vout(const std::vector& v){ for(const auto &el: v) std::cout << el << '\n'; if(flush) std::cout.flush(); } template inline void vout(const Head& head, const Tail&... tail){ std::cout << head << '\n'; vout(tail...); } #define fin(...) do{ out(__VA_ARGS__); return; }while(false) } // IO #if local //https://gist.github.com/naskya/1e5e5cd269cfe16a76988378a60e2ca3 #include #else #define dump(...) static_cast(0) #endif /** * @brief 出力 */ #line 83 "/home/wa_haya_exe/CP_Library/C++/template.hpp" using namespace IO; namespace zia_qu { #define elif else if #define eid(el,v) size_t(&el-&v[0]) #define bif(bit,tar) if(((bit)>>(tar))&1) #define nxp(x) std::next_permutation(all(x)) #define prp(x) std::prev_permutation(all(x)) #define strpl(s,a,b) std::regex_replace(s,std::regex(a),b) #define rgxsr(s,rgx) std::regex_search(s,std::regex(rgx)) inline void YES(const bool ok=1){ out(ok?"YES":"NO"); } inline void NO(const bool ok=1){ YES(!ok); } inline void Yes(const bool ok=1){ out(ok?"Yes":"No"); } inline void No(const bool ok=1){ Yes(!ok); } inline void yes(const bool ok=1){ out(ok?"yes":"no"); } inline void no(const bool ok=1){ yes(!ok); } template inline T sqr(const T x){ return x*x; } template inline T cub(const T x){ return x*x*x; } template inline T mod(T x, const T m) { x %= m; return x < 0 ? x + m : x; } template inline T pow(T a, T b, const T mod=0) { T res=1; if(mod) { res%=mod; a%=mod; } while(b>0) { if(b&1) res*=a; if(mod) res%=mod; a*=a; if(mod) a%=mod; b>>=1; } return res; } inline ll ceil(const ld x, const ll m){ return std::ceil(x/m); } inline ld round(const ld x, const ll m, const short fx=0){ if(!fx) return std::round(x/m); const ul y=pow
      (10,fx); return std::round((x*y)/m)/y; } inline ld log(const ll x, const ld base=2){ return std::log2(x)/std::log2(base); } inline int bitdigit(const ll x){ return 64-__builtin_clzll(x); } inline int popcnt(const ll x){ return __builtin_popcountll(x); } inline int fione(const ll x){ return __builtin_ffsll(x); } inline int zrcnt(const ll x){ return __builtin_ctzll(x); } template inline bool scope(const T a, const T x, const T b){ return a <= x && x <= b; } inline bool isupper(const char c){ return std::isupper(c); } inline bool isupper(const std::string &s){ bool ok=1; each(el,s) ok&=isupper(el); return ok; } inline bool islower(const char c){ return std::islower(c); } inline bool islower(const std::string &s){ bool ok=1; each(el,s) ok&=islower(el); return ok; } inline bool isalpha(const char c){ return std::isalpha(c); } inline bool isalpha(const std::string &s){ bool ok=1; each(el,s) ok&=isalpha(el); return ok; } inline bool isdigit(const char c){ return std::isdigit(c); } inline bool isdigit(const std::string &s){ bool ok=1, neg=s.front()=='-'; each(el,s){ if(neg){ neg=0; continue; } ok&=isdigit(el); } return ok; } inline bool isalnum(const char c){ return std::isalnum(c); } inline bool isalnum(const std::string &s){ bool ok=1; each(el,s) ok&=isalnum(el); return ok; } inline bool isspace(const char c){ return std::isspace(c); } inline bool isspace(const std::string &s){ bool ok=1; each(el,s) ok&=isspace(el); return ok; } inline bool ispunct(const char c){ return std::ispunct(c); } inline bool ispunct(const std::string &s){ bool ok=1; each(el,s) ok&=ispunct(el); return ok; } inline bool isprint(const char c){ return std::isprint(c); } inline bool isprint(const std::string &s){ bool ok=1; each(el,s) ok&=isprint(el); return ok; } inline ll strins(std::string &s, const int id, const std::string &t){ s.insert(id,t); return s.size(); } inline std::string toupper(std::string s){ each(c,s) c=std::toupper(c); return s; } inline std::string tolower(std::string s){ each(c,s) c=std::tolower(c); return s; } inline vi ten_to_adic(ll n, const short base) { if(n==0) { return {0}; } vi res; while(n) { res.emplace_back(n%base); n/=base; } return res; } inline ll adic_to_ten(const vi &v, const short base) { ll res=0; each(el,v) { res+=pow(base,eid(el,v))*el; } return res; } inline std::string to_hex(const ll x, const bool upper = false) { std::stringstream ss; ss << std::hex << x; std::string s = ss.str(); if(upper) s=toupper(s); return s; } inline std::string to_oct(const ll x) { std::stringstream s; s << std::oct <(x); std::string s=ss.str(); std::reverse(all(s)); s.resize(ten_to_adic(x,2).size()); std::reverse(all(s)); return s; } inline ll to_ten(const std::string &s, const short base){ return std::stoll(s,nullptr,base); } template constexpr ul sygcd(const Ts... a) noexcept { std::vector v=std::initializer_list>{a...}; ul g=0; each(el,v) g=std::gcd(g,el); return g; } template constexpr ul sylcm(const Ts... a) noexcept { std::vector v=std::initializer_list>{a...}; ul l=1; each(el,v) l=std::lcm(l,el); return l; } template constexpr auto symin(const Ts... a) noexcept { return std::min(std::initializer_list>{a...}); } template constexpr auto symax(const Ts... a) noexcept { return std::max(std::initializer_list>{a...}); } template inline V kyl(const std::map &m, const U val) { V keys; for(auto it=m.cbegin(); it!=m.cend(); ++it) { if(it->second==val) keys.emplace_back(it->first); } return keys; } template inline K kymin(const std::map &m){ return m.begin()->first; } template inline K kymax(const std::map &m){ return m.rbegin()->first; } template inline V kymin_v(const std::map &m){ return m.begin()->second; } template inline V kymax_v(const std::map &m){ return m.rbegin()->second; } template inline V vlmin(const std::map &m){ const auto pr = *std::min_element(all(m),[](P const &x, P const &y){ return x.second < y.second; }); return pr.second; } template inline V vlmax(const std::map &m){ const auto pr = *std::max_element(all(m),[](P const &x, P const &y){ return x.second < y.second; }); return pr.second; } template inline K vlmin_k(const std::map &m){ const auto pr = *std::min_element(all(m),[](P const &x, P const &y){ return x.second < y.second; }); return pr.first; } template inline K vlmax_k(const std::map &m){ const auto pr = *std::max_element(all(m),[](P const &x, P const &y){ return x.second < y.second; }); return pr.first; } } // zia qu namespace Lady_sANDy { template inline void rev(T& v){ std::reverse(all(v)); } template inline void rev(T& v, const int a, const int b){ std::reverse(all(v,a,b+1)); } template inline T revd(const T& v){ auto c=v; rev(c); return c; } template inline T revd(const T& v, const int a, const int b){ auto c=v; rev(c,a,b); return c; } template inline void Sort(T& v){ std::sort(all(v)); } template inline void Sort(T& v, const int a, const int b){ std::sort(all(v,a,b+1)); } template inline T sorted(const T& v){ auto c=v; Sort(c); return c; } template inline T sorted(const T& v, const int a, const int b){ auto c=v; Sort(c,a,b); return c; } template inline void Sortt(T& v){ std::sort(rall(v)); } template inline void Sortt(T& v, const int a, const int b){ std::sort(rall(v,v.size()-b-1,v.size()-a)); } template inline T Sorted(const T& v){ auto c=v; Sortt(c); return c; } template inline T Sorted(const T& v, const int a, const int b){ auto c=v; Sortt(c,a,b); return c; } template inline void Sorth(T& v){ std::make_heap(all(v)); std::sort_heap(all(v)); } template inline T mrg(const T& a, const T& b){ T res; std::merge(all(a),all(b),std::back_inserter(res)); return res; } template inline T Min(const V& v){ return *std::min_element(all(v)); } template inline T Min(const V& v, const int a, const int b){ return *std::min_element(all(v,a,b+1)); } template inline T Max(const V& v){ return *std::max_element(all(v)); } template inline T Max(const V& v, const int a, const int b){ return *std::max_element(all(v,a,b+1)); } template inline int Min_i(const T& v){ return std::min_element(all(v))-v.begin(); } template inline int Max_i(const T& v){ return std::max_element(all(v))-v.begin(); } template inline int LB(const T& v, const U x){ return std::lower_bound(all(v),x)-v.begin(); } template inline int UB(const T& v, const U x){ return std::upper_bound(all(v),x)-v.begin(); } template inline bool BS(const T& v, const U x){ return std::binary_search(all(v),x); } template inline bool BS(const T& v, const U x, const Boolean &fn){ return std::binary_search(all(v),x,fn); } template inline bool All(const T& v, const Boolean &fn){ return std::all_of(all(v),fn); } template inline bool Exist(const T& v, const Boolean &fn){ return std::any_of(all(v),fn); } template inline int pt(T& v, const Boolean &fn){ auto p=std::partition(all(v),fn); return p-v.begin(); } template inline int ptp(const T& v, const Boolean &fn){ return std::partition_point(all(v),fn)-v.begin(); } template inline int fnd(const T& v, const U x){ auto itr=std::find(all(v),x); return itr!=v.end()?itr-v.begin():-1; } template inline int src(const T& s, const T& t){ auto itr=std::search(all(s),all(t)); return itr!=s.end()?itr-s.begin():-1; } template inline void rpl(T& v, const U fn, const U r){ std::replace(all(v),fn,r); } template inline void rplif(T& v, const Boolean &fn, const U r){ std::replace_if(all(v),fn,r); } template inline ul cntif(const T& v, const Boolean &fn){ return std::count_if(all(v),fn); } template inline T Count(V& v, ll x){ if(!std::is_sorted(all(v))) Sort(v); return UB(v,x)-LB(v,x); } template inline T IP(const V& v, const V& u, T init){ return std::inner_product(all(v),u.begin(),init); } inline vi iot(int n, ll init=0){ vi a(n); std::iota(all(a),init); return a; } template inline V trans(const V& v, const F &fn){ V res; std::transform(all(v),std::back_inserter(res),fn); return res; } template inline int ers(T& v, const U x){ v.erase(std::remove(all(v),x),v.end()); return v.size(); } template int ersif(T& v, const Boolean &fn){ v.erase(std::remove_if(all(v),fn),v.end()); return v.size(); } template inline int unq(T& v){ if(!std::is_sorted(all(v))) Sort(v); v.erase(unique(all(v)),v.end()); return v.size(); } template inline T cp(const T& v){ T res; copy(all(v),back_inserter(res)); return res; } template inline T cp(const T& v, const int a, const int b){ T res; std::copy(all(v,a,b),std::back_inserter(res)); return res; } template inline void rtt(T& s, const int idx){ const int id=zia_qu::mod(idx,s.size()); std::rotate(all(s,id),s.end()); } template inline void rtt(T& s, const int a, const int b, const int c){ std::rotate(all(s,a,b),s.end()-c); } template inline T setdif(const T& s, const T& t){ assert(std::is_sorted(all(s))&&std::is_sorted(all(t))); T res; std::set_difference(all(s),all(t),std::inserter(res,std::end(res))); return res; } template inline T setsum(const T& s, const T& t){ assert(std::is_sorted(all(s))&&std::is_sorted(all(t))); T res; std::set_union(all(s),all(t),std::inserter(res,std::end(res))); return res; } template inline T setmul(const T& s, const T& t){ assert(std::is_sorted(all(s))&&std::is_sorted(all(t))); T res; std::set_intersection(all(s),all(t),std::inserter(res,std::end(res))); return res; } template inline V adf(const V& v){ V a; std::adjacent_difference(all(v),std::back_inserter(a)); rtt(a,1); a.pop_back(); return a; } template inline V isum(const V &v, const F &fn){ V s{0}; std::inclusive_scan(all(v),std::back_inserter(s),fn); return s; } template inline V rext(const V& v, const int size){ V res; std::sample(all(v),std::back_inserter(res),size,Random()); return res; } template inline T rext(const V& v){ V res; std::sample(all(v),std::back_inserter(res),1,Random()); return res.front(); } template inline ll vsum(const T &v){ return std::accumulate(all(v),0LL); } template inline ll vsum(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),0LL); } template inline ld vdsum(const T &v){ return std::accumulate(all(v),0.0L); } template inline ld vdsum(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),0.0L); } template inline ll vmul(const T &v){ return std::accumulate(all(v),1LL,[](ll acc,ll i){ return acc*i; }); } template inline ll vmul(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),1LL,[](ll acc,ll i){ return acc*i; }); } template inline ld vdmul(const T &v){ return std::accumulate(all(v),1.0L,[](ll acc,ll i){ return acc*i; }); } template inline ld vdmul(const T &v, ll a, ll b){ return std::accumulate(all(v,a,b),1.0L,[](ll acc,ll i){ return acc*i; }); } } // Lady s&y #line 2 "/home/wa_haya_exe/CP_Library/C++/math/divisor.hpp" #line 5 "/home/wa_haya_exe/CP_Library/C++/math/divisor.hpp" namespace Heileden { template inline std::vector div(const T n) { std::vector d; for(int64_t i = 1; i * i <= n; ++i) { if(n % i == 0) { d.emplace_back(i); if(i * i != n) { d.emplace_back(n / i); } } } std::ranges::sort(d); return d; } } /** * @brief 約数列挙 */ #line 2 "/home/wa_haya_exe/CP_Library/C++/math/primefactor.hpp" #line 5 "/home/wa_haya_exe/CP_Library/C++/math/primefactor.hpp" namespace Heileden { template inline std::vector> prmfct(T n) { std::vector> res; for(int64_t i = 2; i * i <= n; ++i) { if(n % i != 0) { continue; } int tmp = 0; while(n % i == 0) { tmp++; n /= i; } res.emplace_back(i, tmp); } if(n != 1) { res.emplace_back(n, 1); } return res; } } /** * @brief 素因数分解 */ #line 2 "/home/wa_haya_exe/CP_Library/C++/math/primetable.hpp" #line 4 "/home/wa_haya_exe/CP_Library/C++/math/primetable.hpp" namespace Heileden { struct p_table { std::vector SoE; p_table(const int n): SoE(n + 1, 1) { SoE[0] = SoE[1] = 0; for(int64_t i = 2; i <= n; ++i) { if(!SoE[i]) { continue; } for(int64_t j = i * i; j <= n; j += i) { SoE[j] = 0; } } } std::vector get() { std::vector p; for(size_t i = 2; i < SoE.size(); ++i) { if(SoE[i]) { p.emplace_back(i); } } return p; } }; } /** * @brief Sieve of Eratosthenes */ #line 2 "/home/wa_haya_exe/CP_Library/C++/math/primefactortable.hpp" #line 6 "/home/wa_haya_exe/CP_Library/C++/math/primefactortable.hpp" namespace Heileden { struct p_fact { std::vector spf; p_fact(const int n): spf(n + 1){ std::iota(spf.begin(), spf.end(), 0); for(int64_t i = 2; i * i <= n; ++i) { if(spf[i] == i) { for(int64_t j = i * i; j <= n; j += i) { if(spf[j]==j) { spf[j]=i; } } } } } std::map get(int n) { std::map m; while(n != 1) { m[spf[n]]++; n /= spf[n]; } return m; } }; } /** * @brief 素因数分解テーブル */ #line 2 "/home/wa_haya_exe/CP_Library/C++/math/psum/psum.hpp" #line 6 "/home/wa_haya_exe/CP_Library/C++/math/psum/psum.hpp" namespace Heileden { template struct psum { private: int n; bool not_built; vectors::vi s; public: psum(const vectors::V& v): s{0LL} { std::partial_sum(v.cbegin(), v.cend(), std::back_inserter(s)); } psum(const int n): n(n), not_built(true), s(n + 1){} vectors::vi get() const { return s; } // [l, r] ll sum(const int l, const int r) const { return s[r] - s[l]; } void add(const int l, const int r, const ll x) { assert(not_built); s[l] += x; s[r] -= x; } vectors::vi build() { assert(not_built); vectors::vi res; std::partial_sum(s.cbegin(), s.cend(), std::back_inserter(res)); not_built = false; res.resize(n); return res; } }; } /** * @brief 累積和 */ #line 2 "/home/wa_haya_exe/CP_Library/C++/math/kthrooti.hpp" #line 4 "/home/wa_haya_exe/CP_Library/C++/math/kthrooti.hpp" #ifndef TEMPLATE typedef unsigned long long ul; template inline bool overflow_if_mul(const T a, const U b){ return (std::numeric_limits::max()/a)= 0;) { if(chk(ret|(1U< inline T bins(T ok, T ng, const Boolean &fn, const ld eps = 1) { while(std::abs(ok-ng)>eps) { T mid=(ok+ng)/2; (fn(mid)?ok:ng) = mid; } return ok; } template inline V press(const V& v) { V res,cp=v; Lady_sANDy::unq(cp); each(el,v) res.emplace_back(Lady_sANDy::LB(cp,el)); return res; } template inline V press(V &c1, V &c2) { V res; const int n = c1.size(); rep(n) { for(T d = 0; d < 1; d++) { T tc1 = c1[i]+d; T tc2 = c2[i]+d; res.emplace_back(tc1); res.emplace_back(tc2); } } Lady_sANDy::unq(res); rep(n) { c1[i]=Lady_sANDy::LB(res,c1[i]); c2[i]=Lady_sANDy::LB(res,c2[i]); } return res; } inline vs rtt(const vs &s) { const int h=s.size(), w=s.front().size(); vs t(w,std::string(h,{})); rep(h) rep(j,w) t[j][i]=s[i][j]; rep(w) Lady_sANDy::rev(t[i]); return t; } template inline V> rtt(const V>& v) { const int h=v.size(), w=v.front().size(); V> res(w,V(h)); rep(h) rep(j,w) res[j][i]=v[i][j]; rep(w) Lady_sANDy::rev(res[i]); return res; } template inline T factor(T n, const T mod=0) { T res=1; while(n>0) { res*=n--; if(mod) res%=mod; } return res; } template inline T perm(T n, const T r, const T mod=0) { const T tmp=n; T res=1; while(n>tmp-r) { res*=n--; if(mod) res%=mod; } return res; } template inline T binom(T n, const T r, const T mod=0) { if(r < 0 || n < r) return 0; T res = 1; rep(i,1,r) { res*=n--; if(mod) res%=mod; res/=i; if(mod) res%=mod; } return res; } inline bool is_prime(const ul n) { if(n==1) return 0; sqrp(i,2,n) if(n%i==0) return 0; return 1; } inline bool is_int(const ld n){ return n == std::floor(n); } inline bool is_sqr(const ll n){ return is_int(std::sqrt(n)); } } // Heileden /** * @brief テンプレート * @docs docs/template.md */ #line 6 "main.cpp" using namespace std; using namespace zia_qu; using namespace Lady_sANDy; using namespace Heileden; int main() { VvyLw::wa_haya_exe(); now(start); int T=1; //in(T); while(T--) VvyLw::solve(); now(stop); time(start, stop); } // -------------------------------------------------------------------------------------------------------------- void VvyLw::solve() { LL(n,m,w); VEC(int,a,n); VEC(int,b,m); VEC(int,c,m); Sortt(a); psum p(a); const auto s=p.get(); ll ans=0; rep(1<