#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #define INF 1LL << 60 #define MOD 998244353 #define MMOD 1000000007 using ll = long long; using ull = unsigned long long; using ld = long double; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vc<vvl>; using vs = vc<string>; using vvs = vv<string>; using vb = vc<bool>; using vvb = vv<bool>; using vvvb = vc<vvb>; using lP = pair<ll, ll>; using sP = pair<string, string>; using vlP = vc<lP>; using vsP = vc<sP>; using RLEs = vc<pair<char, ll>>; #define rep(i,n) for(ll i = 0; i < (n); ++i) #define rrep(i,n) for(ll i = 1; i <= (n); ++i) #define drep(i,n) for(ll i = (n)-1; i >= 0; --i) #define nfor(i,s,n) for(ll i=s;i<n;++i) #define nall(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define YES cout<<"Yes"<<endl #define NO cout<<"No"<<endl #define OK cout<<"ok"<<endl #define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;} #define dame cout<<-1<<endl #define LAST(i, n) (i+1==n?"\n":" ") #define RLAST(i, n) (i==n?"\n":" ") const double PI = acos(0) * 2; #define RAD(d) (d * PI / 180.) #define DEG(r) (r * 180. / PI) string atoz = "abcdefghijklmnopqrstuvwxyz"; string TA = "Takahashi"; struct Edge { ll to; ll weight; Edge(ll t, ll w) : to(t), weight(w) { } }; using Graph = vector<vector<Edge>>; //////////////////////////////////////////////////////////////////////////////////////////////// struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); }; } fast_ios_; template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;} template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;} template<class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); } template<class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); } template<class T> void sort_unique(std::vector<T> &vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());} //////////////////////////////////////////////////////////////////////////////////////////////// //maths ll floor(ll n, ll a){ return n / a - (n % a < 0); } ll ceil(ll n, ll a){ return n / a + ((n ^ a) >= 0) * (n % a != 0); } //xとyの最大公約数 ll gcd(ll x, ll y){ if(x % y == 0)return y; else return gcd(y, x % y); } //xとyの最小公倍数 ll lcm(ll x, ll y){ return x / gcd(x, y) * y; } ll log2_ceil(ll x){ ll val = 1; while((1LL << val) <= x)++val; return val; } //xの逆元 ll mod_inv(ll x, ll mod){ ll b = mod, u = 1, v = 0; while(b){ ll t = x / b; x -= t * b; swap(x, b); u -= t * v; swap(u, v); } u %= mod; if(u < 0)u += mod; return u; } ll pow_ll(ll x, ll n){ ll ans = 1; while(n > 0){ if(n & 1)ans *= x; x *= x; n >>= 1; } return ans; } ll pow_ll(ll x, ll n, ll mod){ ll ans = 1; while(n > 0){ if(n & 1)ans = ans * x % mod; x = x * x % mod; n >>= 1; } return ans; } ll comb(ll n, ll k, ll mod){ ll x = 1; for(ll i = n - k + 1; i <= n; ++i)x = x * i % mod; ll y = 1; for(ll i = 1; i <= k; ++i)y = y * i % mod; y = pow_ll(y, mod - 2, mod); return x * y % mod; } ll mod_n(ll N, ll div){ if(N == abs(N))return N % div; else return (N % div + div) % div; } //not_sqrt ll dist(ll sx, ll sy, ll ex, ll ey){ ll dx = ex - sx, dy = ey - sy; return dx * dx + dy * dy; } ll dist_M(ll sx, ll sy, ll ex, ll ey){ return abs(sx - ex) + abs(sy - ey); } ll count_range(ll n, ll m){ return ((m - n + 1) * (n + m)) / 2; } ll count_range(ll n, ll m, ll mod){ ll len = (m - n + 1) % mod; ll sum = (n + m) % mod; return len * sum % mod * mod_inv(2, mod) % mod; } ll mul(ll a, ll b) {ll infl = 1LL << 60; if (a == 0 || b == 0) return 0; if (infl / a < b) return infl; return min(infl, a * b); } ll count_sum(ll A, ll D, ll L, ll N){ if(A == -1)return (N * (2 * L - (N - 1) * D)) / 2; else if(L == -1)return (N * (2 * A + (N - 1) * D)) / 2; else if(N == -1)return (((L - A) / D + 1) * (A + L)) / 2; else return (N * (A + L)) / 2; } ll count_sum(ll A, ll D, ll L, ll N, ll mod){ ll inv2 = mod_inv(2, mod); if (A == -1) { return (N % mod) * (((2 * L % mod - ((N - 1) % mod) * D % mod + mod) % mod) * inv2 % mod) % mod; } else if (L == -1) { return (N % mod) * (((2 * A % mod + ((N - 1) % mod) * D % mod) % mod) * inv2 % mod) % mod; } else if (N == -1) { ll num = (((L - A + mod) % mod) * mod_inv(D, mod)) % mod + 1; return (num % mod) * ((A + L) % mod) % mod * inv2 % mod; } else { return (N % mod) * ((A + L) % mod) % mod * inv2 % mod; } } //素数判定 bool is_Prime(ll num){ if(num == 1)return false; for(ll i = 2; i * i <= num; ++i){ if(num % i == 0)return false; } return true; } //約数列挙 vl enum_divisors(ll N) { vl res; for (ll i = 1; i * i <= N; ++i) { if (N % i == 0) { res.push_back(i); if (N/i != i) res.push_back(N/i); } } sort(res.begin(), res.end()); return res; } //素因数分解 vlP prime_factorize(ll N) { vlP res; for (ll a = 2; a * a <= N; ++a) { if (N % a != 0) continue; ll ex = 0; while (N % a == 0) { ++ex; N /= a; } res.push_back({a, ex}); } if (N != 1) res.push_back({N, 1}); return res; } ll count_Multiple(ll R, ll div, ll mod){ if(R == 0)return 0; ll res = R / div; if(mod <= R % div && 0 < mod)++res; return res; } //[L,R]をdivで割ったあまりがmodになる個数 ll count_Multiple(ll L, ll R, ll div, ll mod){ return count_Multiple(R, div, mod) - count_Multiple(L - 1, div, mod); } //n進数のstrをm進数に変換する string ntom(string str, const string S, const string T){ const int n = S.size(), m = T.size(); vector<int> ns(130); for(int i = 0; i < n; ++i)ns[S[i]] = i; long long sum = 0; for(char c : str)sum = sum * n + ns[c]; string res; do{ res = T[sum % m] + res; sum /= m; }while(sum); return res; } string ntom(string str, const int n, const int m){ string S, T; for(int i = 0; i < n; ++i)S.push_back((i >= 10 ? 'A' - 10 : '0') + i); for(int i = 0; i < m; ++i)T.push_back((i >= 10 ? 'A' - 10 : '0') + i); return ntom(str, S, T); } ll ntom(ll N, const int n, const int m){return stoll(ntom(to_string(N), n, m));} template<typename T> T popcount(T x){ ll cnt = 0; while(x){ cnt += (x & 1); x >>= 1; } return cnt; } //RSBが何桁目にあるか -> 2で割り切れる回数 template<typename T> T RSB(T x){ T cnt = 0; while((x & 1) == 0){ ++cnt; x >>= 1; } return cnt; } ll digit_sum(string N){ ll res = 0; for(char c : N)res += (c - '0'); return res; } template<typename T> T digit_sum(T N){return digit_sum(to_string(N));} struct Vector{ ll x, y; ll cross(const Vector &other)const{ return x * other.y - y * other.x; } ll dot(const Vector &other)const{ return x * other.x + y * other.y; } }; //<AOB 0:時計 1:反時計 bool is_lessthan180(const Vector &OA, const Vector &OB, bool o){ if(o)return (OA.cross(OB) > 0); else return (OA.cross(OB) < 0); } //二次元座標上の点を反時計回りにd(rad)回転させる struct rotate_xy{ double x, y; rotate_xy(double x_, double y_) : x(x_), y(y_) {} //rad void rotate(double d){ double nx = x * cos(d) - y * sin(d); double ny = x * sin(d) + y * cos(d); x = nx, y = ny; } }; //not 1/2 ll triArea(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){ return abs((x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3)); } //string string S_lower(string &str){ for(ll i = 0; i < (ll)str.size(); ++i)str[i] = tolower(str[i]); return str; } ll S_count(string &S, char c){ ll cnt = 0; for(ll i = 0; i < (ll)S.size(); ++i)if(S[i] == c)cnt++; return cnt; } bool S_match(string &S, string &T){ vector<int> SA = suffix_array(S); ll ok = 0; ll ng = SA.size(); while(abs(ok - ng) > 1){ ll mid = (ok + ng) / 2; if(S.substr(SA[mid], T.size()) <= T)ok = mid; else ng = mid; } return (S.substr(SA[ok], T.size()) == T); } vc<pair<char, ll>> RLE(string &S){ ll len = S.size(); vc<pair<char, ll>> ret; for(ll i = 0; i < len;){ ll j = i + 1; while(j < len && S[i] == S[j])j++; ret.push_back({S[i], j - i}); i = j; } return ret; } string RLE_D(vc<pair<char, ll>> &ret){ string S; for(auto x : ret){ for(ll i = 0; i < x.second; ++i)S.push_back(x.first); } return S; } template<class T>string to_string(T N, ll len, char c){ string val = to_string(N); return string(len - (ll)val.size(), c) + val; } //graphs void count_Cycles_sub(Graph &G, ll v, vb &seen, vb &finished, ll &count, bool YM, ll parent){ seen[v] = true; for(Edge &e : G[v]){ ll nv = e.to; if(!YM && nv == parent)continue; if(finished[nv])continue; if(seen[nv] && !finished[nv])++count; if(seen[nv])continue; count_Cycles_sub(G, nv, seen, finished, count, YM, v); } finished[v] = true; } //1:有向 0:無向 ll count_Cycles(Graph &G, ll s, bool YM){ ll count = 0; vb seen(ll(G.size())), finished(ll(G.size())); count_Cycles_sub(G, s, seen, finished, count, YM, -1); return count; } vl count_ConnectedComponents(Graph &G){ vl ans; vb seen(ll(G.size())); for(ll i = 0; i < ll(G.size()); ++i){ if(seen[i])continue; queue<ll> que; seen[i] = true; que.push(i); while (!que.empty()) { ll v = que.front(); que.pop(); for(Edge &e : G[v]){ if (seen[e.to]) continue; seen[e.to] = true; que.push(e.to); } } ans.push_back(i); } return ans; } bool is_GraphPath(Graph &G){ ll N = G.size(); vl val = count_ConnectedComponents(G); if((ll)val.size() != 1)return false; ll o = 0, t = 0; for(ll i = 0; i < N; ++i){ if(G[i].size() == 1)++o; else if(G[i].size() == 2)++t; else return false; } if(o != 2 || o + t != N)return false; return true; } //s == -1 : all v vl BFS(Graph &G, ll s){ vl dist(ll(G.size()), -1); vl val = count_ConnectedComponents(G); for(auto p : val){ queue<ll> que; dist[(s==-1?p:s)] = 0; que.push((s==-1?p:s)); while (!que.empty()) { ll v = que.front(); que.pop(); for(const Edge &e : G[v]){ if (dist[e.to] != -1) continue; dist[e.to] = dist[v] + e.weight; que.push(e.to); } } if(s != -1)break; } return dist; } vvl BFS_grid(vs &G, ll sx, ll sy, char s, char f){ vl DX = {-1, 0, 1, 0}, DY = {0, 1, 0, -1}; ll H = G.size(), W = G[0].size(); vvl dist(H, vl(W, -1)); queue<lP> que; if(s == ' '){ que.push({sx, sy}), dist[sx][sy] = 0; }else{ for(ll i = 0; i < H; ++i){ for(ll j = 0; j < W; ++j){ if(G[i][j] == s)que.push({i, j}), dist[i][j] = 0; } } } while(!que.empty()){ auto [x, y] = que.front(); que.pop(); for(ll d = 0; d < ll(DX.size()); ++d){ ll nx = x + DX[d], ny = y + DY[d]; if(nx < 0 || nx >= H || ny < 0 || ny >= W)continue; if(G[nx][ny] == f)continue; if(dist[nx][ny] != -1)continue; que.push({nx, ny}); dist[nx][ny] = dist[x][y] + 1; } } return dist; } vvl BFS_grid(vs &G, char s, char f){return BFS_grid(G, 0, 0, s, f);} vl dijkstra(Graph &G, ll s){ vl dist(ll(G.size()), INF); priority_queue<lP, vlP, greater<lP>> que; dist[s] = 0; que.push({0, s}); while (!que.empty()) { lP p = que.top(); ll d = p.first; ll v = p.second; que.pop(); if(d > dist[v])continue; for(auto &e : G[v]){ if(d + e.weight < dist[e.to]){ dist[e.to] = d + e.weight; que.push({dist[e.to], e.to}); } } } return dist; } void DFS_tree(Graph &G, ll v, ll p, ll d, vl &depth, vl &size){ depth[v] = d; for(auto &e : G[v]){ if(e.to == p)continue; DFS_tree(G, e.to, v, d + 1, depth, size); } size[v] = 1; for(auto &e : G[v]){ if(e.to == p)continue; size[v] += size[e.to]; } } vl eulerTour(Graph G, ll s){ for(auto &v : G){ sort(v.begin(), v.end(), [](const Edge &a, const Edge &b){ return a.to < b.to; }); } vl val; function<void(ll, ll)> f = [&](ll v, ll pre){ val.push_back(v); for (auto &e : G[v]) { if (e.to != pre) { f(e.to, v); val.push_back(v); } } }; f(s, -1); return val; } //トポロジカルソートをし、辞書順最小を返す vl topological_sort(Graph &G){ ll N = G.size(); vl indeg(N); for(ll i = 0; i < N; ++i){ for(auto &e : G[i])indeg[e.to]++; } priority_queue<ll, vl, greater<ll>> pq; for(ll i = 0; i < N; ++i){ if(indeg[i] == 0)pq.push(i); } vl val; val.reserve(N); while(!pq.empty()){ ll v = pq.top(); pq.pop(); val.push_back(v); for(auto &e : G[v]){ indeg[e.to]--; if(indeg[e.to] == 0){ pq.push(e.to); } } } if((ll)val.size() != N)return {-1}; return val; } struct UnionFind{ private: vector<ll> par, rank, size_; ll cntset; public: UnionFind(ll N) : par(N), rank(N), size_(N, 1), cntset(N){ for(ll i = 0; i < N; i++) par[i] = i; } ll root(ll x){ if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(ll x, ll y){ x = root(x); y = root(y); if (x == y) return; if(rank[x] < rank[y]){ par[x] = y; size_[y] += size_[x]; }else{ par[y] = x; size_[x] += size_[y]; if(rank[x] == rank[y])++rank[x]; } --cntset; } bool same(ll x, ll y){ return root(x) == root(y); } ll size(ll x){ return size_[root(x)]; } ll countSets(){return cntset;} vector<vector<ll> > groups(){ ll N = par.size(); vector<ll> leader_buf(N), group_size(N); for(ll i = 0; i < N; i++){ leader_buf[i] = root(i); group_size[leader_buf[i]]++; } vector<vector<ll>> result(N); for (ll i = 0; i < N; i++){ result[i].reserve(group_size[i]); } for (ll i = 0; i < N; i++){ result[leader_buf[i]].push_back(i); } result.erase( remove_if(result.begin(), result.end(), [&](const vector<ll>& v) { return v.empty(); }), result.end()); return result; } }; //others template<class... A> void prints() { std::cout << std::endl; } template<class... A> void prints_rest() { std::cout << std::endl; } template<class T, class... A> void prints_rest(const T& first, const A&... rest) { std::cout << " " << first; prints_rest(rest...); } template<class T, class... A> void prints(const T& first, const A&... rest) { std::cout << first; prints_rest(rest...); } template<class T> void PrintContainer(const T &C){ cout << "[ "; for(auto c : C)cout << c << ' '; cout << "]\n"; } template<class T> void PrintContainer(const set<T> &st){ cout << "[ "; for(auto c : st)cout << c << ' '; cout << "]\n"; } template<class T> void PrintContainer(const multiset<T> &st){ cout << "[ "; for(auto c : st)cout << c << ' '; cout << "]\n"; } template<class T> void PrintContainer(const queue<T> &que){ queue<T> que_ = que; cout << "[ "; while(!que_.empty()){cout << que_.front() << ' ';que_.pop();} cout << "]\n"; } template<class T> void PrintContainer(const priority_queue<T> &pq){ priority_queue<T> pq_ = pq; cout << "[ "; while(!pq_.empty()){cout << pq_.top() << ' ';pq_.pop();} cout << "]\n"; } template<class T> void PrintContainer(const priority_queue<T, vector<T>, greater<T> > &pq){ priority_queue<T, vector<T>, greater<T> > pq_ = pq; cout << "[ "; while(!pq_.empty()){cout << pq_.top() << ' ';pq_.pop();} cout << "]\n"; } template<class T> void PrintContainer(const stack<T> &sta){ stack<T> sta_ = sta; cout << "[ "; while(!sta_.empty()){cout << sta_.top() << ' ';sta_.pop();} cout << "]\n"; } template <typename T> void print_var(const std::string& name, const T& value) { std::cout << name << ": " << value << std::endl; } std::string extract_name(const std::string& names, size_t& pos) { size_t start = pos; int brackets = 0; while (pos < names.size()) { char ch = names[pos]; if (ch == '(') ++brackets; if (ch == ')') --brackets; if (ch == ',' && brackets == 0) break; ++pos; } std::string name = names.substr(start, pos - start); name.erase(0, name.find_first_not_of(" \t")); name.erase(name.find_last_not_of(" \t") + 1); ++pos; return name; } #define DEBUG(...) prints_impl(#__VA_ARGS__, __VA_ARGS__) template <typename... Args> void prints_impl(const std::string& names, Args&&... args) { size_t pos = 0; ((print_var(extract_name(names, pos), std::forward<Args>(args))), ...); } bool dictionary_sort(string &s1, string &s2){ for(ll i = 0; i < ll(min(s1.size(), s2.size())); ++i){ if(s1[i] == s2[i])continue; return s1[i] < s2[i]; } return s1.size() < s2.size(); } //trueならcontinue bool out_grid(ll i, ll j, ll h, ll w) { return (!(0 <= i && i < h && 0 <= j && j < w)); } template<typename T> vector<T> partial_sum(vector<T> &v){ vector<T> val(v.size() + 1); for(int i = 0; i < (int)v.size(); ++i)val[i + 1] = val[i] + v[i]; return val; } template<typename T> T median(vector<T> &A){ T N = A.size(); sort(A.begin(), A.end()); return (N / 2 ? A[N / 2] : (A[N / 2 - 1] + A[N / 2]) / 2); } template<typename T> void vector_append(vector<T> &destination, const vector<T> &source){ ranges::copy(source, back_inserter(destination)); } struct CircularRing{ private: ll N; public: CircularRing(ll N_) : N(N_) {} //0:時計1:反時計[s, e] bool cross(ll s, ll e, ll x, ll rote){ if(rote == 0){ if(s > e)return (s <= x || x <= e); else return (s <= x && x <= e); }else{ if(s < e)return (s <= x || x <= e); else return (e <= x && x <= s); } } //0:時計1:反時計[s, e] ll dist(ll s, ll e, ll m, ll rote){ if(rote == -1 && s > e)swap(s, e); if(m == -1){ if(rote == -1){ return min(e - s, N - (e - s)); }else if(rote == 0){ if(s < e)return e - s; else return N - (s - e); }else{ if(s > e)return s - e; else return N - (e - s); } }else{ if(rote == -1){ if(e - s <= N - (e - s)){ if(s < m && m < e)return N - (e - s); else return e - s; }else{ if(e < m || m < s)return e - s; else return N - (e - s); } }else{ if(cross(s, e, m, rote))return -1; else return dist(s, e, -1, rote); } } } }; template<typename T> vector<T> press_xy(vector<T> &A){ vector<T> B = A; sort(B.begin(), B.end()); B.erase(unique(B.begin(), B.end()), B.end()); vector<T> res(int(A.size())); for(int i = 0; i < int(A.size()); ++i){ res[i] = lower_bound(B.begin(), B.end(), A[i]) - B.begin(); } return res; } //mh, Mh, mw, Mw tuple<ll, ll, ll, ll> min_rectangle(vs &G, char c){ ll H = G.size(), W = G[0].size(); ll mh = INF, Mh = -INF, mw = INF, Mw = -INF; for(ll i = 0; i < H; ++i){ for(ll j = 0; j < W; ++j){ if(G[i][j] == c)chmax(Mh, i), chmin(mh, i), chmax(Mw, j), chmin(mw, j); } } return {mh, Mh, mw, Mw}; } //1:時計0:反時計 vs vector2D_rotate(vs A, bool clockwise = false, char leading = 0){ ll N = A.size(); if(N == 0)return A; ll M = 0; for(ll i = 0; i < N; ++i)M = max(M, (ll)A[i].size()); vs B(M, string(N, leading)); for(ll i = 0; i < N; ++i){ for(int j = 0; j < (ll)A[i].size(); ++j){ if(clockwise)B[j][N - 1 - i] = A[i][j]; else B[M - 1 - j][i] = A[i][j]; } } return B; } template<class T>void reverse(T &C, int L, int R){ auto itl = next(C.begin(), L); auto itr = next(C.begin(), R + 1); reverse(itl, itr); } template <class T> bool is_reverse(T &C){ int len = C.size(); for(int i = 0; i < len / 2; ++i)if(C[i] != C[len - i - 1])return false; return true; } template <class T> bool is_reverse(T &C, int s, int e){ int len = e - s + 1; for(int i = 0; i < len / 2; ++i)if(C[i + s] != C[len - i - 1 + s])return false; return true; } template<typename T> ll binary_search_index(vector<T> &C, T key){ auto it = lower_bound(C.begin(), C.end(), key); if(it != C.end() && *it == key)return (it - C.begin()); else return -1; } //v.size() == r; bool next_combination(int n, int r, vl &v){ int i = v.size() - 1; while (i >= 0 && v[i] == i + n - r)i--; if (i < 0) return false; v[i]++; for (int j = i + 1; j < r; j++){ v[j] = v[j - 1] + 1; } return true; } struct BIT{ private: ll n; vl a; public: BIT(ll n) : n(n), a(n + 1, 0){} void add(ll i, ll x){ i++; if(i == 0) return; for(ll k = i; k <= n; k += (k & -k))a[k] += x; } void update(ll i, ll x){add(i, x - sum(i, i));} ll sum_sub(ll i){ i++; ll s = 0; if(i == 0) return s; for(ll k = i; k > 0; k -= (k & -k)){ s += a[k]; } return s; } ll sum(ll i, ll j){return sum_sub(j) - sum_sub(i - 1);} ll lower_bound(ll x){ if(x <= 0){ return 0; }else{ ll i = 0; ll r = 1; while(r < n) r = r << 1; for(ll len = r; len > 0; len = len >> 1){ if(i + len < n && a[i + len] < x){ x -= a[i + len]; i += len; } } return i; } } }; ll count_inversions(vl &v){ ll ans = 0, len = v.size(); BIT b(len); for(ll i = 0; i < len; ++i){ ans += i - b.sum_sub(v[i]); b.add(v[i], 1); } return ans; } template <class T>ll count_inversions(vector<T> S, vector<T> E){ if(S.size() != E.size())return -1; map<T, ll> mp; ll len = S.size(); for(ll i = 0; i < len; ++i)mp[E[i]] = i; vector<ll> val(len); for(ll i = 0; i < len; ++i)val[i] = mp[S[i]]; return count_inversions(val); } ll count_inversions(string S, string E){ if(S.size() != E.size())return -1; ll len = S.size(); map<char, ll> mp; for(ll i = 0; i < len; ++i)mp[E[i]] = i; vl val(len); for(ll i = 0; i < len; ++i)val[i] = mp[S[i]]; return count_inversions(val); } //1-indexed struct Kthset{ private: multiset<ll>L, R; ll K; public: Kthset(ll k) : K(k){} void insert(ll v){ R.insert(v); if((ll)L.size() < K){ L.insert(*R.begin()); R.erase(R.begin()); }else if(*R.begin() < *L.rbegin()){ L.insert(*R.begin()); R.erase(R.begin()); R.insert(*L.rbegin()); L.erase(--L.end()); } } void erase(ll v){ auto itl = L.find(v), itr = R.find(v); if(itl != L.end()){ L.erase(itl); }else if(itr != R.end()){ R.erase(itr); } if((ll)L.size() < K && !R.empty()){ L.insert(*R.begin()); R.erase(R.begin()); } } ll getKth(){return *L.rbegin();} }; template <typename T> class TreeList{ private: struct Node{ T value; Node* left; Node* right; ll bias; ll height; ll size; Node(const T& val) : value(val), left(nullptr), right(nullptr), bias(0), height(1), size(1) {} }; Node* root; ll heightOf(Node* node){ return node ? node->height : 0; } ll sizeOf(Node* node) const{ return node ? node->size : 0; } void update(Node* node){ if (!node) return; node->height = std::max(heightOf(node->left), heightOf(node->right)) + 1; node->size = sizeOf(node->left) + sizeOf(node->right) + 1; node->bias = heightOf(node->left) - heightOf(node->right); } Node* rotateLeft(Node* node){ Node* right = node->right; node->right = right->left; right->left = node; update(node); update(right); return right; } Node* rotateRight(Node* node){ Node* left = node->left; node->left = left->right; left->right = node; update(node); update(left); return left; } Node* balance(Node* node){ if(!node)return nullptr; update(node); if(node->bias > 1){ if(node->left->bias < 0){ node->left = rotateLeft(node->left); } return rotateRight(node); } if(node->bias < -1){ if(node->right->bias > 0){ node->right = rotateRight(node->right); } return rotateLeft(node); } return node; } Node* insertRecursive(Node* node, ll index, const T& value){ if(!node)return new Node(value); ll leftSize = sizeOf(node->left); if(index <= leftSize){ node->left = insertRecursive(node->left, index, value); }else{ node->right = insertRecursive(node->right, index - leftSize - 1, value); } return balance(node); } T& getByIndexRecursive(Node* node, ll index){ if(!node) throw std::out_of_range("Index out of range"); ll leftSize = sizeOf(node->left); if(index == leftSize)return node->value; if(index < leftSize)return getByIndexRecursive(node->left, index); return getByIndexRecursive(node->right, index - leftSize - 1); } public: TreeList() : root(nullptr) {} ll count() const { return sizeOf(root); } void insert(ll index, const T& value){ if(index < 0 || index > count()){ throw std::out_of_range("Index out of range"); } root = insertRecursive(root, index, value); } T getElementAt(ll index){ if(index < 0 || index >= count()){ throw std::out_of_range("Index out of range"); } return getByIndexRecursive(root, index); } T& operator[](ll index){ if(index < 0 || index >= count()){ throw std::out_of_range("Index out of range"); } return getByIndexRecursive(root, index); } const T& operator[](ll index) const { if(index < 0 || index >= count()){ throw std::out_of_range("Index out of range"); } return getByIndexRecursive(root, index); } }; //////////////////////////////////////////////////////////////////////////////////////////////// int main(){ ll N;cin >> N; string S;cin >> S; if(N % 2){ NO; return 0; } YES; string P, Q; rep(i, S.size()){ if(i % 2)Q.push_back(S[i]); else P.push_back(S[i]); } prints(P, Q); }