#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define _USE_MATH_DEFINES #include #include #include #pragma intrinsic(_umul128) using namespace std; using namespace atcoder; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef pair pld; typedef pair pdd; typedef pair pdl; typedef pair pic; typedef vector vl; typedef vector vpll; typedef vector vi; typedef vector table; typedef priority_queue, greater> llgreaterq; typedef priority_queue, greater> pllgreaterq; typedef priority_queue, vector>, greater>> plpllgreaterq; typedef priority_queue, greater> vigreaterq; typedef priority_queue, greater> vlgreaterq; typedef vector mat; typedef vector thd; template using tuple3q = priority_queue, vector>, greater>>; template using tuple4q = priority_queue, vector>, greater>>; template using tuple5q = priority_queue, vector>, greater>>; int dx[] = { -1,0,1,0 }; int dy[] = { 0,1,0,-1 }; #define bit(x,v) ((ll)x << v) #define rep(x,n) for(ll x = 0;x < n;x++) #define rep2(x,f,v) for(ll x=f;x 0) #define next(i) i++;i%=2 #define Len size() #define psp(a,b) push_back(make_pair(a,b)) #define psp2(a,b) push(make_pair(a,b)) #define cini(a) a; cin >> a #define infa(a,b) (a + b) % INF #define infm(a,b) (a * b) % INF #define infd(a,b) (a * INFinv(b)) % INF #define infs(a,b) (a + INF - inff(b)) % INF #define inf(a) (a) %= INF #define inff(a) ((a + INF) % INF) #define No cout << "No" << endl #define Yes cout << "Yes" << endl #define NO cout << "NO" << endl #define YES cout << "YES" << endl #define errm1 pln(-1);return; #define smal -(ll)1000000009*1000000009 #define big (ll)1000000009*1000000009 #define frontpop(q) q.front();q.pop() #define toppop(q) q.top();q.pop() #define arr(a,s) a[s]; all0(a); #define nxt(cu) (cu+1) % 2 #define chkover(x,y,h,w) (x<0||y<0||x>=h||y>=w) #define psb(v) ll value;cin>>value;v.push_back(value); #define lower_b(v,p) lower_bound(all(v), p) ll n, m; bool chmin(ll& a, ll b) { if (a > b) { a = b; return 1; } return 0; } ll INF = 1000000007; const int MAX = 2000010; void cout2(ll val) { if (val >= big) { pln(-1); } else { pln(val); } } string padleft(string x, ll dig, char c) { ll si = x.size(); for (ll i = 0; i < dig - si; i++) { x = c + x; } return x; } long long fac[MAX], finv[MAX], inv[MAX]; void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++) { fac[i] = fac[i - 1] * i % INF; inv[i] = INF - inv[INF % i] * (INF / i) % INF; finv[i] = finv[i - 1] * inv[i] % INF; } } // 二項係数計算 long long COM(int n, int k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % INF) % INF; } ll getpow(ll b, ll x, ll md) { ll t = b % md; ll res = 1; while (x > 0) { if (x & 1) { res *= t; res %= md; } x >>= 1; t *= t; t %= md; } return res % md; } ll getpow(ll b, ll x) { return getpow(b, x, INF); } /// 素数を法とする場合 ll modinv(ll x) { return getpow(x, INF - 2); } ll extgcd(ll a, ll b, ll& x, ll& y) { ll d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } /// /// 素数を法としない場合 /// /// /// /// ll modinv(ll a, ll m) { ll x, y; extgcd(a, m, x, y); return (m + x % m) % m; } ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } std::mt19937 mt; std::uniform_int_distribution<> rand100; void init_random(ll mi, ll ma) { std::random_device rnd; // 非決定的な乱数生成器を生成 mt = std::mt19937(rnd()); // メルセンヌ・ツイスタの32ビット版、引数は初期シード値 rand100 = std::uniform_int_distribution<>(mi, ma); } ll getrand() { return rand100(mt); } class mint { public: long long x = 0; mint(ll x = 0) { this->x = (x % INF + INF) % INF; } mint operator-() const { return mint(-x); } mint& operator+=(const mint& a) { if ((x += a.x) >= INF) x -= INF; return *this; } mint& operator-=(const mint& a) { if ((x += INF - a.x) >= INF) x -= INF; return *this; } mint& operator*=(const mint& a) { (x *= a.x) %= INF; return *this; } mint operator+(const mint& a) const { mint res(*this); return res += a; } mint operator-(const mint& a) const { mint res(*this); return res -= a; } mint operator*(const mint& a) const { mint res(*this); return res *= a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t & 1) a *= *this; return a; } // for prime INF mint inv() const { return pow(INF - 2LL); } mint& operator/=(const mint& a) { return (*this) *= a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res /= a; } friend ostream& operator<<(ostream& os, const mint& m) { os << m.x; return os; } }; typedef vector vml; typedef vector matm; // Union find vl pr; vl lank; vl udpt; void uini(int _n) { _n++; // 一個拡張しておく pr = vl(_n + 1); lank = vl(_n + 1); udpt = vl(_n + 1, 0); for (ll i = 0; i <= _n; i++) { pr[i] = i; lank[i] = 1; } } int parent(int x) { if (x == pr[x]) return x; auto paren = parent(pr[x]); udpt[x] = udpt[paren] + 1; return pr[x] = paren; } int same(int x, int y) { return parent(x) == parent(y); } bool unit(int x, int y) { int px = parent(x); int py = parent(y); if (px == py) return false; if (lank[py] <= lank[px]) { pr[py] = px; lank[px] += lank[py]; } else { pr[px] = py; lank[py] += lank[px]; } return true; } bool unitm(int x, int y) { int px = parent(x); int py = parent(y); if (px == py) return false; if (lank[py] < lank[px]) { pr[py] = px; lank[px] += lank[py]; } else { pr[px] = py; lank[py] += lank[px]; } return true; } /// /// 数字の小さい方を親にするように処理 /// /// /// /// bool unitlow(int x, int y) { int px = parent(x); int py = parent(y); if (px == py) return false; if (py < px) { pr[py] = px; lank[px] += lank[py]; } else { pr[px] = py; lank[py] += lank[px]; } return true; } ll wit[500010]; map mp[100010]; ll parent2(ll x) { if (x == pr[x]) return x; // 元々の親から変わっている時、wit[pr[x]]には親からの距離が入っている // 同じところを二度通らないので大丈夫なはず ll o = pr[x]; pr[x] = parent2(o); wit[x] += wit[o]; // 親の重みを足す return pr[x]; } int same2(int x, int y) { return parent2(x) == parent2(y); } bool relate(int x, int y, int v) { auto px = parent2(x); auto py = parent2(y); // 自分の距離が取れる ll xd = wit[x]; ll yd = wit[y]; // ↑のydにvを足した値とxdを比較する // yd+v> xdであれば、pyが親となる // yの直接の親はxとしてしまう? // wit[y] = v; if (px == py) return false; if (xd + v > yd) { pr[py] = px; wit[py] = xd + v - yd; // 親同士の距離を入れておく } else { pr[px] = py; wit[px] = yd - (xd + v); } return true; } int H; int left(int i) { return i * 2 + 1; } int right(int i) { return i * 2 + 2; } class edge { public: int from, to, i; ll val; ll cap, rev, icap; edge() {} edge(ll to) : to(to) {} edge(ll to, ll i) : to(to), i(i) {} edge(ll from, ll to, ll val) : from(from), to(to), val(val) {} void flowEdge(ll _to, ll _cap, ll _rev) { to = _to; cap = _cap; icap = _cap; rev = _rev; } }; typedef vector> vve; class LCA { private: vector> v; vector> parent; vector depth; ll root; void dfs(int n, int m, int d) { parent[0][n] = m; depth[n] = d; for (auto x : v[n]) { if (x.to != m) dfs(x.to, n, d + 1); } } public: LCA() {} LCA(ll N, ll root, vector>& tree) { v = tree; this->root = root; parent = vector>(21, vector(N + 1, 0)); depth = vector(N + 1, 0); dfs(root, -1, 0); for (int j = 0; j + 1 < 20; j++) { for (int i = 1; i <= N; i++) { if (parent[j][i] < 0) parent[j + 1][i] = -1; else parent[j + 1][i] = parent[j][parent[j][i]]; } } } int lca(int n, int m) { if (depth[n] > depth[m]) swap(n, m); if (n == root) return root; for (int j = 0; j < 20; j++) { if ((depth[m] - depth[n]) >> j & 1) m = parent[j][m]; } if (n == m) return n; for (int j = 19; j >= 0; j--) { if (parent[j][n] != parent[j][m]) { n = parent[j][n]; m = parent[j][m]; } } return parent[0][n]; } int dep(int n) { return depth[n]; } }; ll k; int _rank[1010]; int temp[1010]; bool compare_sa(int i, int j) { if (_rank[i] != _rank[j]) return _rank[i] < _rank[j]; else { int ri = i + k <= n ? _rank[i + k] : -1; int rj = j + k <= n ? _rank[j + k] : -1; return ri < rj; } } void construct_sa(string S, int* sa) { n = S.length(); for (ll i = 0; i <= n; i++) { sa[i] = i; _rank[i] = i < n ? S[i] : -1; } for (k = 1; k <= n; k *= 2) { sort(sa, sa + n + 1, compare_sa); // saはソート後の接尾辞の並びになっている、rankは元の位置のindexを保持したまま、更新されている。 // ピンとこなかった部分 temp[sa[0]] = 0; for (ll i = 1; i <= n; i++) { temp[sa[i]] = temp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); } for (ll i = 0; i <= n; i++) { _rank[i] = temp[i]; } } } bool contain(string S, int* sa, string T) { int a = 0, b = S.length(); // sa は 接尾辞が辞書順に並んでいる、入っているのはその位置のインデックス while (b - a > 1) { int c = (a + b) / 2; if (S.compare(sa[c], T.length(), T) < 0) a = c; else b = c; } return S.compare(sa[b], T.length(), T) == 0; } #define bit(x,v) ((ll)x << v) class BIT { static const int MAX_N = 500010; public: BIT() { memset(bit, 0, sizeof(bit)); } ll bit[MAX_N + 1], n; ll sum(int i) { ll s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(int i, int x) { while (i <= n) { bit[i] += x; i += i & -i; } } }; struct UnionFind { vector A; UnionFind(int n) : A(n, -1) {} int find(int x) { if (A[x] < 0) return x; return A[x] = find(A[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (A[x] > A[y]) swap(x, y); A[x] += A[y]; A[y] = x; } int ngroups() { int ans = 0; for (auto a : A) if (a < 0) ans++; return ans; } }; vector getp(ll n) { vector res; if (n % 2 == 0) { res.push_back(2); while (n % 2 == 0)n /= 2; } for (ll i = 3; i * i <= n; i += 2) { if (n % i == 0) { res.push_back(i); while (n % i == 0)n /= i; } } if (n != 1) res.push_back(n); return res; } vector getp2(ll n) { vector res; if (n % 2 == 0) { while (n % 2 == 0) { n /= 2; res.push_back(2); } } for (ll i = 3; i * i <= n; i += 2) { if (n % i == 0) { while (n % i == 0) { n /= i; res.push_back(i); } } } if (n != 1) res.push_back(n); return res; } vector getp3(ll n) { vector res; int si = 0; if (n % 2 == 0) { res.push_back(make_pair(2, 0)); while (n % 2 == 0) { n /= 2; res[si].second++; } si++; } for (ll i = 3; i * i <= n; i += 2) { if (n % i == 0) { res.push_back(make_pair(i, 0)); while (n % i == 0) { n /= i; res[si].second++; } si++; } } if (n != 1) { res.push_back(make_pair(n, 1)); } return res; } vector getDivisors(ll n) { vector res; res.push_back(1); if (1 < n) res.push_back(n); for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { res.push_back(i); if (n / i != i) res.push_back(n / i); } } vsort(res); return res; } struct ve { public: vector child; int _t = INF; ve(int t) :_t(t) {} ve(ve _left, ve _right) { _t = _left._t + _right._t; child.push_back(_left); child.push_back(_right); } bool operator<(const ve& t) const { return _t > t._t; } }; vector elas(ll n) { n++; vector r(n, 1); r[0] = 0; r[1] = 0; ll tw = 4; while (tw < n) { r[tw] = false; tw += 2; } ll th = 6; while (th < n) { r[th] = false; th += 3; } ll fv = 10; while (fv < n) { r[fv] = false; fv += 5; } for (ll i = 6; i * i < n; i += 6) { ll bf = i - 1; if (r[bf]) { ll ti = bf * 2; while (ti < n) { r[ti] = false; ti += bf; } } ll nx = i + 1; if (r[nx]) { ll ti = nx * 2; while (ti < n) { r[ti] = false; ti += nx; } } } return r; } bool isPrime(ll v) { for (ll i = 2; i * i <= v; i++) { if (v % i == 0) return false; } return true; } class SegTree { public: const static int MAX_N = 1000100; const static int DAT_SIZE = (1 << 20) - 1; int N, Q; int A[MAX_N]; ll MAX = big; ll data[DAT_SIZE], datb[DAT_SIZE]; void init(int _n) { N = 1; while (N < _n) N <<= 1; memset(data, 0, sizeof(data)); memset(datb, 0, sizeof(datb)); } void init(int _n, ll iv) { N = 1; while (N < _n) N <<= 1; rep(i, DAT_SIZE) { data[i] = iv; datb[i] = iv; } } void initRMQ(int _n) { N = 1; while (N < _n) N *= 2; // 全ての値をbigに rep(i, 2 * N - 1) data[i] = MAX; } void updateRMQ(int k, ll a) { k += N - 1; data[k] = a; while (k > 0) { k = (k - 1) / 2; data[k] = min(data[k * 2 + 1], data[k * 2 + 2]); } } ll RMQ(int a, int b) { return queryRMQ(a, b + 1, 0, 0, N); } ll queryRMQ(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return MAX; // [a,b)が[l,r)を完全に含んでいれば if (a <= l && r <= b) return data[k]; // そうでなければ2つの子の最小値 // n=16 // 0,16→0,8 8,16 // 0,4 4,8 8,12 12,16 ll vl = queryRMQ(a, b, k * 2 + 1, l, (l + r) / 2); ll vr = queryRMQ(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } void add(int a, int b, int x) { add(a, b + 1, x, 0, 0, N); } void add(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { data[k] += x; } else if (l < b && a < r) { datb[k] += (min(b, r) - max(a, l)) * x; add(a, b, x, k * 2 + 1, l, (l + r) / 2); add(a, b, x, k * 2 + 2, (l + r) / 2, r); } } void change(int a, int b, int x) { change(a, b + 1, x, 0, 0, N); } void change(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { data[k] = x; } else if (l < b && a < r) { datb[k] = x; change(a, b, x, k * 2 + 1, l, (l + r) / 2); change(a, b, x, k * 2 + 2, (l + r) / 2, r); } } ll sum(int a, int b) { return sum(a, b + 1, 0, 0, N); } ll sum(int a, int b, int k, int l, int r) { if (b <= l || r <= a) { return 0; } if (a <= l && r <= b) { return data[k] * (r - l) + datb[k]; } ll res = (min(b, r) - max(a, l)) * data[k]; res += sum(a, b, k * 2 + 1, l, (l + r) / 2); res += sum(a, b, k * 2 + 2, (l + r) / 2, r); return res; } }; class LazySegTree { private: int N; vl node, lazy; public: void init(int _n) { N = 1; while (N < _n) N <<= 1; node.resize(2 * N, 0); lazy.resize(2 * N, 0); } // k 番目のノードについて遅延評価を行う void eval(int k, int l, int r) { // 遅延配列が空でない場合、自ノード及び子ノードへの // 値の伝播が起こる if (lazy[k] != 0) { node[k] += lazy[k]; // 最下段かどうかのチェックをしよう // 子ノードは親ノードの 1/2 の範囲であるため、 // 伝播させるときは半分にする if (r - l > 1) { lazy[2 * k + 1] += lazy[k] / 2; lazy[2 * k + 2] += lazy[k] / 2; } // 伝播が終わったので、自ノードの遅延配列を空にする lazy[k] = 0; } } void add(int a, int b, ll x) { addbody(a, b + 1, x); } void addbody(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; // k 番目のノードに対して遅延評価を行う eval(k, l, r); // 範囲外なら何もしない if (b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if (a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k, l, r); } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { addbody(a, b, x, 2 * k + 1, l, (l + r) / 2); addbody(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = node[2 * k + 1] + node[2 * k + 2]; } } ll getsum(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return 0; // 関数が呼び出されたら評価! eval(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r); return vl + vr; } ll getMax(int a, int b) { // 半開区間に変換 return getMaxBdy(a, b + 1); } ll getMaxBdy(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return -big; // 関数が呼び出されたら評価! eval(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getMaxBdy(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getMaxBdy(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } }; class LazySegTreeRMQ { private: int N; vl node, lazy; public: void init(int _n) { N = 1; while (N < _n) N <<= 1; node.resize(2 * N, 0); lazy.resize(2 * N, 0); } // k 番目のノードについて遅延評価を行う void eval(int k, int l, int r) { if (lazy[k] != 0) { node[k] = lazy[k]; if (r - l > 1) { lazy[2 * k + 1] = lazy[k]; lazy[2 * k + 2] = lazy[k]; } lazy[k] = 0; } } void evalAdd(int k, int l, int r) { if (lazy[k] != 0) { node[k] += lazy[k]; if (r - l > 1) { lazy[2 * k + 1] += lazy[k]; lazy[2 * k + 2] += lazy[k]; } lazy[k] = 0; } } void add(int a, int b, ll x) { addbody(a, b + 1, x); } void addbody(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; // k 番目のノードに対して遅延評価を行う evalAdd(k, l, r); // 範囲外なら何もしない if (b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if (a <= l && r <= b) { lazy[k] += x; evalAdd(k, l, r); } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { addbody(a, b, x, 2 * k + 1, l, (l + r) / 2); addbody(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = max(node[2 * k + 1], node[2 * k + 2]); } } void update(int a, int b, ll v) { updateBdy(a, b + 1, v); } void updateBdy(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; // k 番目のノードに対して遅延評価を行う eval(k, l, r); // 範囲外なら何もしない if (b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if (a <= l && r <= b) { if (x > node[k]) { lazy[k] = x; eval(k, l, r); } } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { updateBdy(a, b, x, 2 * k + 1, l, (l + r) / 2); updateBdy(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = max(node[2 * k + 1], node[2 * k + 2]); } } ll getMaxAdd(int a, int b) { // 半開区間に変換 return getMaxAddBdy(a, b + 1); } ll getMaxAddBdy(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return -big; // 関数が呼び出されたら評価! evalAdd(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getMaxAddBdy(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getMaxAddBdy(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } ll getMax(int a, int b) { // 半開区間に変換 return getMaxBdy(a, b + 1); } ll getMaxBdy(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return -big; // 関数が呼び出されたら評価! eval(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getMaxBdy(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getMaxBdy(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } }; class Segment; class Circle; class Point { public: double x, y; Point(double x = 0, double y = 0) :x(x), y(y) {} Point operator + (Point p) { return Point(x + p.x, y + p.y); } Point operator - (Point p) { return Point(x - p.x, y - p.y); } Point operator * (double a) { return Point(a * x, a * y); } Point operator / (double a) { return Point(x / a, y / a); } double abs() { return sqrt(norm()); } double norm() { return x * x + y * y; } bool operator < (const Point& p)const { return x != p.x ? x < p.x : y < p.y; } bool operator == (const Point& p) const { return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS; } // 内積 static double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; } // 外積 static double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; } static bool isOrthogonal(Point a, Point b) { return EQ(dot(a, b), 0.0); } static bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) { return isOrthogonal(a1 - a2, b1 - b2); } static bool isOrthogonal(Segment s1, Segment s2); static bool isPalallel(Point a, Point b) { return EQ(cross(a, b), 0.0); } static bool isPalallel(Point a1, Point a2, Point b1, Point b2) { return isPalallel(a1 - a2, b1 - b2); } static bool isPalallel(Segment s1, Segment s2); static const int COUNTER_CLOCKWISE = 1; static const int CLOCKWISE = -1; static const int ONLINE_BACK = 2; static const int ONLINE_FRONT = -2; static const int ON_SEGMENT = 0; static int ccw(Point p0, Point p1, Point p2) { // 線分はp0とp1でp2がどこにあるかを探る Point a = p1 - p0; Point b = p2 - p0; if (cross(a, b) > EPS) return COUNTER_CLOCKWISE; if (cross(a, b) < -EPS) return CLOCKWISE; if (dot(a, b) < -EPS) return ONLINE_BACK; if (a.norm() < b.norm()) return ONLINE_FRONT; return ON_SEGMENT; } // 交差しているか static bool intersect(Point p1, Point p2, Point p3, Point p4) { return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0); } static bool intersect(Segment s1, Segment s2); static Point project(Segment s, Point p); static Point reflect(Segment s, Point p); static Point getDistance(Point a, Point b) { return (a - b).abs(); } static double getDistanceLP(Segment s, Point p); static double getDistanceSP(Segment s, Point p); static double getDistance(Segment s1, Segment s2); static Point getIntersection(Segment s1, Segment s2); static pair crossPoints(Circle c, Segment s); static int contains(vector g, Point p) { int n = g.size(); bool x = false; rep(i, n) { Point a = g[i] - p, b = g[(i + 1) % n] - p; // 線の上に載っているか if (std::abs(cross(a, b)) < EPS && dot(a, b) < EPS) return 1; // pを基準として上下にあるか // または外積が正か?(→にあるか) if (a.y > b.y) swap(a, b); if (a.y < EPS && EPS < b.y && cross(a, b) > EPS) x = !x; } return x ? 2 : 0; } static vector andrewScan(vector s) { vector u, l; ll si = s.size(); if (si < 3) return s; sort(all(s)); u.push_back(s[0]); u.push_back(s[1]); l.push_back(s[si - 1]); l.push_back(s[si - 2]); for (int i = 2; i < si; i++) { for (int _n = u.size(); _n >= 2 && ccw(u[_n - 2], u[_n - 1], s[i]) > CLOCKWISE; _n--) { u.pop_back(); } u.push_back(s[i]); } for (int i = s.size() - 3; i >= 0; i--) { for (int _n = l.size(); _n >= 2 && ccw(l[_n - 2], l[_n - 1], s[i]) > CLOCKWISE; _n--) { l.pop_back(); } l.push_back(s[i]); } reverse(all(l)); for (int i = u.size() - 2; i >= 1; i--) { l.push_back(u[i]); } return l; } void get_cin() { cin >> x >> y; } static Point rotate(double r, Point p) { Point ret; ret.x = cos(r) * p.x - sin(r) * p.y; ret.y = sin(r) * p.x + cos(r) * p.y; return ret; } }; class Segment { public: Point p1, p2; Segment() {} Segment(Point p1, Point p2) :p1(p1), p2(p2) {} void get_cin() { cin >> p1.x >> p1.y >> p2.x >> p2.y; } Point p1tp2() { return p2 - p1; } Point p2tp1() { return p1 - p2; } double abs() { return (p2 - p1).abs(); } double norm() { return (p2 - p1).norm(); } }; // 直行 bool Point::isOrthogonal(Segment s1, Segment s2) { return EQ(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0); } // 平行 bool Point::isPalallel(Segment s1, Segment s2) { return EQ(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0); } // 交差しているか bool Point::intersect(Segment s1, Segment s2) { return intersect(s1.p1, s1.p2, s2.p1, s2.p2); } Point Point::project(Segment s, Point p) { Point base = s.p2 - s.p1; double r = Point::dot(p - s.p1, base) / base.norm(); return s.p1 + base * r; } Point Point::reflect(Segment s, Point p) { return (project(s, p) * 2) - p; } double Point::getDistanceLP(Segment s, Point p) { return std::abs(cross(s.p2 - s.p1, p - s.p1) / (s.p2 - s.p1).abs()); } double Point::getDistanceSP(Segment s, Point p) { if (dot(s.p2 - s.p1, p - s.p1) < 0.0) return (p - s.p1).abs(); if (dot(s.p1 - s.p2, p - s.p2) < 0.0) return (p - s.p2).abs(); return getDistanceLP(s, p); } double Point::getDistance(Segment s1, Segment s2) { if (intersect(s1, s2)) return 0.0; return min({ getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2) ,getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2) }); } Point Point::getIntersection(Segment s1, Segment s2) { // (s1.p1 - s2.p1).norm() auto bs = s1.p2 - s1.p1; auto n1 = s2.p1 - s1.p1; auto n2 = s2.p2 - s1.p1; auto c1 = std::abs(cross(n1, bs)) / bs.norm(); auto c2 = std::abs(cross(n2, bs)) / bs.norm(); return s2.p1 + (s2.p2 - s2.p1) * (c1 / (c1 + c2)); // c1:c2=t:1-t // c2t=(1-t)c1 // t/(1-t)=c1/(c1+c2) // } double arg(Point p) { return atan2(p.y, p.x); } Point polar(double a, double r) { return Point(cos(r) * a, sin(r) * a); } class Circle { public: Point c; double r; Circle(Point c = Point(), double r = 0.0) : c(c), r(r) {} void get_cin() { cin >> c.x >> c.y >> r; } static pair getCrossPoints(Circle c1, Circle c2) { double d = (c1.c - c2.c).abs(); // 中心点どうしの距離 double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d)); double t = arg(c2.c - c1.c); return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)); } }; pair Point::crossPoints(Circle c, Segment s) { auto pp = project(s, c.c); auto f = (pp - c.c).norm(); auto mu = sqrt(c.r * c.r - f); // 単位ベクトル auto e = s.p1tp2() / s.p1tp2().abs(); return make_pair(pp + e * mu, pp - e * mu); } ll divRm(string s, ll x) { ll r = 0; for (ll i = 0; i < s.size(); i++) { r *= 10; r += s[i] - '0'; r %= x; } return r; } ll cmbi(ll x, ll b) { ll res = 1; for (size_t i = 0; i < b; i++) { res *= x - i; res %= INF; res *= inv[b - i]; res %= INF; } return res; } ll digsum(ll x) { ll res = 0; while (x > 0) { res += x % 10; x /= 10; } return res; } bool check_parindrome(string s) { int n = s.size(); rep(i, n / 2) { if (s[i] != s[n - i - 1]) { return false; } } return true; } ll npr(ll n, ll r) { if (r == 0) return 1; return inff(fac[n] * modinv(fac[n - r])); } vl zalgo(string s) { ll c = 0; vl a(s.size()); ll si = s.size(); rep2(i, 1, s.size()) { if (i + a[i - c] < c + a[c]) { a[i] = a[i - c]; } else { ll j = max(0LL, a[c] - (i - c)); while (i + j < si && s[j] == s[i + j]) { j++; } a[i] = j; c = i; } } a[0] = s.size(); return a; } // 数値文字列の除算 string divStrNum(string s, ll v) { ll si = s.size(); ll val = 0; string res = ""; for (ll i = 0; i < si; i++) { val *= 10; val += s[i] - '0'; ll add = val / v; val %= v; if (add == 0 && res == "") continue; res += add + '0'; } if (res == "") return "0"; return res; } // 数値文字列の減算 string difStrNum(string s, ll v) { ll si = s.size(); bool dec = false; for (ll i = si - 1; i >= 0; i--) { if (v == 0) break; ll t = v % 10; v /= 10; ll u = (s[i] - '0'); if (dec) { if (u == 0) { s[i] = 9 - t; dec = true; continue; } u--; } if (u < t) { s[i] = 10 - (t - u); dec = true; } else { s[i] -= t; dec = false; } } return s; } // 数値文字列を1減らした数 string decStrNum(string s) { ll si = s.size(); for (int i = si - 1; i >= 0; i--) { if (s[i] == '0') { s[i] = '9'; continue; } s[i] = s[i] - 1; break; } return s; } void dateCal(int x) { int lp = x / 7; string date[] = { "月曜日","火曜日","水曜日","木曜日","金曜日","土曜日","日曜日" }; rep(i, 7) { int st = i; rep(j, lp) { cout << "\t" << date[i] << x << "-" << st << "\t" << "NULL" << "\t" << x << "\t" << st << "\t" << 0 << endl; st += 7; } } } // 行列べき乗計算 mat mul(mat& A, mat& B) { ll as = A.size(); ll bs = B.size(); mat C(A.size(), vl(B[0].size())); rep(i, as) { rep(t, bs) { ll bz = B[0].size(); rep(j, bz) { C[i][j] = inff(C[i][j] + A[i][t] * B[t][j]); } } } return C; } mat pow(mat A, ll x) { mat B(A.size(), vl(A.size())); rep(i, A.size()) { B[i][i] = 1; } while (x > 0) { if (x & 1)B = mul(B, A); A = mul(A, A); x >>= 1; } return B; } class dinic { public: vve G; vl level; vl iter; dinic(int _n) : dinic(vve(_n + 1)) { } dinic(vve g) { G = g; level = vl(g.size()); iter = vl(g.size()); } void add_edge(ll from, ll to, ll cap) { auto e1 = edge(); auto e2 = edge(); e1.flowEdge(to, cap, G[to].size()); G[from].push_back(e1); e2.flowEdge(from, 0, G[from].size() - 1); G[to].push_back(e2); } void bfs(ll s) { fill(all(level), -1); queue q; level[s] = 0; q.push(s); while (!q.empty()) { ll v = frontpop(q); for (auto e : G[v]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } ll dfs(ll v, ll t, ll f) { if (v == t) return f; for (ll& i = iter[v]; i < G[v].size(); i++) { edge& e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { ll d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } ll max_flow(ll s, ll t) { ll flow = 0; for (;;) { bfs(s); if (level[t] < 0) return flow; fill(all(iter), 0); ll f; while ((f = dfs(s, t, big)) > 0) { flow += f; } } } }; const ull BS = 1000000007; // aはbに含まれているか? bool rolling_hash(string a, string b) { int al = a.size(), bl = b.size(); if (al > bl) return false; // BSのal乗を計算 ull t = 1; rep(i, al)t *= BS; // aとbの最初のal文字に関するハッシュ値を計算 ull ah = 0, bh = 0; rep(i, al) ah = ah * BS + a[i]; rep(i, al) bh = bh * BS + b[i]; // bの場所を一つずつ進めながらハッシュ値をチェック for (ll i = 0; i + al <= bl; i++) { if (ah == bh) return true; if (i + al < bl)bh = bh * BS + b[i + al] - b[i] * t; } return false; } mat sans(9, vl(9, -1)); bool srec(ll x, ll y) { if (x == 9) return true; vl use(10, 0); rep(i, 9) { if (sans[i][y] == -1) continue; use[sans[i][y]] = 1; } rep(j, 9) { if (sans[x][j] == -1) continue; use[sans[x][j]] = 1; } ll px = x % 3; ll py = y % 3; ll tx = x - px + 3; ll ty = y - py + 3; rep2(i, x - px, tx) { rep2(j, y - py, ty) { if (sans[i][j] == -1) continue; use[sans[i][j]] = 1; } } ll nx, ny; if (y == 8) { nx = x + 1; ny = 0; } else { nx = x; ny = y + 1; } if (sans[x][y] != -1) { if (srec(nx, ny)) { return true; } return false; } rep2(i, 1, 10) { if (use[i]) continue; sans[x][y] = i; if (srec(nx, ny)) { return true; } sans[x][y] = -1; } return false; } void sudoku() { vector tb; rep(i, 9) { string s; cin >> s; tb.push_back(s); rep(j, 9) { if (tb[i][j] != '.') { sans[i][j] = tb[i][j] - '0'; } } } srec(0, 0); rep(i, 9) { rep(j, 9) { cout << sans[i][j]; } cout << endl; } } mint ncr(ll n, ll r) { mint v = 1; rep(i, r) { v *= (n - i); v /= (i + 1); } return v; } ll sq(ll x) { return x * x; } // ここまでライブラリ // ここからコード void solv() { cin >> n; string s; cin >> s; vl t(200, 0); rep(i, n) { t[s[i]]++; } char y = 'y', u = 'u', k = 'k', i = 'i'; for (char c = u + 2; c < y; c++) t[c] += t[c - 1]; for (char c = k + 2; c < u; c++) t[c] += t[c - 1]; for (char c = i + 2; c < k; c++) t[c] += t[c - 1]; for (char c = 'b'; c < i; c++) t[c] += t[c - 1]; ll res = 0; while (true) { if (t['z'] > 0) { t['z']--; res++; continue; } if (t[y] > 0 && t[y - 1] > 0) { t[y]--; t[y - 1]--; res++; continue; } if (t[y] > 0 && t[u]>0 && t[u - 1] > 0) { t[y]--; t[u]--; t[u - 1]--; res++; continue; } if (t[y] > 0 && t[u] > 0 &&t[k]>0 && t[k - 1] > 0) { t[y]--; t[u]--; t[k]--; t[k - 1]--; res++; continue; } if (t[y] > 0 && t[u] > 0 && t[k] > 0&&t[i]>0 && t[i - 1] > 0) { t[y]--; t[u]--; t[k]--; t[i]--; t[i - 1]--; res++; continue; } if (t[y] > 0 && t[u] > 0 && t[k] > 0 && t[i] > 1) { t[y]--; t[u]--; t[k]--; t[i]-=2; res++; continue; } if (t[y] > 0 && t[u] > 0 && t[k] > 1) { t[y]--; t[u]--; t[k]-=2; res++; continue; } if (t[y] > 0 && t[u] > 1) { t[y]--; t[u]-=2;res++; continue; } if (t[y] > 1) { t[y]-=2;res++; continue; } break; } pln(res); } int main() { cin.tie(0); ios::sync_with_stdio(false); INF = 998244353; COMinit(); solv(); return 0; }