結果
問題 | No.3036 Nauclhlt型文字列 |
ユーザー |
|
提出日時 | 2025-02-28 21:25:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 26,071 bytes |
コンパイル時間 | 7,599 ms |
コンパイル使用メモリ | 353,400 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2025-02-28 21:26:00 |
合計ジャッジ時間 | 8,374 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define INF 1LL << 60#define MOD 998244353#define MMOD 1000000007using 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());}//////////////////////////////////////////////////////////////////////////////////////////////////mathsll 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_sqrtll 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_) {}//radvoid 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/2ll triArea(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){return abs((x1 - x3) * (y2 - y3) - (x2 - x3) * (y1 - y3));}//stringstring 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;}//graphsvoid 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 vvl 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;}};//otherstemplate<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ならcontinuebool 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, Mwtuple<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-indexedstruct 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);}