結果
| 問題 | No.2997 Making YuzuKizu |
| ユーザー |
 ルク
|
| 提出日時 | 2024-12-04 17:56:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 32,070 bytes |
| コンパイル時間 | 6,154 ms |
| コンパイル使用メモリ | 486,396 KB |
| 最終ジャッジ日時 | 2025-02-26 10:55:09 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /usr/include/c++/13/string:43,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
from main.cpp:5:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::__cxx11::basic_string<char>::_Alloc_hider::~_Alloc_hider()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = char]’: target specific option mismatch
184 | ~allocator() _GLIBCXX_NOTHROW { }
| ^
In file included from /usr/include/c++/13/string:54:
/usr/include/c++/13/bits/basic_string.h:181:14: note: called from here
181 | struct _Alloc_hider : allocator_type // TODO check __is_final
| ^~~~~~~~~~~~
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#if __has_include(<bits/stdc++.h>)#include <bits/stdc++.h>using namespace std;#endif#if __has_include(<boost/multiprecision/cpp_int.hpp>)#include <boost/multiprecision/cpp_int.hpp>using namespace boost::multiprecision;#endif#if __has_include(<atcoder/all>)#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using MINT = modint1000000007;#endif#if __has_include("./cpp-dump/cpp-dump.hpp")#include "./cpp-dump/cpp-dump.hpp"#endif#include <chrono>#include <random>using namespace chrono;#define rep(i, n) for (ll i = 0; i < (int)(n); ++i)#define rep1(i, n) for (ll i = 1; i <= (n); ++i)#define rrep(i, n) for (ll i = n; i > 0; --i)#define bitrep(i, n) for (ll i = 0; i < (1 << n); ++i)#define all(a) (a).begin(), (a).end()#define yesNo(b) ((b) ? "Yes" : "No")using ll = long long;using ull = unsigned long long;using ld = long double;string alphabet = "abcdefghijklmnopqrstuvwxyz";string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";constexpr double pi = 3.141592653589793;constexpr ll smallMOD = 998244353;constexpr ll bigMOD = 1000000007;constexpr ll INF = 1LL << 60;constexpr ll dx[] = {1, 0, -1, 0, 1, -1, -1, 1};constexpr ll dy[] = {0, 1, 0, -1, 1, 1, -1, -1};// init.struct Init{Init(){ios::sync_with_stdio(0);cin.tie(0);cout << fixed << setprecision(15);}} init;template <typename T>ostream &operator<<(ostream &os, const vector<T> &vec){os << "[";rep(i, vec.size()){os << vec[i];if (i != vec.size() - 1)os << ", ";}os << "]";return os;}template <typename T>ostream &operator<<(ostream &os, const vector<vector<T>> &vec){os << "[";rep(i, vec.size()){os << vec[i];if (i != vec.size() - 1)os << ", ";}os << "]";return os;}template <typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &pair_var){os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}template <typename T>ostream &operator<<(ostream &os, const set<T> &st){os << "{";for (auto itr = st.begin(); itr != st.end(); ++itr){os << *itr;if (next(itr) != st.end())os << ", ";}os << "}";return os;}template <typename T>ostream &operator<<(ostream &os, const multiset<T> &st){os << "{";for (auto itr = st.begin(); itr != st.end(); ++itr){os << *itr;if (next(itr) != st.end())os << ", ";}os << "}";return os;}template <typename T>ostream &operator<<(ostream &os, const queue<T> &que){queue<T> que2 = que;os << "{";while (!que2.empty()){os << que2.front();que2.pop();if (!que2.empty())os << ", ";}os << "}";return os;}template <typename T>ostream &operator<<(ostream &os, const deque<T> &deq){os << "{";rep(i, deq.size()){os << deq[i];if (i != deq.size() - 1)os << ", ";}os << "}";return os;}template <typename T, typename U>ostream &operator<<(ostream &os, const map<T, U> &mp){os << "{";for (auto itr = mp.begin(); itr != mp.end(); ++itr){os << *itr;if (next(itr) != mp.end())os << ", ";}os << "}";return os;}template <typename T>ostream &operator<<(ostream &os, const stack<T> &stk){stack<T> stk2 = stk;os << "{";while (!stk2.empty()){os << stk2.top();stk2.pop();if (!stk2.empty())os << ", ";}os << "}";return os;}template <typename T>ostream &operator<<(ostream &os, const priority_queue<T> &que){priority_queue<T> que2 = que;os << "{";while (!que2.empty()){os << que2.top();que2.pop();if (!que2.empty())os << ", ";}os << "}";return os;}template <class T>bool chmax(T &a, T b){if (a < b){a = b;return 1;}return 0;}template <class T>bool chmin(T &a, T b){if (b < a){a = b;return 1;}return 0;}template <class T>size_t HashCombine(const size_t seed, const T &v){return seed ^ (std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2));}template <class T, class S>struct std::hash<std::pair<T, S>>{size_t operator()(const std::pair<T, S> &keyval) const noexcept{return HashCombine(std::hash<T>()(keyval.first), keyval.second);}};template <class T>struct std::hash<std::vector<T>>{size_t operator()(const std::vector<T> &keyval) const noexcept{size_t s = 0;for (auto &&v : keyval)s = HashCombine(s, v);return s;}};template <int N>struct HashTupleCore{template <class Tuple>size_t operator()(const Tuple &keyval) const noexcept{size_t s = HashTupleCore<N - 1>()(keyval);return HashCombine(s, std::get<N - 1>(keyval));}};template <>struct HashTupleCore<0>{template <class Tuple>size_t operator()(const Tuple &keyval) const noexcept { return 0; }};template <class... Args>struct std::hash<std::tuple<Args...>>{size_t operator()(const tuple<Args...> &keyval) const noexcept{return HashTupleCore<tuple_size<tuple<Args...>>::value>()(keyval);}};// Math.vector<ll> all_divisors(ll N){vector<ll> res;for (ll i = 1; i * i <= N; ++i){if (N % i != 0)continue;res.push_back(i);if (N / i != i)res.push_back(N / i);}sort(res.begin(), res.end());return res;}void recursive_comb(vector<ll> indexes, ll s, ll rest, function<void(vector<ll>)> f){if (rest == 0){f(indexes);}else{if (s < 0)return;recursive_comb(indexes, s - 1, rest, f);indexes[rest - 1] = s;recursive_comb(indexes, s - 1, rest - 1, f);}}void foreach_comb(ll n, ll k, function<void(vector<ll>)> f){vector<ll> indexes(k);recursive_comb(indexes, n - 1, k, f);}vector<pair<ll, ll>> prime_factorize(ll N){vector<pair<ll, ll>> res;for (ll p = 2; p * p <= N; ++p){if (N % p != 0)continue;ll e = 0;while (N % p == 0){++e;N /= p;}res.emplace_back(p, e);}if (N != 1){res.emplace_back(N, 1);}return res;}ll repeated_squaring(ll x, ll y, ll z = smallMOD){ll ans = 1;bitset<64> bits(y);string bit_str = bits.to_string();reverse(all(bit_str));rep(i, 64){if (bit_str[i] == '1')ans = ans * x % z;x = x * x % z;}return ans;}// String.bool isPalindrome(string str){ll low = 0;ll high = str.length() - 1;while (low < high){if (str[low] != str[high]){return false;}low++;high--;}return true;}map<char, ll> alphabetHash = {{'a', 2},{'b', 3},{'c', 5},{'d', 7},{'e', 11},{'f', 13},{'g', 17},{'h', 19},{'i', 23},{'j', 29},{'k', 31},{'l', 37},{'m', 41},{'n', 43},{'o', 47},{'p', 53},{'q', 59},{'r', 61},{'s', 67},{'t', 71},{'u', 73},{'v', 79},{'w', 83},{'x', 89},{'y', 97},{'z', 101},};void split(vector<string> &elems, const string &s, char delim){stringstream ss(s);string item;while (getline(ss, item, delim)){elems.push_back(item);}}ll string_mod(string s, ll mod){ll rest = 0;for (char c : s){ll v = c - '0';rest = (rest * 10 + v) % mod;}return rest;}// algorithms.pair<pair<ll, ll>, pair<ll, ll>> maxAndMinSubarraySum(const vector<ll> &nums){ll maxSum = nums[0];ll minSum = nums[0];ll maxStart = 0;ll maxEnd = 0;ll minStart = 0;ll minEnd = 0;ll currentMaxSum = nums[0];ll currentMinSum = nums[0];ll tempMaxStart = 0;ll tempMinStart = 0;for (ll i = 1; i < nums.size(); ++i){if (currentMaxSum < 0){currentMaxSum = nums[i];tempMaxStart = i;}else{currentMaxSum += nums[i];}if (currentMaxSum > maxSum){maxSum = currentMaxSum;maxStart = tempMaxStart;maxEnd = i;}if (currentMinSum > 0){currentMinSum = nums[i];tempMinStart = i;}else{currentMinSum += nums[i];}if (currentMinSum < minSum){minSum = currentMinSum;minStart = tempMinStart;minEnd = i;}}return make_pair(make_pair(maxStart, maxEnd), make_pair(minStart, minEnd));}// array.vector<string> RotateVectorString(vector<string> A, bool clockwise = false, char leading = 0){ll N = A.size();if (N == 0)return A;ll M = 0;rep(i, N){M = max(M, (ll)A[i].size());}vector<string> B(M, string(N, leading));rep(i, N){rep(j, A[i].size()){if (clockwise){B[j][N - 1 - i] = A[i][j];}else{B[M - 1 - j][i] = A[i][j];}}}return B;}// struct.// Data structure.struct CumulativeSum2D{vector<vector<ll>> data;CumulativeSum2D(vector<vector<ll>> &source){ll h = source.size();ll w = 0;if (h != 0)w = source[0].size();data.resize(h + 1, vector<ll>(w + 1, 0));rep(i, h){rep(j, w){data[i + 1][j + 1] = source[i][j];}}rep(i, h + 1){rep(j, w){data[i][j + 1] += data[i][j];}}rep(i, h){rep(j, w + 1){data[i + 1][j] += data[i][j];}}}ll query(ll x1, ll y1, ll x2, ll y2){return data[x2][y2] - data[x1][y2] - data[x2][y1] + data[x1][y1];}};struct CumulativeSumND{public:vector<ll> sum;ll N;ll d;CumulativeSumND(ll d, ll N, vector<ll> &data){this->d = d;this->N = N;ll cumSize = 1;ll size = 1;ll bitSize = 1;for (ll i = 0; i < d; i++){cumSize *= N + 1;size *= N;bitSize *= 2;assert(cumSize <= 1e8);assert(size <= 1e8);assert(bitSize <= 1e8);}assert(data.size() == size);sum.resize(cumSize);build(data);}// (X1,Y1,Z1,W1,...,X2,Y2,Z2,W2,...)ll query(vector<ll> q){assert(q.size() == d * 2);vector<ll> LPos(d + 1, 0);vector<ll> RPos(d + 1, 0);ll res = 0;for (ll i = 0; i < d; i++){LPos[i + 1] = q[i] - 1;RPos[i + 1] = q[i + d];}bitrep(i, d){vector<ll> pos(d + 1, 0);ll cnt = 0;rep(j, d){if (i & (1 << j)){pos[j + 1] = RPos[j + 1];}else{pos[j + 1] = LPos[j + 1];cnt++;}}if (cnt % 2){res -= sum[getPos(pos, 1)];}else{res += sum[getPos(pos, 1)];}}return res;}private:// 0-indexed.ll getPos(vector<ll> &pos, bool isZeroIndex){assert(pos.size() == d + 1);vector<ll> A(d, 1);for (ll i = 0; i < d - 1; i++){A[i + 1] = A[i] * (N + isZeroIndex);}reverse(all(A));ll res = 0;for (ll i = 1; i < d + 1; i++){res += A[i - 1] * pos[i];}return res;}void build(vector<ll> &data){{// 0-indexed→1-indexed.vector<ll> loop(d + 1, 0);while (loop[0] != 1){bool isZero = false;for (ll i = 1; i < d + 1; i++){if (loop[i] == 0){isZero = true;break;}}if (!isZero){ll sumPos = getPos(loop, 1);for (ll i = 1; i < d + 1; i++){loop[i]--;}ll dataPos = getPos(loop, 0);for (ll i = 1; i < d + 1; i++){loop[i]++;}sum[sumPos] = data[dataPos];}loop[d]++;// 繰り上がり処理.for (ll i = d; i > 0; i--){if (loop[i] == N + 1){loop[i] = 0;loop[i - 1]++;}}}}// calc sum.{vector<ll> loop(d + 1, 0);while (loop[0] != d){ll p1 = getPos(loop, 1);loop[loop[0] + 1]++;ll p2 = getPos(loop, 1);sum[p2] += sum[p1];loop[loop[0] + 1]--;loop[d]++;// 繰り上がり処理.for (ll i = d; i > 0; i--){if (i == loop[0] + 1){// N-1回.if (loop[i] == N){loop[i] = 0;loop[i - 1]++;}}else{// N回.if (loop[i] == N + 1){loop[i] = 0;loop[i - 1]++;}}}}}}};struct BitVector{public:vector<int> data, cum;BitVector(vector<int> &source){if (source.size() != 0){data.resize(source.size(), 0);cum.resize(source.size(), 0);cum[0] = source[0];for (int i = 0; i < (int)source.size(); i++){data[i] = source[i];assert(source[i] == 0 || source[i] == 1);if (i != 0){cum[i] = cum[i - 1] + source[i];}}}}int size(){return (int)data.size();}int get(int i){return data[i];}int rank1(int i){if (i <= 0){return 0;}i = min(i, (int)data.size());return cum[i - 1];}int rank0(int i){if (i <= 0){return 0;}i = min(i, (int)data.size());return i - rank1(i);}int rank0_all(){return rank0(data.size());}int rank1_all(){return rank1(data.size());}int select0(int k){// K個目の0のindexを返す.if (k <= 0 || k > rank0_all()){return -1;}int l = 0, r = data.size();while (r - l > 1){int mid = (l + r) / 2;if (rank0(mid) < k){l = mid;}else{r = mid;}}return l;}int select1(int k){// K個目の1のindexを返す.if (k <= 0 || k > rank1_all()){return -1;}int l = 0, r = data.size();while (r - l > 1){int mid = (l + r) / 2;if (rank1(mid) < k){l = mid;}else{r = mid;}}return l;}};struct UnionFind{vector<ll> parent;vector<ll> parentSize;vector<set<ll>> children;UnionFind(ll N){rep(i, N + 1){parent.push_back(i);parentSize.push_back(1);children.push_back({i});}}ll root(ll x){if (parent[x] == x)return x;parent[x] = root(parent[x]);return parent[x];}void unite(ll x, ll y){x = root(x);y = root(y);if (x == y)return;if (parentSize[x] <= parentSize[y]){parent[x] = y;parentSize[y] += parentSize[x];for (auto c : children[x]){children[y].insert(c);}children[x].clear();}else{parent[y] = x;parentSize[x] += parentSize[y];for (auto c : children[y]){children[x].insert(c);}children[y].clear();}}bool same(ll x, ll y){return root(x) == root(y);}ll size(ll x){return parentSize[root(x)];}};// Math.struct NCR{ll max = 510000, mod = 0;vector<ll> fact, inv, inv_fact;NCR(ll mod = 998244353){this->mod = mod;fact.resize(max);inv.resize(max);inv_fact.resize(max);fact[0] = 1;fact[1] = 1;inv[0] = 1;inv[1] = 1;inv_fact[0] = 1;inv_fact[1] = 1;for (ll i = 2; i < max; i++){fact[i] = fact[i - 1] * i % mod;inv[i] = mod - inv[mod % i] * (mod / i) % mod;inv_fact[i] = inv_fact[i - 1] * inv[i] % mod;}}ll nCr(ll n, ll r){ll x = fact[n];ll y = inv_fact[n - r];ll z = inv_fact[r];if (n < r)return 0;if (n < 0 || r < 0)return 0;return x * ((y * z) % mod) % mod;}};// Graph.struct Edge{ll to;ll cost;Edge(ll to, ll cost) : to(to), cost(cost) {}bool operator>(const Edge &e) const{return cost > e.cost;}};struct Graph{vector<vector<Edge>> g;Graph(ll n){g.resize(n);}ll size(){return g.size();}void add_edge(ll from, ll to, ll cost = 1){g[from].push_back(Edge(to, cost));g[to].push_back(Edge(from, cost));}void add_directed_edge(ll from, ll to, ll cost = 1){g[from].push_back(Edge(to, cost));}pair<ll, vector<ll>> tree_diameter(){function<pair<ll, ll>(ll, ll)> dfs = [&](ll v, ll p) -> pair<ll, ll>{pair<ll, ll> res = {0, v};for (auto e : g[v]){if (e.to == p)continue;auto [d, u] = dfs(e.to, v);d += e.cost;if (res.first < d){res.first = d;res.second = u;}}return res;};auto [d, u] = dfs(0, -1);auto [d2, v] = dfs(u, -1);vector<ll> path;function<void(ll, ll, ll)> get_path = [&](ll v, ll p, ll u){if (v == u){path.push_back(v);return;}for (auto e : g[v]){if (e.to == p)continue;get_path(e.to, v, u);if (!path.empty()){path.push_back(v);return;}}};get_path(u, -1, v);return {d2, path};}vector<Edge> &operator[](ll v){return g[v];}};struct Dijkstra{vector<ll> dist;vector<ll> prev;// dijkstraを構築Dijkstra(Graph &g, ll s){ll n = g.size();dist.assign(n, INF);prev.assign(n, -1);priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;dist[s] = 0;pq.emplace(dist[s], s);while (!pq.empty()){auto p = pq.top();pq.pop();ll v = p.second;if (dist[v] < p.first)continue;for (auto &e : g[v]){if (dist[e.to] > dist[v] + e.cost){dist[e.to] = dist[v] + e.cost;prev[e.to] = v;pq.emplace(dist[e.to], e.to);}}}}// 最小コストを求めるll get_cost(ll to){return dist[to];}// 最短経路を求めるvector<ll> get_path(ll to){vector<ll> get_path;for (ll i = to; i != -1; i = prev[i]){get_path.push_back(i);}reverse(get_path.begin(), get_path.end());return get_path;}// 到達可能か調べるbool cango(ll to){return (dist[to] != INF);}};struct Bellman_ford{vector<ll> dist;vector<ll> prev;ll start;ll size;bool cl = false;// bellman_fordを構築Bellman_ford(Graph &g, ll s){start = s;ll n = g.size();size = n;dist.assign(n, INF);prev.assign(n, -1);vector<ll> counts(n);vector<bool> inqueue(n);queue<ll> q;dist[s] = 0;q.push(s);inqueue[s] = true;while (!q.empty()){ll from = q.front();q.pop();inqueue[from] = false;for (auto &e : g[from]){ll d = dist[from] + e.cost;if (d < dist[e.to]){dist[e.to] = d;prev[e.to] = from;if (!inqueue[e.to]){q.push(e.to);inqueue[e.to] = true;++counts[e.to];if (n < counts[e.to])cl = true;}}}}}// 最小コストを求めるll get_cost(ll to){return dist[to];}// 最短経路を求めるvector<ll> get_path(ll to){vector<ll> path;if (dist[to] != INF){for (ll i = to; i != -1; i = prev[i]){path.push_back(i);}reverse(path.begin(), path.end());}return path;}// 到達可能か調べるbool cango(ll to){return (dist[to] != INF);}// 閉路の有無を調べるbool closed(){return cl;}};struct Warshall_floyd{vector<vector<ll>> d;vector<vector<ll>> next;bool cl = false;// warshall_floydを構築Warshall_floyd(Graph &g){ll n = g.size();d.resize(n, vector<ll>(n, INF));next.resize(n, vector<ll>(n, -1));for (ll i = 0; i < n; i++){d[i][i] = 0;}for (ll i = 0; i < n; i++){for (auto e : g[i]){d[i][e.to] = e.cost;next[i][e.to] = e.to;}}for (ll k = 0; k < n; ++k){for (ll i = 0; i < n; ++i){for (ll j = 0; j < n; ++j){if (d[i][j] > d[i][k] + d[k][j]){d[i][j] = d[i][k] + d[k][j];next[i][j] = next[i][k];}}}}for (ll i = 0; i < n; i++){if (d[i][i] < 0){cl = true;break;}}}// 最小コストを求めるll get_cost(ll from, ll to){return d[from][to];}// 最短経路を求めるvector<ll> get_path(ll from, ll to){if (d[from][to] == INF)return {};vector<ll> path;for (ll at = from; at != to; at = next[at][to]){if (at == -1)return {};path.push_back(at);}path.push_back(to);return path;}// 到達可能か調べるbool cango(ll from, ll to){return d[from][to] != INF;}// 負の閉路の有無を調べるbool closed(){return cl;}};// String.struct Suffix_array{vector<ll> sa, rank, tmp;ll n;string base;// suffix_arrayを構築Suffix_array(const string s){n = s.size();base = s;sa.resize(n);rank.resize(n);tmp.resize(n);for (ll i = 0; i < n; i++){sa[i] = i;rank[i] = s[i];}for (ll k = 1; k < n; k *= 2){auto compare_sa = [&](ll i, ll j){if (rank[i] != rank[j])return rank[i] < rank[j];ll ri = (i + k < n) ? rank[i + k] : -1;ll rj = (j + k < n) ? rank[j + k] : -1;return ri < rj;};sort(sa.begin(), sa.end(), compare_sa);tmp[sa[0]] = 0;for (ll i = 1; i < n; i++){tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);}rank = tmp;}}// 部分文字列の個数を求めるll get_counts(string t){string u = t + "彁";ll num1, num2;{ll m = t.size();ll ng = -1, ok = n;while (ok - ng > 1){ll mid = (ng + ok) / 2;ll l = sa[mid];if (base.substr(l, m) >= t){ok = mid;}else{ng = mid;}}num1 = ok;}{ll m = u.size();ll ng = -1, ok = n;while (ok - ng > 1){ll mid = (ng + ok) / 2;ll l = sa[mid];if (base.substr(l, m) >= u){ok = mid;}else{ng = mid;}}num2 = ok;}return num2 - num1;}// make lcp arrayvector<ll> make_lcp(){vector<ll> lcp(n);for (ll i = 0; i < n; i++){rank[sa[i]] = i;}ll h = 0;lcp[0] = 0;for (ll i = 0; i < n; i++){if (rank[i] == n - 1){h = 0;continue;}ll j = sa[rank[i] + 1];while (i + h < n && j + h < n && base[i + h] == base[j + h]){h++;}lcp[rank[i]] = h;if (h > 0){h--;}}return lcp;}};// others.class Timer{public:Timer(ll ms) : duration(ms), start_time(steady_clock::now()) {}bool isTimeOver() const{auto current_time = steady_clock::now();auto elapsed = duration_cast<milliseconds>(current_time - start_time).count();return elapsed >= duration;}private:ll duration;steady_clock::time_point start_time;};class FunctionalGraph{private:const ll V;ll loop_id;vector<ll> nx;void make_loop(const ll st, ll nw, vector<ll> &vec){while (nx[nw] != st){vec.push_back(nx[nw]);visit[nx[nw]] = loop_id;nw = nx[nw];}}ll dfs(ll u, vector<ll> &vec){visit[u] = -loop_id;ll v = nx[u];if (visit[v] == -loop_id){vec.push_back(u), vec.push_back(v);visit[u] = visit[v] = loop_id;make_loop(u, v, vec);loop_id++;return 0;}else if (visit[v] == 0){const ll res = dfs(v, vec);if (res == 0)return 0;elsereturn visit[u] = res;}return visit[u] = (visit[v] > 0 ? -visit[v] : visit[v]);}void make_graph(){graph.resize(V);for (ll i = 0; i < V; i++){if (visit[i] < 0)graph[nx[i]].push_back(i);}}public:vector<ll> visit;vector<vector<ll>> loop, graph;FunctionalGraph(const ll node_size): V(node_size), loop_id(1), nx(V, 0), visit(V, 0) {}void add_edge(ll u, ll v){nx[u] = v;if (u == nx[u])visit[u] = loop_id++, loop.push_back({u});}void solve(){for (ll i = 0; i < V; i++){if (visit[i] == 0){vector<ll> vec;dfs(i, vec);if (!vec.empty())loop.push_back(move(vec));}}}};void print2DArr(vector<vector<ll>> &arr){for (auto &a : arr){for (auto &b : a){cout << b << " ";}cout << endl;}cout << endl;}string encode(ll n){string res = "";while (n){n--;res = ALPHABET[n % 26] + res;n /= 26;}return res;}ll decode(string s){ll res = 0;for (char c : s){res = res * 26 + c - 'A' + 1;}return res;}ll digit_sum(ll n){ll sum = 0;while (n > 0){sum += n % 10;n /= 10;}return sum;}ll non_mod_ncr(ll n, ll r){ll res = 1;for (ll i = 0; i < r; i++){res *= (n - i);}for (ll i = 0; i < r; i++){res /= (i + 1);}return res;}int rand_int(int a, int b){return a + rand() % (b - a + 1);}int main(){string s;cin >> s;vector<ll> cnt(26, 0);rep(i, s.size()) cnt[s[i] - 'a']++;string Y = "yukari";string A = "akari";string X = "yuzukizu";vector<ll> cntY(26, 0), cntA(26, 0), cntX(26, 0);rep(i, Y.size()) cntY[Y[i] - 'a']++;rep(i, A.size()) cntA[A[i] - 'a']++;rep(i, X.size()) cntX[X[i] - 'a']++;ll ansY = INF;rep(i, 26){if (cntY[i] == 0)continue;chmin(ansY, cnt[i] / cntY[i]);}ll ansA = INF;rep(i, 26){if (cntA[i] == 0)continue;chmin(ansA, cnt[i] / cntA[i]);}ll ansX = INF;rep(i, 26){if (cntX[i] == 0)continue;chmin(ansX, cnt[i] / cntX[i]);}cout << ansY << " " << ansA << " " << ansX << endl;return 0;}