結果
| 問題 | No.2997 Making YuzuKizu |
| ユーザー |
 ルク
|
| 提出日時 | 2024-12-04 17:56:21 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 32,070 bytes |
| コンパイル時間 | 12,965 ms |
| コンパイル使用メモリ | 465,656 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-12-21 23:34:50 |
| 合計ジャッジ時間 | 10,952 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 5 ms
5,248 KB |
| testcase_02 | AC | 5 ms
5,248 KB |
| testcase_03 | AC | 5 ms
5,248 KB |
| testcase_04 | AC | 2 ms
5,248 KB |
| testcase_05 | AC | 2 ms
5,248 KB |
| testcase_06 | AC | 2 ms
5,248 KB |
| testcase_07 | AC | 2 ms
5,248 KB |
| testcase_08 | AC | 2 ms
5,248 KB |
| testcase_09 | AC | 2 ms
5,248 KB |
| testcase_10 | AC | 3 ms
5,248 KB |
| testcase_11 | AC | 2 ms
5,248 KB |
| testcase_12 | AC | 2 ms
5,248 KB |
| testcase_13 | AC | 2 ms
5,248 KB |
| testcase_14 | AC | 2 ms
5,248 KB |
| testcase_15 | AC | 2 ms
5,248 KB |
| testcase_16 | AC | 2 ms
5,248 KB |
| testcase_17 | AC | 2 ms
5,248 KB |
ソースコード
#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 array
vector<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;
else
return 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;
}