#include // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2") #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define yn(joken) cout<<((joken) ? "Yes" : "No")<<"\n" #define YN(joken) cout<<((joken) ? "YES" : "NO")<<"\n" using namespace std; using ll = long long; using vi = vector; using vl = vector; using vs = vector; using vc = vector; using vd = vector; using vld = vector; using vvi = vector>; using vvl = vector>; using vvs = vector>; using vvc = vector>; using vvd = vector>; using vvld = vector>; using vvvi = vector>>; using vvvl = vector>>; using vvvvi = vector>>>; using vvvvl = vector>>>; using pii = pair; using pll = pair; const int INF = 1e9; const ll LINF = 2e18; template bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } bool ispow2(int i) { return i && (i & -i) == i; } bool ispow2(ll i) { return i && (i & -i) == i; } template vector make_vec(size_t a) { return vector(a); } template auto make_vec(size_t a, Ts... ts) { return vector(ts...))>(a, make_vec(ts...)); } template istream& operator>>(istream& is, vector& v) { for (int i = 0; i < int(v.size()); i++) { is >> v[i]; } return is; } template ostream& operator<<(ostream& os, const vector& v) { for (int i = 0; i < int(v.size()); i++) { os << v[i]; if (i < int(v.size()) - 1) os << ' '; } return os; } static uint32_t RandXor(){ static uint32_t x=123456789; static uint32_t y=362436069; static uint32_t z=521288629; static uint32_t w=88675123; uint32_t t; t=x^(x<<11); x=y; y=z; z=w; return w=(w^(w>>19))^(t^(t>>8)); } static double Rand01(){ return (RandXor()+0.5)*(1.0/UINT_MAX); } // BinaryTrie BT; などする // void add(INT val): BTに入っている数字全てにvalをXORする // INT get(Node *v): ポインタvに対応した値を返す(BTに入っている値,XORした時のk番目とかのときはあとで自分でXORする) // Node* find(INT val): valに対応したポインタを返す // void insert(INT val,size_t k=1): valをk個追加する // bool erase(INT val): valを1個削除する // bool erase(Node *v,size_t k=1): ポインタvに対応した値をk個削除する // Node* get_max(INT val=0): valをXORした時の最大の要素と対応したポインタを返す(復元はget(*ptr)^valする) // Node* get_min(INT val=0): 上の最小バージョン // Node* lower_bound(INT val): val以上で最小の要素に対応するポインタを返す // Node* upper_bound(INT val): valより大で最小の要素に対応するポインタを返す // size_t order_of_val(INT val): valが小さい方から何番目か返す(val未満の数の個数+1を返すとも) // Node* get_kth(size_t k,INT val=0): valをXORした時の小さい方からk番目(0-indexed)の要素に対応したポインタを返す(復元はget(*ptr)^valする) template struct BinaryTrie{ struct Node{ size_t count; Node *prev, *left, *right; Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {} }; INT lazy; Node *root; // constructor BinaryTrie() : lazy(0), root(emplace(nullptr)) {} inline size_t get_count(Node *v) const { return v ? v->count : 0; } // add and get value of Node inline void add(INT val){ lazy ^= val; } inline INT get(Node *v){ if (!v) return -1; INT res = 0; for (int i = 0; i < MAX_DIGIT; ++i){ if (v == v->prev->right) res |= INT(1) << i; v = v->prev; } return res ^ lazy; } // find Node* whose value is val Node *find(INT val){ INT nval = val ^ lazy; Node *v = root; for (int i = MAX_DIGIT - 1; i >= 0; --i){ bool flag = (nval >> i) & 1; if (flag) v = v->right; else v = v->left; if (!v) return v; } return v; } // insert inline Node *emplace(Node *prev){ return new Node(prev); } void insert(INT val, size_t k = 1){ INT nval = val ^ lazy; Node *v = root; for (int i = MAX_DIGIT - 1; i >= 0; --i){ bool flag = (nval >> i) & 1; if (flag && !v->right) v->right = emplace(v); if (!flag && !v->left) v->left = emplace(v); if (flag) v = v->right; else v = v->left; } v->count += k; while ((v = v->prev)) v->count = get_count(v->left) + get_count(v->right); } // erase Node *clear(Node *v){ if (!v || get_count(v)) return v; delete (v); return nullptr; } bool erase(Node *v, size_t k = 1){ if (!v) return false; v->count -= k; while ((v = v->prev)){ v->left = clear(v->left); v->right = clear(v->right); v->count = get_count(v->left) + get_count(v->right); } return true; } bool erase(INT val){ auto v = find(val); return erase(v); } // max (with xor-addition of val) and min (with xor-addition of val) Node *get_max(INT val = 0){ INT nval = val ^ lazy; Node *v = root; for (int i = MAX_DIGIT - 1; i >= 0; --i){ bool flag = (nval >> i) & 1; if (!v->right) v = v->left; else if (!v->left) v = v->right; else if (flag) v = v->left; else v = v->right; } return v; } Node *get_min(INT val = 0){ return get_max(~val & ((INT(1) << MAX_DIGIT) - 1)); } // lower_bound, upper_bound Node *get_cur_node(Node *v, int i){ if (!v) return v; Node *left = v->left, *right = v->right; if ((lazy >> i) & 1) swap(left, right); if (left) return get_cur_node(left, i + 1); else if (right) return get_cur_node(right, i + 1); return v; } Node *get_next_node(Node *v, int i){ if (!v->prev) return nullptr; Node *left = v->prev->left, *right = v->prev->right; if ((lazy >> (i + 1)) & 1) swap(left, right); if (v == left && right) return get_cur_node(right, i); else return get_next_node(v->prev, i + 1); } Node *lower_bound(INT val){ INT nval = val ^ lazy; Node *v = root; for (int i = MAX_DIGIT - 1; i >= 0; --i){ bool flag = (nval >> i) & 1; if (flag && v->right) v = v->right; else if (!flag && v->left) v = v->left; else if ((val >> i) & 1) return get_next_node(v, i); else return get_cur_node(v, i); } return v; } Node *upper_bound(INT val){ return lower_bound(val + 1); } size_t order_of_val(INT val){ Node *v = root; size_t res = 0; for (int i = MAX_DIGIT - 1; i >= 0; --i){ Node *left = v->left, *right = v->right; if ((lazy >> i) & 1) swap(left, right); bool flag = (val >> i) & 1; if (flag){ res += get_count(left); v = right; } else v = left; } return res; } // k-th, k is 0-indexed Node *get_kth(size_t k, INT val = 0){ Node *v = root; INT nval = val ^ lazy; if (get_count(v) <= k) return nullptr; for (int i = MAX_DIGIT - 1; i >= 0; --i){ bool flag = (nval >> i) & 1; Node *left = (flag ? v->right : v->left); Node *right = (flag ? v->left : v->right); if (get_count(left) <= k) k -= get_count(left), v = right; else v = left; } return v; } // debug void print(Node *v, string prefix = ""){ if (!v) return; cout << prefix << ": " << v->count << endl; print(v->left, prefix + "0"); print(v->right, prefix + "1"); } void print(){ print(root); } vector eval(Node *v, int digit) const{ vector res; if (!v) return res; if (!v->left && !v->right){ for (int i = 0; i < get_count(v); ++i) res.push_back(0); return res; } const auto &left = eval(v->left, digit - 1); const auto &right = eval(v->right, digit - 1); for (auto val : left) res.push_back(val); for (auto val : right) res.push_back(val + (INT(1) << digit)); return res; } vector eval() const{ auto res = eval(root, MAX_DIGIT - 1); for (auto &val : res) val ^= lazy; return res; } friend ostream &operator<<(ostream &os, const BinaryTrie &bt){ auto res = bt.eval(); for (auto val : res) os << val << " "; return os; } }; void solve(){ int N; cin>>N; string S; cin>>S; vi cnt(26); BinaryTrie BT; rep(i,N){ cnt[S[i]-'A']++; BT.insert(i); } int d=0,ans=0; while(true){ int x=cnt[(26-d)%26]+cnt[(28-d)%26]+cnt[(32-d)%26]+cnt[(45-d)%26]; if(!x) break; ans++; int p=BT.get(BT.get_kth(x-1)); cnt[S[p]-'A']--; BT.erase(p); int y=cnt[S[p]-'A']; d=(d+y)%26; } cout<