//#pragma GCC optimize("Ofast") #include #include #include using namespace std; using namespace std::chrono; #define int long long #define ll long long auto start_time = system_clock::now(); //@formatter:off #ifdef _DEBUG //区間削除は出来ない template struct my_pbds_tree { set s; auto begin() { return s.begin(); } auto end() { return s.end(); } auto rbegin() { return s.rbegin(); } auto rend() { return s.rend(); } auto empty() { return s.empty(); } auto size() { return s.size(); } void clear() { s.clear(); } template void insert(U v) { s.insert(v); } template void operator+=(U v) { insert(v); } template auto erase(F v) { return s.erase(v); } template auto find(U v) { return s.find(v); } template auto lower_bound(U v) { return s.lower_bound(v); } template auto upper_bound(U v) { return s.upper_bound(v); } auto find_by_order(int k) { auto it = s.begin(); for (int i = 0; i < k; i++)it++; return it; } auto order_by_key(int v) { auto it = s.begin(); int i=0; for (;it != s.end() && *it #else #define unordered_map __gnu_pbds::gp_hash_table //find_by_order(k) k番目のイテレーター //order_of_key(k) k以上が前から何番目か #define pbds(U) __gnu_pbds::tree, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> #endif struct xorshift { static uint64_t splitmix64(uint64_t x) { x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } size_t operator()(std::pair x) const { int v=((x.first) << 32) | x.second; static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(v + FIXED_RANDOM); }}; template void operator+=(__gnu_pbds::tree, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> &s, L v) { s.insert(v); } //衝突対策 #define ws wszzzz templatestruct T2 {A f;B s;C t;T2() { f = 0, s = 0, t = 0; }T2(A f, B s, C t) : f(f), s(s), t(t) {}bool operator<(const T2 &r) const { return f != r.f ? f < r.f : s != r.s ? s < r.s : t < r.t; /*return f != r.f ? f > r.f : s != r.s ?n s > r.s : t > r.t; 大きい順 */ } bool operator>(const T2 &r) const { return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; /*return f != r.f ? f > r.f : s != r.s ? s > r.s : t > r.t; 小さい順 */ } bool operator==(const T2 &r) const { return f == r.f && s == r.s && t == r.t; } bool operator!=(const T2 &r) const { return f != r.f || s != r.s || t != r.t; }}; template struct F2 { A a; B b; C c; D d; F2() { a = 0, b = 0, c = 0, d = 0; } F2(A a, B b, C c, D d) : a(a), b(b), c(c), d(d) {} bool operator<(const F2 &r) const { return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d; /* return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d;*/ } bool operator>(const F2 &r) const { return a != r.a ? a > r.a : b != r.b ? b > r.b : c != r.c ? c > r.c : d > r.d;/* return a != r.a ? a < r.a : b != r.b ? b < r.b : c != r.c ? c < r.c : d < r.d;*/ } bool operator==(const F2 &r) const { return a == r.a && b == r.b && c == r.c && d == r.d; } bool operator!=(const F2 &r) const { return a != r.a || b != r.b || c != r.c || d != r.d; } int operator[](int i) { assert(i < 4); return i == 0 ? a : i == 1 ? b : i == 2 ? c : d; }}; typedef T2 T; typedef F2 F; T mt(int a, int b, int c) {return T(a, b, c);} //@マクロ省略系 型,構造 #define double long double #define ull unsigned long long using dou = double; using itn = int; using str = string; using bo= bool; #define au auto using P = pair; using pd =pair; #define fi first #define se second #define beg begin #define rbeg rbegin #define con continue #define bre break #define brk break #define is == #define elf else if #define wh while #define maxq 1 #define minq -1 #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define MALLOC(type, len) (type*)malloc((len) * sizeof(type)) #define lam(right) [&](int& p){return p right;} //マクロ省略系 コンテナ using vi = vector; using vb = vector; using vs = vector; using vd = vector; using vc = vector; using vp = vector

; using vt = vector; #define V vector #define o_vvt(o1, o2, o3, o4, name, ...) name #define vvt0(t) V> #define vvt1(t,a) V>a #define vvt2(t,a, b) V>a(b) #define vvt3(t,a, b, c) V> a(b,V(c)) #define vvt4(t,a, b, c, d) V> a(b,V(c,d)) #define vvi(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(int,__VA_ARGS__) #define vvb(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(bool,__VA_ARGS__) #define vvs(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(string,__VA_ARGS__) #define vvd(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(double,__VA_ARGS__) #define vvc(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(char,__VA_ARGS__) #define vvp(...) o_vvt(__VA_ARGS__,vvt4,vvt3,vvt2 ,vvt1,vvt0)(P,__VA_ARGS__) template vector make_v(size_t a) { return vector(a); } template auto make_v(size_t a, Ts... ts) {return vector(ts...))>(a, make_v(ts...));} #define vni(name, ...) auto name = make_v(__VA_ARGS__) #define vnb(name, ...) auto name = make_v(__VA_ARGS__) #define vns(name, ...) auto name = make_v(__VA_ARGS__) #define vnd(name, ...) auto name = make_v(__VA_ARGS__) #define vnc(name, ...) auto name = make_v(__VA_ARGS__) #define vnp(name, ...) auto name = make_v

(__VA_ARGS__) #define PQ priority_queue, greater > #define tos to_string using mapi = map; using mapp = map; using mapd = map; using mapc = map; using maps = map; using seti = set; using setd = set; using setc = set; using sets = set; using qui = queue; #define bset bitset #define uset unordered_set #define useti unordered_set #define mset multiset #define umap unordered_map #define umapi unordered_map #define umapp unordered_map #define mmap multimap template struct pq { priority_queue, greater > q;/*小さい順*/ T su = 0; void clear() {q = priority_queue, greater >();su = 0;} void operator+=(T v) {su += v;q.push(v);} T sum() {return su;} T top() {return q.top();} void pop() {su -= q.top();q.pop();} T poll() {T ret = q.top();su -= ret;q.pop();return ret;} int size() {return q.size();}}; template struct pqg { priority_queue q;/*大きい順*/ T su = 0; void clear() {q = priority_queue();su = 0;} void operator+=(T v) {su += v;q.push(v);} T sum() {return su;} T top() {return q.top();} void pop() {su -= q.top();q.pop();} T poll() {T ret = q.top();su -= ret;q.pop();return ret;} int size() {return q.size();}}; #define pqi pq #define pqgi pqg //マクロ 繰り返し #define o_rep(o1, o2, o3, o4, name, ...) name # define rep1(n) for(int rep1i = 0,rep1lim=n; rep1i < rep1lim ; ++rep1i) # define rep2(i, n) for(int i = 0,rep2lim=n; i < rep2lim ; ++i) #define rep3(i, m, n) for(int i = m,rep3lim=n; i < rep3lim ; ++i) #define rep4(i, m, n, ad) for(int i = m,rep4lim=n; i < rep4lim ; i+= ad) #define rep(...) o_rep(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) #define rer2(i, n) for(int i = n; i >= 0 ; i--) #define rer3(i, m, n) for(int i = m,rer3lim=n; i >= rer3lim ; i--) #define rer4(i, m, n, dec) for(int i = m,rer4lim=n; i >= rer4lim ; i-=dec) #define rer(...) o_rep(__VA_ARGS__,rer4,rer3,rer2,)(__VA_ARGS__) #define reps2(i, j, n) for(int i = 0,reps2lim=n; i < reps2lim ;++i)for(int j = 0; j < reps2lim ; ++j) #define reps3(i, j, k, n) for(int i = 0,reps3lim=n; i < reps3lim ; ++i)for(int j = 0; j < reps3lim ; ++j)for(int k = 0; k < reps3lim ; ++k) #define reps4(i, j, k, l, n) for(int i = 0,reps4lim=n; i < reps4lim ; ++i)for(int j = 0; j < reps4lim ; ++j)for(int k = 0; k < reps4lim ; ++k)for(int l = 0; l < reps4lim ; ++l) #define o_reps(o1, o2, o3, o4, o5, name, ...) name #define reps(...) o_reps(__VA_ARGS__,reps4,reps3,reps2,rep2,)(__VA_ARGS__) #define repss(i, j, k, a, b, c) for(int i = 0; i < a ; ++i)for(int j = 0; j < b ; ++j)for(int k = 0; k < c ; ++k) #define fora(a, b) for(auto&& a : b) #define forg(gi, ve) for (int gi = 0,forglim = ve.size(), f, t, c; gi < forglim && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); ++gi) #define fort(gi, ve) for (int gi = 0, f, t, c; gi < ve.size() && (f = ve[gi].f, t = ve[gi].t, c = ve[gi].c, true); ++gi)if(t!=p) #define form(st, l, r) for (auto &&it = st.lower_bound(l); it != st.end() && (*it).fi < r; ++it) #define forit(st, l, r) for (auto &&it = st.lower_bound(l); it != st.end() && (*it) < r;) //マクロ 定数 #define k3 1010 #define k4 10101 #define k5 101010 #define k6 1010101 #define k7 10101010 const int inf = (int) 1e9 + 100; const ll linf = (ll) 1e18 + 100; const char infc = '{'; const string infs = "{"; const double eps = 1e-9; const double PI = 3.1415926535897932384626433832795029L; ll ma = numeric_limits::min(); ll mi = numeric_limits::max(); //マクロ省略形 関数等 #define arsz(a) (sizeof(a)/sizeof(a[0])) #define sz(a) ((int)(a).size()) #define mp make_pair #define pb pop_back #define pf push_front #define eb emplace_back #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() constexpr bool ev(int a) { return !(a & 1); } constexpr bool od(int a) { return (a & 1); } //@拡張系 こう出来るべきというもの //埋め込み 存在を意識せずに機能を増やされているもの //@formatter:on namespace std { template<> class hash> { public:size_t operator()(const std::pair &x) const { return hash()(((ll) x.first << 32) | x.second); }}; template<> class hash> { public:/*大きいllが渡されると、<<32でオーバーフローするがとりあえず問題ないと判断*/size_t operator()(const std::pair &x) const { return hash()(((ll) x.first << 32) | x.second); }}; } //@formatter:off //stream まとめ istream &operator>>(istream &iss, P &a) {iss >> a.first >> a.second;return iss;}template istream &operator>>(istream &iss, vector &vec) {for (T &x: vec) iss >> x;return iss;}template ostream &operator<<(ostream &os, pair p) {os << p.fi << " " << p.se << endl;return os;}ostream &operator<<(ostream &os, T p) { os << p.f << " " << p.s << " " << p.t; return os;}ostream &operator<<(ostream &os, F p) { os << p.a << " " << p.b << " " << p.c << " " << p.d; return os;}template ostream &operator<<(ostream &os, vector &vec) { for (int i = 0; i < vec.size(); ++i)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os;}template ostream &operator<<(ostream &os, vector > &vec) { for (int i = 0; i < vec.size(); ++i) { for (int j = 0; j < vec[0].size(); ++j) { os << vec[i][j]; } os << endl; } return os;}template ostream &operator<<(ostream &os, map &m) { for (auto &&v:m) os << v; return os;} template void resize(vector &vec, const H head) { vec.resize(head); }template void resize(vector &vec, const H &head, const T ... tail) {vec.resize(head);for (auto &v: vec)resize(v, tail...);} template bool all_of2(T &v, F f) { return f(v); } template bool all_of2(vector &v, F f) { rep(i, sz(v)) { if (!all_of2(v[i], f))return false; } return true;} template bool any_of2(T &v, F f) { return f(v); } template bool any_of2(vector &v, F f) { rep(i, sz(v)) { if (any_of2(v[i], f))return true; } return false;} template bool none_of2(T &v, F f) { return f(v); } template bool none_of2(vector &v, F f) { rep(i, sz(v)) { if (none_of2(v[i], f))return false; } return true;} template bool find_if2(T &v, F f) { return f(v); } template int find_if2(vector &v, F f) { rep(i, sz(v)) { if (find_if2(v[i], f))return i; } return sz(v);} template bool rfind_if2(T &v, F f) { return f(v); } template int rfind_if2(vector &v, F f) { rer(i, sz(v) - 1) { if (rfind_if2(v[i], f))return i; } return -1;} template bool contains(string &s, const T &v) { return s.find(v) != string::npos; } template bool contains(vector &v, const T &val) { return std::find(v.begin(), v.end(), val) != v.end(); } template bool contains_if2(vector &v, F f) { return find_if(v.begin(), v.end(), f) != v.end(); } template int count_if2(T &v, F f) { return f(v); } template int count_if2(vector &vec, F f) { int ret = 0; fora(v, vec)ret += count_if2(v, f); return ret;} template void for_each2(T &v, F f) { f(v); } template void for_each2(vector &vec, F f) { fora(v, vec)for_each2(v, f); } template int count_od(vector &a) {return count_if2(a,[](int v){return v&1 ;});} template int count_ev(vector &a) {return count_if2(a,[](int v){return !(v&1) ;});} #define all_of(a,right) all_of2(a,lam(right)) #define any_of(a,right) any_of2(a,lam(right)) #define none_of(a,right) none_of2(a,lam(right)) #define find_if(a,right) find_if2(a,lam(right)) #define rfind_if(a,right) rfind_if2(a,lam(right)) #define contains_if(a,right) contains_if2(a,lam(right)) #define count_if(a, right) count_if2(a,lam(right)) #define for_each(a, right) do{fora(v,a){v right;}}while(0) template void replace(vector &a, T key, U v) { replace(a.begin(), a.end(), key, v); } void replace(str &a, char key, str v) { if (v == "")a.erase(remove(all(a), key), a.end()); } void replace(str &a, char key, char v) { replace(all(a), key, v); } //keyと同じかどうか01で置き換える template void replace(vector &a, U k) { rep(i, sz(a)) a[i] = a[i] == k; } template void replace(vector> &a, U k) { rep(i, sz(a))rep(j, sz(a[0])) a[i][j] = a[i][j] == k; } template void replace(T &a) { replace(a, '#'); } void replace(str &a, str key, str v) {stringstream t;int kn = sz(key);std::string::size_type Pos(a.find(key));int l = 0;while (Pos != std::string::npos) {t << a.substr(l, Pos - l);t << v;l = Pos + kn;Pos = a.find(key, Pos + kn);}t << a.substr(l, sz(a) - l);a = t.str();} template bool includes(vector &a, vector &b) {vi c = a;vi d = b;sort(all(c));sort(all(d));return includes(all(c), all(d));} template bool is_permutation(vector &a, vector &b) { return is_permutation(all(a), all(b)); } template bool next_permutation(vector &a) { return next_permutation(all(a)); } void iota(vector &ve, int s, int n) {ve.resize(n);iota(all(ve), s);} vi iota(int s, int len) {vi ve(len);iota(all(ve), s);return ve;} template auto vtop(vector &a, vector &b) { assert(sz(a) == sz(b)); /*stringを0で初期化できない */ vector> res; rep(i, sz(a))res.eb(a[i], b[i]);return res;} template void ptov(vector> &p, vector &a, vector &b) { a.resize(sz(p)), b.resize(sz(p)); rep(i, sz(p))a[i] = p[i].fi, b[i] = p[i].se;} template auto vtot(vector &a, vector &b, vector &c) { assert(sz(a) == sz(b) && sz(b) == sz(c)); vector> res; rep(i, sz(a))res.eb(a[i], b[i], c[i]); return res;} template auto vtof(vector &a, vector &b, vector &c, vector &d) { assert(sz(a) == sz(b) && sz(b) == sz(c) && sz(c) == sz(d)); vector> res; rep(i, sz(a))res.eb(a[i], b[i], c[i], d[i]); return res;} enum pcomparator { fisi, fisd, fdsi, fdsd, sifi, sifd, sdfi, sdfd }; enum tcomparator { fisiti, fisitd, fisdti, fisdtd, fdsiti, fdsitd, fdsdti, fdsdtd, fitisi, fitisd, fitdsi, fitdsd, fdtisi, fdtisd, fdtdsi, fdtdsd, sifiti, sifitd, sifdti, sifdtd, sdfiti, sdfitd, sdfdti, sdfdtd, sitifi, sitifd, sitdfi, sitdfd, sdtifi, sdtifd, sdtdfi, sdfdfd, tifisi, tifisd, tifdsi, tifdsd, tdfisi, tdfisd, tdfdsi, tdfdsd, tisifi, tisifd, tisdfi, tisdfd, tdsifi, tdsifd, tdsdfi, tdsdfd}; template void sort(vector> &a, pcomparator type) { typedef pair U; if (type == fisi) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi < r.fi : l.se < r.se; }); else if (type == fisd) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi < r.fi : l.se > r.se; }); else if (type == fdsi) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi > r.fi : l.se < r.se; }); else if (type == fdsd) sort(all(a), [&](U l, U r) { return l.fi != r.fi ? l.fi > r.fi : l.se > r.se; }); else if (type == sifi) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se < r.se : l.fi < r.fi; }); else if (type == sifd) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se < r.se : l.fi > r.fi; }); else if (type == sdfi) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se > r.se : l.fi < r.fi; }); else if (type == sdfd) sort(all(a), [&](U l, U r) { return l.se != r.se ? l.se > r.se : l.fi > r.fi; });};template void sort(vector &a, pcomparator type) { if (type == fisi) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s < r.s; }); else if (type == fisd) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s > r.s; }); else if (type == fdsi) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s < r.s; }); else if (type == fdsd) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s > r.s; }); else if (type == sifi) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f < r.f; }); else if (type == sifd) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f > r.f; }); else if (type == sdfi) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f < r.f; }); else if (type == sdfd) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f > r.f; });};template void sort(vector > &a, pcomparator type) { typedef F2 U; if (type == fisi) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b < r.b; }); else if (type == fisd) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b > r.b; }); else if (type == fdsi) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b < r.b; }); else if (type == fdsd) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b > r.b; }); else if (type == sifi) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a < r.a; }); else if (type == sifd) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a > r.a; }); else if (type == sdfi) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a < r.a; }); else if (type == sdfd) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a > r.a; });};template void sort(vector &a, tcomparator type) { if (type == 0) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s < r.s : l.t < r.t; }); else if (type == 1) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s < r.s : l.t > r.t; }); else if (type == 2) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s > r.s : l.t < r.t; }); else if (type == 3) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.s != r.s ? l.s > r.s : l.t > r.t; }); else if (type == 4) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s < r.s : l.t < r.t; }); else if (type == 5) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s < r.s : l.t > r.t; }); else if (type == 6) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s > r.s : l.t < r.t; }); else if (type == 7) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.s != r.s ? l.s > r.s : l.t > r.t; }); else if (type == 8) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t < r.t : l.s < r.s; }); else if (type == 9) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t < r.t : l.s > r.s; }); else if (type == 10) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t > r.t : l.s < r.s; }); else if (type == 11) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f < r.f : l.t != r.t ? l.t > r.t : l.s > r.s; }); else if (type == 12) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t < r.t : l.s < r.s; }); else if (type == 13) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t < r.t : l.s > r.s; }); else if (type == 14) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t > r.t : l.s < r.s; }); else if (type == 15) sort(all(a), [&](U l, U r) { return l.f != r.f ? l.f > r.f : l.t != r.t ? l.t > r.t : l.s > r.s; }); else if (type == 16) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f < r.f : l.t < r.t; }); else if (type == 17) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f < r.f : l.t > r.t; }); else if (type == 18) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f > r.f : l.t < r.t; }); else if (type == 19) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.f != r.f ? l.f > r.f : l.t > r.t; }); else if (type == 20) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f < r.f : l.t < r.t; }); else if (type == 21) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f < r.f : l.t > r.t; }); else if (type == 22) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f > r.f : l.t < r.t; }); else if (type == 23) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.f != r.f ? l.f > r.f : l.t > r.t; }); else if (type == 24) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t < r.t : l.f < r.f; }); else if (type == 25) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t < r.t : l.f > r.f; }); else if (type == 26) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t > r.t : l.f < r.f; }); else if (type == 27) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s < r.s : l.t != r.t ? l.t > r.t : l.f > r.f; }); else if (type == 28) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t < r.t : l.f < r.f; }); else if (type == 29) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t < r.t : l.f > r.f; }); else if (type == 30) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t > r.t : l.f < r.f; }); else if (type == 31) sort(all(a), [&](U l, U r) { return l.s != r.s ? l.s > r.s : l.t != r.t ? l.t > r.t : l.f > r.f; }); else if (type == 32) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f < r.f : l.s < r.s; }); else if (type == 33) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f < r.f : l.s > r.s; }); else if (type == 34) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f > r.f : l.s < r.s; }); else if (type == 35) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.f != r.f ? l.f > r.f : l.s > r.s; }); else if (type == 36) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f < r.f : l.s < r.s; }); else if (type == 37) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f < r.f : l.s > r.s; }); else if (type == 38) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f > r.f : l.s < r.s; }); else if (type == 39) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.f != r.f ? l.f > r.f : l.s > r.s; }); else if (type == 40) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s < r.s : l.f < r.f; }); else if (type == 41) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s < r.s : l.f > r.f; }); else if (type == 42) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s > r.s : l.f < r.f; }); else if (type == 43) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t < r.t : l.s != r.s ? l.s > r.s : l.f > r.f; }); else if (type == 44) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s < r.s : l.f < r.f; }); else if (type == 45) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s < r.s : l.f > r.f; }); else if (type == 46) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s > r.s : l.f < r.f; }); else if (type == 47) sort(all(a), [&](U l, U r) { return l.t != r.t ? l.t > r.t : l.s != r.s ? l.s > r.s : l.f > r.f; });}template void sort(vector> &a, tcomparator type) { typedef F2 U; if (type == 0) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b < r.b : l.c < r.c; }); else if (type == 1) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b < r.b : l.c > r.c; }); else if (type == 2) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b > r.b : l.c < r.c; }); else if (type == 3) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.b != r.b ? l.b > r.b : l.c > r.c; }); else if (type == 4) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b < r.b : l.c < r.c; }); else if (type == 5) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b < r.b : l.c > r.c; }); else if (type == 6) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b > r.b : l.c < r.c; }); else if (type == 7) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.b != r.b ? l.b > r.b : l.c > r.c; }); else if (type == 8) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c < r.c : l.b < r.b; }); else if (type == 9) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c < r.c : l.b > r.b; }); else if (type == 10) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c > r.c : l.b < r.b; }); else if (type == 11) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a < r.a : l.c != r.c ? l.c > r.c : l.b > r.b; }); else if (type == 12) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c < r.c : l.b < r.b; }); else if (type == 13) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c < r.c : l.b > r.b; }); else if (type == 14) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c > r.c : l.b < r.b; }); else if (type == 15) sort(all(a), [&](U l, U r) { return l.a != r.a ? l.a > r.a : l.c != r.c ? l.c > r.c : l.b > r.b; }); else if (type == 16) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a < r.a : l.c < r.c; }); else if (type == 17) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a < r.a : l.c > r.c; }); else if (type == 18) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a > r.a : l.c < r.c; }); else if (type == 19) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.a != r.a ? l.a > r.a : l.c > r.c; }); else if (type == 20) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a < r.a : l.c < r.c; }); else if (type == 21) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a < r.a : l.c > r.c; }); else if (type == 22) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a > r.a : l.c < r.c; }); else if (type == 23) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.a != r.a ? l.a > r.a : l.c > r.c; }); else if (type == 24) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c < r.c : l.a < r.a; }); else if (type == 25) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c < r.c : l.a > r.a; }); else if (type == 26) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c > r.c : l.a < r.a; }); else if (type == 27) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b < r.b : l.c != r.c ? l.c > r.c : l.a > r.a; }); else if (type == 28) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c < r.c : l.a < r.a; }); else if (type == 29) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c < r.c : l.a > r.a; }); else if (type == 30) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c > r.c : l.a < r.a; }); else if (type == 31) sort(all(a), [&](U l, U r) { return l.b != r.b ? l.b > r.b : l.c != r.c ? l.c > r.c : l.a > r.a; }); else if (type == 32) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a < r.a : l.b < r.b; }); else if (type == 33) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a < r.a : l.b > r.b; }); else if (type == 34) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a > r.a : l.b < r.b; }); else if (type == 35) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.a != r.a ? l.a > r.a : l.b > r.b; }); else if (type == 36) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a < r.a : l.b < r.b; }); else if (type == 37) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a < r.a : l.b > r.b; }); else if (type == 38) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a > r.a : l.b < r.b; }); else if (type == 39) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.a != r.a ? l.a > r.a : l.b > r.b; }); else if (type == 40) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b < r.b : l.a < r.a; }); else if (type == 41) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b < r.b : l.a > r.a; }); else if (type == 42) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b > r.b : l.a < r.a; }); else if (type == 43) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c < r.c : l.b != r.b ? l.b > r.b : l.a > r.a; }); else if (type == 44) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b < r.b : l.a < r.a; }); else if (type == 45) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b < r.b : l.a > r.a; }); else if (type == 46) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b > r.b : l.a < r.a; }); else if (type == 47) sort(all(a), [&](U l, U r) { return l.c != r.c ? l.c > r.c : l.b != r.b ? l.b > r.b : l.a > r.a; });} void sort(string &a) { sort(all(a)); } template void sort(vector &a) { sort(all(a)); } //P l, P rで f(P) の形で渡す template void sort(vector &a, F f) { sort(all(a), [&](U l, U r) { return f(l) < f(r); }); }; template void rsort(vector &a) { sort(all(a), greater()); }; template void rsort(vector &a, F f) { sort(all(a), [&](U l, U r) { return f(l) > f(r); }); }; //F = T //例えばreturn p.fi + p.se; template void sortp(vector &a, vector &b) { auto c = vtop(a, b); sort(c); rep(i, sz(a)) a[i] = c[i].fi, b[i] = c[i].se;}template void sortp(vector &a, vector &b, F f) { auto c = vtop(a, b); sort(c, f); rep(i, sz(a)) a[i] = c[i].fi, b[i] = c[i].se;}template void rsortp(vector &a, vector &b) { auto c = vtop(a, b); rsort(c); rep(i, sz(a))a[i] = c[i].first, b[i] = c[i].second;}template void rsortp(vector &a, vector &b, F f) { auto c = vtop(a, b); rsort(c, f); rep(i, sz(a))a[i] = c[i].first, b[i] = c[i].second;} template void sortt(vector &a, vector &b, vector &c) { auto d = vtot(a, b, c); sort(d); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;} template void sortt(vector &a, vector &b, vector &c, F f) { auto d = vtot(a, b, c); sort(d, f); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;} template void rsortt(vector &a, vector &b, vector &c) { auto d = vtot(a, b, c); rsort(d); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;} template void rsortt(vector &a, vector &b, vector &c, F f) { auto d = vtot(a, b, c); rsort(d, f); rep(i, sz(a)) a[i] = d[i].f, b[i] = d[i].s, c[i] = d[i].t;} template void sortf(vector &a, vector &b, vector &c, vector &d) { auto e = vtof(a, b, c, d); sort(e); rep(i, sz(a)) a[i] = e[i].a, b[i] = e[i].b, c[i] = e[i].c, d[i] = e[i].d;} template void rsortf(vector &a, vector &b, vector &c, vector &d) { auto e = vtof(a, b, c, d); rsort(e); rep(i, sz(a)) a[i] = e[i].a, b[i] = e[i].b, c[i] = e[i].c, d[i] = e[i].d;} //sortindex 元のvectorはソートしない template vi sorti(vector &a) { auto b = a; vi ind = iota(0, sz(a)); sortp(b, ind); return ind;}/*indexの分で型が変わるためpcomparatorが必要*/template vi sorti(vector &a, pcomparator f) { auto b = a; vi ind = iota(0, sz(a)); sortp(b, ind, f); return ind;}template vi sorti(vector &a, F f) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(a[x]) < f(a[y]); }); return ind;}template vi rsorti(vector &a) { auto b = a; vi ind = iota(0, sz(a)); rsortp(b, ind); return ind;}template vi rsorti(vector &a, F f) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(a[x]) > f(a[y]); }); return ind;}template vi sortpi(vector &a, vector &b, F f) { auto c = vtop(a, b); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(c[x]) < f(c[y]); }); return ind;}template vi sortpi(vector &a, vector &b, pcomparator f) { vi ind = iota(0, sz(a)); auto c = a; auto d = b; sortt(c, d, ind, f); return ind;}template vi sortpi(vector &a, vector &b) { return sortpi(a, b, fisi); };template vi rsortpi(vector &a, vector &b, F f) { auto c = vtop(a, b); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(c[x]) > f(c[y]); }); return ind;}template vi rsortpi(vector &a, vector &b) { return sortpi(a, b, fdsd); };template vi sortti(vector &a, vector &b, vector &c, F f) { auto d = vtot(a, b, c); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(d[x]) < f(d[y]); }); return ind;}template vi sortti(vector &a, vector &b, vector &c, pcomparator f) { vi ind = iota(0, sz(a)); auto d = vtof(a, b, c, ind); sort(d, f); rep(i, sz(a))ind[i] = d[i].d; return ind;}template vi sortti(vector &a, vector &b, vector &c) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { if (a[x] == a[y]) { if (b[x] == b[y])return c[x] < c[y]; else return b[x] < b[y]; } else { return a[x] < a[y]; } }); return ind;}template vi rsortti(vector &a, vector &b, vector &c, F f) { auto d = vtot(a, b, c); vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { return f(d[x]) > f(d[y]); }); return ind;}template vi rsortti(vector &a, vector &b, vector &c) { vi ind = iota(0, sz(a)); sort(all(ind), [&](int x, int y) { if (a[x] == a[y]) { if (b[x] == b[y])return c[x] > c[y]; else return b[x] > b[y]; } else { return a[x] > a[y]; } }); return ind;} template void sort2(vector> &a) { for (int i = 0, n = a.size(); i < n; ++i)sort(a[i]); } template void rsort2(vector> &a) { for (int i = 0, n = a.size(); i < n; ++i)rsort(a[i]); } template void fill(A (&a)[N], const T &v) { rep(i, N)a[i] = v; }template void fill(A (&a)[N][O], const T &v) { rep(i, N)rep(j, O)a[i][j] = v; }template void fill(A (&a)[N][O][P], const T &v) { rep(i, N)rep(j, O)rep(k, P)a[i][j][k] = v; }template void fill(A (&a)[N][O][P][Q], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)a[i][j][k][l] = v; }template void fill(A (&a)[N][O][P][Q][R], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)a[i][j][k][l][m] = v; }template void fill(A (&a)[N][O][P][Q][R][S], const T &v) { rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)rep(n, S)a[i][j][k][l][m][n] = v; } templatevoid fill(W &xx, const T vall) { xx = vall;}templatevoid fill(vector &vecc, const T vall) { for (auto &&vx : vecc)fill(vx, vall);} templatevoid fill(vector &a,U val,vi& ind) {fora(v,ind)a[v]=val;} template A sum(A (&a)[N]) { A res = 0; rep(i, N)res += a[i]; return res;}template A sum(A (&a)[N][O]) { A res = 0; rep(i, N)rep(j, O)res += a[i][j]; return res;}template A sum(A (&a)[N][O][P]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)res += a[i][j][k]; return res;}template A sum(A (&a)[N][O][P][Q]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)rep(l, Q)res += a[i][j][k][l]; return res;}template A sum(A (&a)[N][O][P][Q][R]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)res += a[i][j][k][l][m]; return res;}template A sum(A (&a)[N][O][P][Q][R][S]) { A res = 0; rep(i, N)rep(j, O)rep(k, P)rep(l, Q)rep(m, R)rep(n, S)res += a[i][j][k][l][m][n]; return res;} //@汎用便利関数 入力 int in() {int ret;cin >> ret;return ret;} string sin() {string ret;cin >> ret;return ret;} template void in(T &head) { cin >> head; }template void in(T &head, U &... tail) {cin >> head;in(tail...);} #define o_din(o1, o2, o3, o4, name, ...) name #define din1(a) int a;cin>>a #define din2(a, b) int a,b;cin>>a>> b #define din3(a, b, c) int a,b,c;cin>>a>>b>>c #define din4(a, b, c, d) int a,b,c,d;cin>>a>>b>>c>>d #define din(...) o_din(__VA_ARGS__,din4,din3,din2 ,din1)(__VA_ARGS__) #define o_dind(o1, o2, o3, o4, name, ...) name #define din1d(a) din1(a);a-- #define din2d(a, b) din2(a,b);a--,b-- #define din3d(a, b, c) din3(a,b,c);a--,b--,c-- #define din4d(a, b, c, d) din4(a,b,c,d);a--,b--,c--,d-- #define dind(...) o_dind(__VA_ARGS__,din4d,din3d,din2d ,din1d)(__VA_ARGS__) #define o_out(o1, o2, o3, o4, name, ...) name #define out1(a) cout<void outv(vector &a,int W){ rep(i,W){ cout <void outv(vector > &a,int H,int W){ rep(h, H) { rep(w, W) { cout << a[h][w] << " "; } cout << "" << endl; }} template void outl(vector &a) { fora(v, a)cout << v << endl; } template void na(vector &a, int n) {a.resize(n);rep(i, n)cin >> a[i];} #define dna(a, n) vi a(n); rep(dnai,n) cin >> a[dnai]; template void nao(vector &a, int n) { a.resize(n + 1); a[0] = 0; rep(i, n)cin >> a[i + 1];} template void naod(vector &a, int n) { a.resize(n + 1); a[0] = 0; rep(i, n)cin >> a[i + 1],a[i+1]--;} template void nad(vector &a, int n) { a.resize(n); rep(i, n)cin >> a[i], a[i]--;} template void na2(vector &a, vector &b, int n) { a.resize(n); b.resize(n); rep(i, n)cin >> a[i] >> b[i];} #define dna2(a, b, n) vi a(n),b(n);rep(dna2i, n)cin >> a[dna2i] >> b[dna2i]; template void nao2(vector &a, vector &b, int n) { a.resize(n + 1); b.resize(n + 1); a[0] = b[0] = 0; rep(i, n)cin >> a[i + 1] >> b[i + 1];} #define dna2d(a, b, n) vi a(n),b(n);rep(dna2di, n){cin >> a[dna2di] >> b[dna2di];a[dna2di]--,b[dna2di]--;} template void na2d(vector &a, vector &b, int n) { a.resize(n); b.resize(n); rep(i, n)cin >> a[i] >> b[i], a[i]--, b[i]--;} template void na3(vector &a, vector &b, vector &c, int n) { a.resize(n); b.resize(n); c.resize(n); rep(i, n)cin >> a[i] >> b[i] >> c[i];} #define dna3(a, b, c, n) vi a(n),b(n),c(n); rep(dna3i, n)cin >> a[dna3i] >> b[dna3i] >> c[dna3i]; template void na3d(vector &a, vector &b, vector &c, int n) { a.resize(n); b.resize(n); c.resize(n); rep(i, n)cin >> a[i] >> b[i] >> c[i], a[i]--, b[i]--, c[i]--;} #define dna3d(a, b, c, n) vi a(n),b(n),c(n); rep(dna3di, n){cin >> a[dna3di] >> b[dna3di] >> c[dna3di];a[dna3di]--,b[dna3di]--,c[dna3di]--;} #define nt(a, h, w) resize(a,h,w);rep(nthi,h)rep(ntwi,w) cin >> a[nthi][ntwi]; #define ntd(a, h, w) resize(a,h,w);rep(ntdhi,h)rep(ntdwi,w) cin >> a[ntdhi][ntdwi], a[ntdhi][ntdwi]--; #define ntp(a, h, w) resize(a,h+2,w+2);fill(a,'#');rep(ntphi,1,h+1)rep(ntpwi,1,w+1) cin >> a[ntphi][ntpwi]; //デバッグ #define sp << " " << #define debugName(VariableName) # VariableName #define deb1(x) debugName(x)<<" = "< par; vector siz; vector es; int n, trees;//連結グループの数(親の種類) unionfind(int n) : n(n), trees(n) { par.resize(n); siz.resize(n); es.resize(n); for (int i = 0; i < n; i++) { par[i] = i; siz[i] = 1; } } int root(int x) { if (par[x] == x) { return x; } else { return par[x] = root(par[x]); }} void unite(int x, int y) { x = root(x); y = root(y); es[x]++; if (x == y) return; if (siz[x] > siz[y]) swap(x, y); trees--; par[x] = y; siz[y] += siz[x]; es[y] += es[x]; } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return siz[root(x)]; } int esize(int x) { return es[root(x)]; } //つながりを無向グラフと見なし、xが閉路に含まれるか判定 bool close(int x) { return esize(x) >= size(x); } /*@formatter:off*/V sets() {vvi(res, trees); umap map; rep(i, n) map[root(i)].push_back(i); int i = 0; for (auto &&p:map) { int r = p.fi; res[i].push_back(r); for (auto &&v:p.se) { if (r == v)continue; res[i].push_back(v); } ++i; } return res; } }; using bint =__int128; using u32 = unsigned; using u64 = unsigned long long; using u128 = __uint128_t; std::ostream &operator<<(std::ostream &dest, __int128_t value) { std::ostream::sentry s(dest); if (s) { __uint128_t 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;} //__int128 toi128(string &s) { __int128 ret = 0; for (int i = 0; i < s.length(); ++i) if ('0' <= s[i] && s[i] <= '9') ret = 10 * ret + s[i] - '0'; return ret;} //エラー void ole() { #ifdef _DEBUG debugline("ole");exit(0); #endif string a = "a";rep(i, 30)a += a;rep(i, 1 << 17)cout << a << endl;cout << "OLE 出力長制限超過" << endl;exit(0); } void re() { assert(0 == 1);exit(0); } void tle() { while (inf)cout << inf << endl; } //便利関数 #define unique(v) v.erase( unique(v.begin(), v.end()), v.end() ); //[i] := i番として圧縮されたものを返す vi compress(vi &a) { vi b; int len = a.size(); for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); unique(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); } int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;} vi compress(vi &a, umap &map) { vi b; int len = a.size(); for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); unique(b); for (int i = 0; i < len; ++i) { int v = a[i]; a[i] = lower_bound(all(b), a[i]) - b.begin(); map[v] = a[i]; } int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;} vi compress(vi &a, vi &r) { vi b; int len = a.size(); fora(v, a)b.push_back(v); fora(v, r)b.push_back(v); sort(b); unique(b); for (int i = 0; i < len; ++i) a[i] = lower_bound(all(b), a[i]) - b.begin(); for (int i = 0; i < sz(r); ++i) r[i] = lower_bound(all(b), r[i]) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;} vi compress(vi &a, vi &r, vi &s) { vi b; int len = a.size(); fora(v, a)b.push_back(v); fora(v, r)b.push_back(v); fora(v, s)b.push_back(v); sort(b); unique(b); for (int i = 0; i < len; ++i) a[i] = lower_bound(all(b), a[i]) - b.begin(); for (int i = 0; i < sz(r); ++i) r[i] = lower_bound(all(b), r[i]) - b.begin(); for (int i = 0; i < sz(s); ++i) r[i] = lower_bound(all(b), s[i]) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;} vi compress(V &a) { vi b; fora(vv, a)fora(v, vv)b.push_back(v); sort(b); unique(b); fora(vv, a)fora(v, vv)v = lower_bound(all(b), v) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;} vi compress(vector> &a) { vi b; fora(vvv, a)fora(vv, vvv)fora(v, vv)b.push_back(v); sort(b); unique(b); fora(vvv, a)fora(vv, vvv)fora(v, vv)v = lower_bound(all(b), v) - b.begin(); int blen = sz(b); vi ret(blen); rep(i, blen) { ret[i] = b[i]; } return ret;} void compress(int a[], int len) { vi b; for (int i = 0; i < len; ++i) { b.push_back(a[i]); } sort(b); unique(b); for (int i = 0; i < len; ++i) { a[i] = lower_bound(all(b), a[i]) - b.begin(); }} //要素が見つからなかったときに困る #define binarySearch(a, v) (binary_search(all(a),v)) #define lowerIndex(a, v) (lower_bound(all(a),v)-a.begin()) #define lowerBound(a, v) (*lower_bound(all(a),v)) #define upperIndex(a, v) (upper_bound(all(a),v)-a.begin()) #define upperBound(a, v) (*upper_bound(all(a),v)) template void fin(T s) { cout << s << endl, exit(0); } //@起動時 struct initon { initon() { cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); srand((unsigned) clock() + (unsigned) time(NULL)); }; } initonv;//@formatter:on //gra mint pr //上下左右 const string udlr = "udlr"; string UDLR = "UDLR";//x4と連動 UDLR.find('U') := x4[0] //右、上が正 constexpr int y4[] = {1, -1, 0, 0}; constexpr int x4[] = {0, 0, -1, 1}; constexpr int y8[] = {0, 1, 0, -1, -1, 1, 1, -1}; constexpr int x8[] = {1, 0, -1, 0, 1, -1, 1, -1}; int n, m, k, d, H, W, x, y, z, q; int cou; vi t, a, b, c; //vvi (s, 0, 0); vvc (ba, 0, 0); vp p; str s; struct pbds_sum { //@formatter:off template class BIT { public: int n; vector dat; BIT(int n) : n(n) { dat.assign(n, 0); } T sum(int k) { if (k >= n) k = n - 1; T ret = 0; for (int x = k - 1; x >= 0; x = (x & (x + 1)) - 1) { ret += dat[x]; } return ret; } T sum(int l, int r) { return sum(r) - sum(l); } T get(int l, int r) { return sum(r) - sum(l); } T get(int k) { return sum(k); } T operator[](int k) { assert(0 <= k && k < n); return sum(k + 1) - sum(k); } T operator()(int k) { return sum(k); } T operator()(int l, int r) { return sum(l, r); } void add(int k, T val = 1) { for (int x = k; x < n; x |= x + 1)dat[x] += val; } void update(int k, T val = 0) { add(k, -operator[](k) + val); } void del(int k) { update(k, 0); } void clear() { fill(dat, 0); } void debu() { #ifdef _DEBUG vi res; rep(i, min(10ll, n)) { res.push_back(operator[](i)); } deb(res); #endif } int lower_bound(int w) { if (w <= 0) return -1; int x = 0; int k = 1; while ((k << 1) <= n) k <<= 1; for (; k > 0; k >>= 1) { if (x + k <= n && dat[x + k - 1] < w) { w -= dat[x + k - 1]; x += k; } } return x; } }; BIT bco, bsu; umapi v_i; vi i_v; int count = 0; //クエリの順番が分かってる場合の高速化はとりあえずしない(十分高速なため) //クエリの順番が入れ替わってもいいようにする pbds_sum(vi &a) : bco(sz(a) + 3), bsu(sz(a) + 3) { vi b = a; b.push_back(linf + 100); i_v = compress(b); rep(i, sz(a)) { v_i[a[i]] = b[i]; } } pbds_sum(vi &a, vi &b) : bco(sz(a) + sz(b) + 3), bsu(sz(a) + sz(b) + 3) { vi c = a; vi d = b; c.push_back(linf + 100); d.push_back(linf + 100); i_v = compress(c, d); rep(i, sz(a)) { v_i[a[i]] = c[i]; v_i[b[i]] = d[i]; } } pbds_sum(vi &a, vi &b, vi &c) : bco(sz(a) + sz(b) + sz(c) + 3), bsu(sz(a) + sz(b) + sz(c) + 3) { vi d = a; vi e = b; vi f = c; d.push_back(linf + 100); e.push_back(linf + 100); f.push_back(linf + 100); i_v = compress(d, e, f); rep(i, sz(a)) { v_i[a[i]] = d[i]; v_i[b[i]] = e[i]; v_i[c[i]] = f[i]; } } void add(int v, int c = 1) { count += c; int ind = v_i[v]; bco.add(ind, c); bsu.add(ind, v * c); } //開区間 int sum() {return bsu.sum(inf); } int sum(int rv) { int i = (std::lower_bound(all(i_v), rv) - i_v.begin()); return bsu.sum(i); } //半開区間 l rは存在しない値でもいい int sum(int l, int r) { return sum(r) - sum(l); } //クエリ候補全ての中でのi int sum_i(int li, int ri) {return bsu.sum(ri) - bsu.sum(li);} int cou(int rv) {int i = (std::lower_bound(all(i_v), rv) - i_v.begin());return bco.sum(i);} //半開区間 l rは存在しない値でもいい int cou(int l, int r) { return cou(r) - cou(l); } int cou_i(int ri) { return bco.sum(ri); } int cou_i(int li, int ri) { return bco.sum(ri) - bco.sum(li); } //k番目の要素を返す int find_by_order(int k) { int i = bco.lower_bound(k + 1); if (i >= sz(i_v)) { cerr << "find_by_order(" << k << ") k >=" << sz(i_v) << endl; exit(0); } return i_v[i]; } //vは何番目に入るか int order_by_key(int v) { v = *std::lower_bound(all(i_v), v); int i = v_i[v]; return bco.sum(i); } //中央値を返す (左寄り) int mid() { return find_by_order((count - 1) >> 1); } int mid(int lv, int rv) { int lcou = cou(lv); int rcou = cou(rv); int wantk = lcou + ((rcou - lcou - 1) >> 1); return find_by_order(wantk); } int mid_i(int li, int ri) { int lcou = bco.sum(li ); int rcou = bco.sum(ri ); int wantk = lcou + ((rcou - lcou - 1) >> 1); return find_by_order(wantk); } int mid_i(int ri) { return mid_i(0, ri); } //全要素との 最小の差の和をかえす (全要素の中央値との差の和) int min_dis() { int mv = mid(); int mi = v_i[mv]; int lcou = bco.sum(mi); int rcou = bco.sum(mi + 1, linf); int lsum = mv * lcou - bsu.sum(mi); int rsum = bsu.sum(mi + 1, linf) - mv * rcou; return lsum + rsum; } int min_dis(int lv, int rv) { int li = (std::lower_bound(all(i_v), lv) - i_v.begin()); int ri = (std::lower_bound(all(i_v), rv) - i_v.begin()); int mv = mid_i(li, ri); int mi = v_i[mv]; int lcou = cou_i(li, mi); int rcou = cou_i(mi, ri); return mv * lcou - sum_i(li, mi) + sum_i(mi, ri) - mv * rcou; } int min_dis_i(int li, int ri) { int mv = mid_i(li, ri); int mi = v_i[mv]; int lcou = cou_i(li, mi); int rcou = cou_i(mi, ri); return mv * lcou - sum_i(li, mi) + sum_i(mi, ri) - mv * rcou; } //vをc個消す void erase(int v, int c = 1) { int ind = v_i[v]; assert(bco[ind] >= c); count -= c; bco.add(ind, -c); bsu.add(ind, v * -c); } int lower_bound(int v) { v = *std::lower_bound(all(i_v), v); int i = v_i[v]; int needc = bco.sum(i) + 1; i = bco.lower_bound(needc); return i_v[i]; } int upper_bound(int v) { return lower_bound(v + 1); }//@formatter:on }; void solve() { in(n); na(a, n); sort(a); if(all_of(a,==a[0])){ cout << 1 << endl; return; } pbds_sum sl(a); pbds_sum sr(a); rep(i, n) { sr.add(a[i]); } rep(m, 1, n) { sr.erase(a[m - 1]); sl.add(a[m - 1]); mi=min(mi,sr.min_dis() + sl.min_dis()); } cout << mi << endl; } int my(int n, vi &a) { return 0; } int sister(int n, vi &a) { int ret = 0; return ret; } signed main() { solve(); return 0; }