#include #include using namespace std; using namespace atcoder; // input template istream &operator>>(istream &is, vector &v){ for(T &in : v) is >> in; return is; } template istream &operator>>(istream &is, pair &p){ is >> p.first >> p.second; return is; } template void input(T&... a) {(cin >> ... >> a);} //output template ostream & operator<<(ostream &os, const vector &v){ for(int i = 0; i < (int)v.size(); i++) os << (i == 0 ? "" : " ") << v[i]; return os; } template ostream &operator<<(ostream &os, const pair &p){ os << p.first << " " << p.second; return os; } template ostream &operator<<(ostream &os, const map &mp){ for(auto &[key, val] : mp) os << key << ":" << val << " "; return os; } template ostream &operator<<(ostream &os, const set &st){ for(auto itr = st.begin(); itr != st.end(); itr++) os << (itr == st.begin() ? "" : " ") << *itr; return os; } template ostream &operator<<(ostream &os, const multiset &st){ for(auto itr = st.begin(); itr != st.end(); itr++) os << (itr == st.begin() ? "" : " ") << *itr; return os; } template ostream &operator<<(ostream &os, queue que){ while(!que.empty()) { os << que.front(); que.pop(); if(!que.empty()) os << " "; } return os; } template ostream &operator<<(ostream &os, stack st){ while(!st.empty()) { os << st.top(); st.pop(); if(!st.empty()) os << " "; } return os; } template ostream &operator<<(ostream &os, priority_queue pq) { while (!pq.empty()){ os << pq.top(); pq.pop(); if(!pq.empty()) os << " "; } return os; } void print() {cout << "\n";} template void print(const T& a) {cout << a << '\n';} template void print(const T& a, const Ts&... b) {cout << a; (..., (cout << ' ' << b)); cout << '\n';} #define debug(var) cout << #var << " = ";print(var); typedef long long lint; #define _overload3(_1,_2,_3,name,...) name #define _rep(i,n) repi(i,0,n) #define repi(i,a,b) for(int i=int(a);i=int(b);--i) #define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep)(__VA_ARGS__) #define all(x) (x).begin(),(x).end() templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b