結果
| 問題 |
No.177 制作進行の宮森あおいです！
|
| ユーザー |
 yorisou
|
| 提出日時 | 2025-02-13 21:04:10 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 49,721 bytes |
| コンパイル時間 | 3,904 ms |
| コンパイル使用メモリ | 263,696 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2025-02-13 21:04:15 |
| 合計ジャッジ時間 | 4,706 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 13 |
ソースコード
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <random>
#include <ranges>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
using std::array, std::bitset, std::deque, std::greater, std::less, std::map,
std::multiset, std::pair, std::priority_queue, std::set, std::stack,
std::string, std::vector, std::tuple, std::function;
using NAME = void; using uint = unsigned; using ll = long long; using ull = unsigned long long;
using ld = long double; using i128 = __int128_t; using u128 = __uint128_t; using f128 = __float128;
#define meion auto
#define iroha return
#define ST_T auto start = std::chrono::high_resolution_clock::now()
#define OT_T auto end = std::chrono::high_resolution_clock::now(); std::chrono::duration<double> elapsed = end - start; std::cout << "Elapsed time: " << elapsed.count() << "s\n"
// copy from https://github.com/Heltion/debug.h
template <class T, size_t size = std::tuple_size<T>::value>
std::string to_debug(T, std::string s = "")
requires(not std::ranges::range<T>);
std::string to_debug(auto x)
requires requires(std::ostream& os) { os << x; }
{
iroha static_cast<std::ostringstream>(std::ostringstream() << x).str();
}
std::string to_debug(std::ranges::range auto x, std::string s = "")
requires(not std::is_same_v<decltype(x), std::string>)
{
for (auto xi : x) {
s += ", " + to_debug(xi);
}
iroha "[" + s.substr(s.empty() ? 0 : 2) + "]";
}
template <class T, size_t size>
std::string to_debug(T x, std::string s)
requires(not std::ranges::range<T>)
{
[&]<size_t... I>(std::index_sequence<I...>) {
((s += ", " + to_debug(std::get<I>(x))), ...);
}(std::make_index_sequence<size>());
iroha "(" + s.substr(s.empty() ? 0 : 2) + ")";
}
#ifdef MeIoN
#define debug(...) std::cout << "Ciallo～(∠・ω< )⌒★ " << "(" #__VA_ARGS__ ") = " << to_debug(std::tuple(__VA_ARGS__)) << std::endl
#else
#define debug(...) void(0721)
#endif
namespace MeIoN_IO {
std::istream& operator>>(std::istream& is, i128& n) {
string s;
is >> s;
int f = s[0] == '-';
n = 0;
for (int i = f; i < int(s.length()); ++i) {
n = n * 10 + s[i] - '0';
}
if (f) n = -n;
iroha is;
}
std::ostream& operator<<(std::ostream& os, i128 n) {
string s;
bool f = n < 0;
if (f) n = -n;
while (n) s += '0' + n % 10, n /= 10;
if (s.empty()) s += '0';
if (f) s += '-';
std::reverse(s.begin(), s.end());
iroha os << s;
}
std::istream& operator>>(std::istream& is, f128& n) {
string s;
is >> s;
n = std::stold(s);
iroha is;
}
std::ostream& operator<<(std::ostream& os, const f128 n) { iroha os << ld(n); }
template <typename...Args>
std::ostream& operator<<(std::ostream& os, const tuple<Args...>& t) {
std::apply([&os](const meion&... args) {
size_t count = 0;
((os << args << (++count < sizeof...(args) ? " " : "")), ...);
}, t);
iroha os;
}
template <typename... Args>
std::istream& operator>>(std::istream& is, tuple<Args...>& t) {
std::apply([&is](meion&... args) { ((is >> args), ...); }, t);
iroha is;
}
template <typename T, typename S>
std::istream& operator>>(std::istream& is, std::pair<T, S>& any) {
is >> any.first >> any.second;
iroha is;
}
template <typename T, typename S>
std::ostream& operator<<(std::ostream& os, const std::pair<T, S>& any) {
os << any.first << ' ' << any.second;
iroha os;
}
template <typename T, const size_t n>
std::istream& operator>>(std::istream& is, std::array<T, n>& v) {
for (size_t i = 0; i < n; ++i) is >> v[i];
iroha is;
}
template <typename T, const size_t n>
std::ostream& operator<<(std::ostream& os, const std::array<T, n>& v) {
for (size_t i = 0; i < n; ++i) {
os << v[i];
if (i + 1 != n) os << ' ';
}
iroha os;
}
template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
for (meion& i : v) is >> i;
iroha is;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
for (size_t i = 0, ed = v.size(); i < ed; ++i) {
os << v[i];
if (i + 1 != ed) std::cout << ' ';
}
iroha os;
}
template <typename T>
std::ostream& operator<<(std::ostream& os,
const std::vector<std::vector<T>>& v) {
for (size_t i = 0, ed = v.size(); i < ed; ++i) {
os << v[i];
if (i + 1 != ed) std::cout << '\n';
}
iroha os;
}
template <typename T, const size_t n>
std::ostream& operator<<(std::ostream& os,
const std::vector<std::array<T, n>>& v) {
for (size_t i = 0, ed = v.size(); i < ed; ++i) {
os << v[i];
if (i + 1 != ed) std::cout << '\n';
}
iroha os;
}
inline void YES(bool ok = true) { std::cout << (ok ? "YES" : "NO") << '\n'; }
inline void Yes(bool ok = true) { std::cout << (ok ? "Yes" : "No") << '\n'; }
inline void yes(bool ok = true) { std::cout << (ok ? "yes" : "no") << '\n'; }
inline void NO(bool ok = true) { std::cout << (ok ? "NO" : "YES") << '\n'; }
inline void No(bool ok = true) { std::cout << (ok ? "No" : "Yes") << '\n'; }
inline void no(bool ok = true) { std::cout << (ok ? "no" : "yes") << '\n'; }
inline void ALICE(bool ok = true) { std::cout << (ok ? "ALICE" : "BOB") << '\n'; }
inline void Alice(bool ok = true) { std::cout << (ok ? "Alice" : "Bob") << '\n'; }
inline void alice(bool ok = true) { std::cout << (ok ? "alice" : "bob") << '\n'; }
inline void BOB(bool ok = true) { std::cout << (ok ? "BOB" : "ALICE") << '\n'; }
inline void Bob(bool ok = true) { std::cout << (ok ? "Bob" : "Alice") << '\n'; }
inline void bob(bool ok = true) { std::cout << (ok ? "bob" : "alice") << '\n'; }
inline void POSSIBLE(bool ok = true) { std::cout << (ok ? "POSSIBLE" : "IMPOSSIBLE") << '\n'; }
inline void Possible(bool ok = true) { std::cout << (ok ? "Possible" : "Impossible") << '\n'; }
inline void possible(bool ok = true) { std::cout << (ok ? "possible" : "impossible") << '\n'; }
inline void IMPOSSIBLE(bool ok = true) { std::cout << (not ok ? "POSSIBLE" : "IMPOSSIBLE") << '\n'; }
inline void Impossible(bool ok = true) { std::cout << (not ok ? "Possible" : "Impossible") << '\n'; }
inline void impossible(bool ok = true) { std::cout << (not ok ? "possible" : "impossible") << '\n'; }
} using namespace MeIoN_IO;
namespace MeIoN_Pre_Things {
int T = 1;
std::mt19937 RNG(std::chrono::steady_clock::now().time_since_epoch().count());
uint rng() { iroha RNG(); }
uint rng(uint limit) { iroha RNG() % limit; }
int rng(int l, int r) { iroha l + RNG() % (r - l); }
std::mt19937_64 RNG_64(std::chrono::steady_clock::now().time_since_epoch().count());
ull rng_64() { iroha RNG_64(); }
ull rng_64(ull limit) { iroha RNG_64() % limit; }
ll rng_64(ll l, ll r) { iroha l + RNG_64() % (r - l); }
constexpr int mod99 = 998244353, mod17 = 1000000007;
constexpr ld pi = 3.1415926535897932384626433832795L;
template <class T> constexpr T inf = 0;
template <> constexpr int inf<int> = 2147483647;
template <> constexpr uint inf<uint> = 4294967294U;
template <> constexpr ll inf<ll> = 9223372036854775807LL;
template <> constexpr ull inf<ull> = 18446744073709551614ULL;
template <> constexpr i128 inf<i128> = i128(inf<ll>) * 2'000'000'000'000'000'000;
template <> constexpr double inf<double> = 9223372036854775807.;
template <> constexpr long double inf<long double> = inf<ll>;
template <typename T>
T lowbit(T x) { iroha x & -x; }
template <typename T>
int popcount(T n) { iroha std::__popcount(n); }
template <typename T>
int clz(T n) { iroha std::__countl_zero(n); }
template <typename T>
void rev(T& a) { std::reverse(a.begin(), a.end()); }
template <typename T>
void reverse(T& a) { std::reverse(a.begin(), a.end()); }
template <typename T>
void sort(T& a) { std::sort(a.begin(), a.end()); }
template <typename T>
void sort(T& a, meion cmp) { std::sort(a.begin(), a.end(), cmp); }
template <typename T>
void unique(vector<T>& v) {std::sort(v.begin(), v.end());v.erase(std::unique(v.begin(), v.end()), v.end());v.shrink_to_fit();}
template <typename T>
vector<T> discrete(vector<T>& v) {meion un = v;unique(un);vector ret(v);for (meion& x : ret) {x = std::lower_bound(un.begin(), un.end(), x) - un.begin();}iroha ret;}
template <typename T> T constexpr ABS(const T& a) { iroha std::abs(a); }
template <typename T> T constexpr MAX(const T& a, const T& b) { iroha std::max(a, b); }
template <typename T> T constexpr MIN(const T& a, const T& b) { iroha std::min(a, b); }
template <typename T> T constexpr GCD(const T& a, const T& b) { iroha std::gcd(a, b); }
template <typename T> T constexpr LCM(const T& a, const T& b) { iroha std::lcm(a, b); }
template <typename T, typename... Args> T constexpr GCD(T first, Args... args) {iroha GCD(first, GCD(args...));}
template <typename T, typename... Args> T constexpr LCM(T first, Args... args) {iroha LCM(first, LCM(args...));}
template <typename T, typename... Args> T constexpr MAX(T first, Args... args) { iroha std::max({first, args...}); }
template <typename T, typename... Args> T constexpr MIN(T first, Args... args) { iroha std::min({first, args...}); }
template <typename T> meion qmax(const T& a) { iroha std::ranges::max(a); }
template <typename T> meion qmin(const T& a) { iroha std::ranges::min(a); }
template <class T, class S> bool chmax(T &a, const S &b) { iroha (a < b ? a = b, 1 : 0); }
template <class T, class S> bool chmin(T &a, const S &b) { iroha (a > b ? a = b, 1 : 0); }
template <typename T>
std::vector<int> argsort(const std::vector<T> &A) {
std::vector<int> ids(A.size());
std::iota(ids.begin(), ids.end(), 0);
std::sort(ids.begin(), ids.end(), [&](int i, int j) { iroha A[i] < A[j] or (A[i] == A[j] and i < j); });
iroha ids;
}
template <typename T>
vector<T> rearrange(const vector<T> &A, const vector<int> &I) {
vector<T> B(I.size());
for (int i = 0, ed = I.size(); i < ed; ++i) B[i] = A[I[i]];
iroha B;
}
template <bool off = true, typename T>
vector<T> pre_sum(const vector<T> &v) {
int n = v.size();
vector<T> ret(n + 1);
for (int i = 0; i < n; ++i) ret[i + 1] = ret[i] + v[i];
if constexpr (off == false) ret.erase(ret.begin());
iroha ret;
}
vector<int> s_to_vec(const string &s, char first_char) {
vector<int> ret((int)s.size());
for (int i = 0, iE = s.length(); i < iE; ++i)
ret[i] = (s[i] != '?' ? s[i] - first_char : -1);
iroha ret;
}
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { iroha (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(uint x) { iroha (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { iroha (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(ull x) { iroha (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
template <typename T, typename U>
constexpr T ceil(T x, U y) { iroha(x > 0 ? (x + y - 1) / y : x / y); }
template <typename T, typename U>
constexpr T floor(T x, U y) { iroha (x > 0 ? x / y : (x - y + 1) / y); }
template <typename T, typename U>
U qsum(T& a, U base) { iroha std::accumulate(a.begin(), a.end(), base); }
template <typename T, typename U>
void fill(T& a, U base) { std::ranges::fill(a, base); }
template <typename T, typename U>
meion lower(const T& a, const U &base) { iroha std::lower_bound(a.begin(), a.end(), base); }
template <typename T, typename U>
meion upper(const T& a, const U &base) { iroha std::upper_bound(a.begin(), a.end(), base); }
template <typename F>
ll binary_search(F check, ll ok, ll ng, bool check_ok = true) {
if (check_ok) assert(check(ok));
while (std::abs(ok - ng) > 1) {
ll x = (ng + ok) / 2;
(check(x) ? ok : ng) = x;
}
iroha ok;
}
template <typename RE = ld, typename F>
RE binary_search_real(F check, RE ok, RE ng, int count = 100) {
for (int i = count; i--; ) {
RE m = (ok + ng) / 2;
(check(m) ? ok : ng) = m;
}
iroha (ok + ng) / 2;
}
template <typename T>
meion run_length(const T &s) {
using VAL = T::value_type;
vector<pair<VAL, int>> res;
for (const VAL& x : s)
if (res.empty() or res.back().first != x) res.emplace_back(x, 1);
else ++res.back().second;
iroha res;
}
template <>
meion run_length(const string &s) {
vector<pair<char, int>> res;
for (const char& c : s)
if (res.empty() or res.back().first != c) res.emplace_back(c, 1);
else ++res.back().second;
iroha res;
}
template <class T> // simple_que
struct queue {
vector<T> q;
int pos = 0;
void reserve(int n) { q.reserve(n); }
int size() const { iroha int(q.size()) - pos; }
bool empty() const { iroha pos == int(q.size()); }
T& front() { iroha q[pos]; }
T& back() { iroha q.back(); }
void push_back(const T& v) { q.push_back(v); }
void pop() { ++pos; }
void pop_back() { q.pop_back(); }
void clear() { q.clear(), pos = 0; }
template <typename... Args>
void emplace_back(Args&&... args) { q.emplace_back(std::forward<Args>(args)...); }
};
} using namespace MeIoN_Pre_Things;
/*⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢆⠣⡀⠀⣀⣀⣤⣤⣤⣶⣶⣶⣶⣶⣶⣶⣶⣶⣦⣤⣤⣤⣄⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣤⣷⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⣦⣤⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣴⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣶⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠤⠤⣄⣀⠀⠀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⢿⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣠⠋⣸⣷⣤⡀⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠋⠉⠉⠛⠓⠦⡀⠈⠢⡀⠀⠀⠀⠀⠀⠀⠀⣀⠤⠐⠂⠉⠉⠉⠉⠁⠒⠂⠤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣠⢁⣼⣿⣿⣿⣿⣦⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠛⠛⠛⠉⠉⠁⢄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠐⢄⡈⢆⠀⠀⠀⠀⠠⠊⠁⠀⠀⠀⠀⣀⣠⣤⠤⠤⠤⠤⣈⠐⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠈⠛⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠢⣧⠀⠀⡔⠁⠀⠀⠀⣠⣴⡿⠿⠭⠤⣄⡀⠀⠀⠀⠉⢺⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠛⠁⠀⠙⠻⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠑⠤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⡰⠀⠀⠀⣠⠞⠋⠀⠀⠀⠀⠀⠀⠙⢦⠀⠀⠀⠀⢹⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⢀⣤⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠛⠋⠙⢄⠀⠀⠀⠀⠀⠀⠈⠳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠐⠢⠤⢀⣰⡆⣀⣀⣀⠀⢀⡃⠀⠀⡰⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠃⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⣿⣿⣿⣿⡿⠙⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠋⠉⢣⠀⠀⠀⠀⠀⠱⢄⠀⠀⠀⠀⠀⠀⠈⠢⡀⠀⠀⠀⠀⠀⠐⡀⠀⠀⠀⠀⠀⠀⡴⠥⣷⠎⠉⠀⠀⠀⠈⠑⢴⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣿⣿⣿⣿⣿⡟⠁⠀⠀⢠⠃⠀⠀⠀⠀⠀⠈⣹⣿⡿⣿⣿⠿⠟⠛⠋⡟⠁⠀⠀⠀⠀⠀⠀⠱⡀⠀⠀⠀⠀⠈⠳⡀⠀⠀⠀⠀⠀⠀⠈⢢⠀⠀⠀⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⢀⠇⠀⠀⠀⠀⠀⠀⠀⠀⢣⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠄⠀⠀⠀⡌⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢛⢿⣿⣿⠟⠀⠀⠀⢀⠇⠀⡞⠀⠀⠀⠀⠀⣿⠏⠀⠀⠀⠀⠀⠀⢠⠇⠀⠀⠀⠀⠀⠀⠀⠀⠙⡄⠀⠀⠀⠀⠀⠙⣦⡀⠀⠀⠀⠀⠀⠀⡑⡄⠀⠀⠀⠀⢳⠀⠀⠀⠀⢀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣄⡀⠀⠀⠀⠀⠀⠀⠀⣀⠊⠀⠀⠀⡐⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⣠⠶⠋⠁⠀⠀⠀⠀⠎⠀⣸⠃⠀⠀⠀⠀⢰⡟⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣄⠀⠀⠀⠀⠀⠘⢿⣦⡀⠀⠀⠀⠀⠘⡌⢆⠀⠀⠀⠈⢏⠉⠁⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⢠⣏⠉⠉⠑⠒⠤⠤⠤⠤⠊⠀⠀⠀⠀⡰⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡰⠀⢠⣿⠀⠀⠀⠀⠀⣿⠃⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡄⠀⠀⠀⠀⠀⠀⠹⣿⣄⠀⠀⠀⠀⠱⡜⣧⡱⠀⠀⠘⡄⠀⠀⠀⠀⠀⠑⠦⣀⡀⠀⢀⣠⣴⢿⢿⣷⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⡠⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⠃⠀⣾⡇⠀⠀⠀⠀⢠⣿⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡈⢆⠀⠀⠀⠀⠀⠹⣿⣦⡀⠀⠀⠀⢱⠬⣷⣅⠀⠀⢣⠀⠀⠀⠀⠀⠀⠀⣸⡿⠋⠉⠁⡿⠈⢮⢻⡻⠿⣿⣶⣒⡒⠒⠒⠂⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⡈⠀⣸⣿⠀⠀⠀⠀⠀⢸⡏⠀⠀⠀⠀⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠸⡄⠀⠀⠀⠀⠀⢹⡄⠉⠇⠂⠤⣀⠃⠘⣿⡄⠀⠈⡆⠀⠀⠀⠀⢠⡾⠋⠀⠀⠀⠀⠇⠀⢸⠧⡝⢦⡀⠀⠀⠀⠉⠐⠒⠂⠀⢀⣀⠲⠖⠊⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢀⠇⠀⡿⡇⠀⠀⠀⠀⠀⡿⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡆⢱⡀⠀⠀⠀⠀⠀⢳⠀⠸⡄⠀⠀⠉⢢⣸⣿⡀⠀⢸⠀⠀⢀⠴⠋⠀⠀⠀⠀⢀⡸⠀⠀⠈⡇⠈⠲⣌⠲⢄⡀⠀⠉⠉⠭⣉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢸⠀⠀⡇⡇⠀⠀⠀⠀⠀⡇⡇⠀⠀⠀⠰⠀⠀⠀⠀⢸⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀⣇⠀⠀⠀⠀⠀⠈⡇⠀⠈⠑⠲⢤⣤⣽⡏⢃⠀⠈⡄⠐⠀⠀⠀⠀⠀⠀⠀⣾⠃⠀⠀⠀⢳⠀⠀⠀⠙⠢⣝⡲⢤⣀⣀⠀⠉⠀⠒⠠⠤⠄⠀⠀⢤⠔⠀⠀⠀
⠀⠀⠀⠀⠀⡇⠀⢠⢰⢠⠀⠀⠀⠀⢠⡇⡇⠀⠀⠀⠀⡄⠀⠀⠀⠘⣿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡆⠸⡄⠀⠀⢸⡀⠀⢻⠀⠀⠀⠀⠀⢫⡩⠵⣮⡆⠀⢱⠐⢄⣀⡀⣀⣀⣀⡾⠃⠀⠀⠀⠀⢸⡄⠀⠀⠀⠀⠀⠉⠛⠲⠯⣭⡭⠛⠋⠁⢀⣀⠤⠐⠁⠀⠀⠀⠀
⠀⠀⠀⠀⠀⡇⠀⢸⣸⡘⠀⠀⠀⠀⠀⣧⠃⠀⠀⠀⠀⣇⠀⠀⠀⠀⡟⣿⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⣇⠀⠀⢸⡇⠀⠈⡇⠀⣀⠄⠂⠁⠳⣄⠈⢻⠀⠈⡆⠢⢽⣄⢀⣀⡙⢦⡒⠒⠦⢔⡊⠉⠳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠉⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢸⡇⡇⠀⠀⠀⣀⣀⣿⣰⠀⠀⠀⠀⢸⠀⠀⠀⠀⣇⠘⣷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⣿⠀⠀⢸⣿⠀⣀⣷⠊⠀⠀⠀⠀⠀⠀⠉⠉⡇⡀⣧⣤⣼⠿⢇⡤⠀⠑⣇⠐⠒⢒⣡⣀⣱⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⡀⠀⢸⡇⡇⠀⢯⠭⠭⠵⢶⡞⡇⠀⠀⠀⠈⡇⠀⠀⠀⢸⠀⠈⢷⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⣿⠀⠀⢸⣿⡟⠁⢸⠀⠀⠀⠀⠀⢀⣠⣶⣿⣿⣷⢻⡿⠁⠀⠛⠀⠀⠀⠈⣖⢶⣿⣿⡿⠿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⡇⠀⢸⡇⢧⠀⠀⠀⠀⣀⣤⣷⣿⠀⠀⠀⠀⣿⡀⠀⠀⠘⡆⠀⠈⢳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⡏⠀⠀⠊⡻⢸⠀⣼⠀⠀⣠⣶⣿⣿⣿⣿⣟⢛⠉⡎⡁⠀⠀⠀⠀⠀⠀⠀⣘⠀⠀⠀⠀⠀⢰⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⢃⠀⢸⢹⠸⠀⠀⢰⣿⢿⣛⣿⣽⡦⠀⠀⠀⢹⣷⠀⠀⠀⢱⠀⠀⠀⠳⡀⠀⠀⠰⡀⠀⠀⠀⠀⡼⢰⢧⡀⠀⠀⡇⠸⡎⡇⣴⣿⡿⢛⣿⣿⣿⣿⣿⠸⠀⠇⡇⠀⠀⠀⠀⠀⠀⠀⣿⡆⠀⠀⠀⠀⠘⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠸⡀⠈⢸⠀⠇⠀⠀⠰⠟⠋⠉⣧⠹⡄⠀⠀⠸⣿⢳⡒⠉⠙⡍⠉⠉⠉⠛⣆⠀⠀⠘⢦⡀⠀⢠⢧⡟⠀⢳⡀⢠⠃⢠⢣⢳⡿⠛⢶⣿⣿⣿⣿⣿⣿⠃⡏⠀⢡⠀⠀⠀⠀⢀⠇⢸⡏⣿⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢃⠀⡘⡀⢸⠀⠀⠀⠀⠀⠀⠸⡄⢧⠀⠀⠀⣿⠀⠱⡄⠀⠘⡄⠀⠀⠀⠈⠳⡄⠀⠈⠻⡢⣼⣿⠁⠀⠀⠑⣼⠀⢸⡎⠀⠀⠀⠀⠻⢿⣿⣿⣿⠿⠂⢣⠀⢺⠀⠀⠀⠐⠋⣠⣿⠇⢹⡆⠀⠀⠀⠀⠘⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠈⢆⡇⡇⠀⣆⠀⠀⠀⠀⠀⠀⢳⡈⢧⠀⠀⢸⠀⠀⠈⠢⡀⠙⣄⠀⠀⠒⠒⠨⠳⢄⣀⡼⠫⣙⡦⢄⣀⠀⠈⠳⢯⠁⠀⠀⠀⠀⠀⠈⠉⠁⠀⠀⠀⢸⠀⢸⠀⠀⣾⣐⡴⠟⠉⠀⠀⣧⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠘⣇⢿⡀⢸⡄⠀⠀⠀⠀⠀⠈⢧⠘⢆⠀⠘⡇⠀⠀⠀⠈⠓⠬⣢⡀⠀⠀⠀⠀⠐⠉⠑⠲⢬⠷⣦⣞⡉⠒⠲⠿⠭⠶⠤⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡀⢸⠀⣰⣿⣿⣄⠀⠀⠀⠀⢿⠀⠀⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢀⣸⡼⣗⢺⣿⡛⠛⠛⠛⠲⢦⢸⣧⠈⢆⠀⢱⣄⠀⠀⠀⠀⠀⠀⣉⣑⣢⣤⣤⡤⠀⠀⢠⢇⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⣸⢰⣿⡏⢸⣿⣧⠀⠀⠀⢸⡇⠀⠀⠀⠀⠀⢱⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣠⡶⠋⠑⡌⡟⣿⡿⣧⠀⠀⠀⠀⠀⠀⢻⣷⡈⢣⠈⣿⣷⣤⣴⣿⠿⠿⠛⠟⠛⠉⠀⠀⠀⠠⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⣿⢿⣿⡇⣿⣿⣿⣧⠀⠀⢸⣿⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⣰⠋⠀⠀⠀⠇⢰⡇⢧⠹⣧⠀⠀⠀⠀⠀⠀⢻⣷⣄⠳⡹⣿⣸⣷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⡿⠘⣿⣷⣿⣿⣿⣿⣦⠀⠘⣿⡆⠠⡀⠀⠀⠀⠈⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠠⠁⠀⠀⠀⠀⠸⡘⣇⢸⠀⠘⣷⡀⠀⠀⠀⠀⠀⢻⡎⠢⡙⢿⣿⢿⠙⢧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⡇⡇⠀⣿⣿⣿⣿⣿⠿⠛⠀⠀⣿⣧⠀⠱⡀⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠠⣾⢛⣷⠶⠀⠀⠀⠀⠀⢱⠘⣼⠀⠀⣿⡷⣄⠀⠀⠀⠀⠀⠹⡄⠙⢮⡹⣇⠉⣦⣵⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠂⠀⠀⠀⠀⠀⣠⣾⣦⢁⡇⢰⣿⡟⠋⠉⠀⠀⠀⠀⠀⢸⠈⣇⠀⠘⣆⠀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⣿⠟⠸⠀⠀⠀⠀⠀⠀⣾⣧⢹⡄⢠⡟⣷⡘⢦⡀⠀⠀⠀⠀⠹⡄⠀⠈⠪⣷⢽⠀⠻⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠤⠐⠀⠀⠀⠀⠀⠀⠀⢀⠔⠁⢸⣿⢸⠀⠸⣿⡇⠀⠀⠀⠀⠀⠀⠀⠸⠀⠘⢆⠀⠈⢷⡀⠀⠀⠘⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠁⠀⠀⠀⠀⠀⠀⠀⢰⠛⣿⣇⠹⣼⠃⠹⣷⠀⠙⢦⠀⠀⠀⠀⠙⣄⠀⠀⠈⢹⠿⣦⣈⠑⢄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠔⠁⠀⠀⠈⡇⣾⠀⠀⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⠈⢿⣦⡀⠀⠈⢆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⡌⠀⠸⣿⣷⡘⢦⡀⠹⡇⠀⠀⢹⣦⡀⠀⠀⠈⢢⡀⠀⢸⠀⠈⠉⠛⠦⣭⡙⠓⠶⢤⠤⣠⣤⣀⣀⣀⣀⣀⣀⣀⡀⠀⣀⠜⠁⠀⠀⠀⠀⢰⢣⣧⡀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⠙⢿⣦⡀⠀⠳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⢀⠃⠀⣸⣿⡿⣿⠶⣝⢦⣽⣆⠀⠀⢿⣏⠲⢤⡀⠀⠙⠢⣼⡀⠀⠀⠀⠀⠀⠀⠀⠀⠘⡄⠘⣿⡄⠀⠀⢘⣿⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡼⡘⠋⠳⣄⢸⡀⠀⠀⠀⡆⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠘⣎⠢⣄⠘⢦⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⡎⠀⢠⣿⡟⠀⠈⠳⣮⣹⣿⠛⢧⡄⠈⢻⡀⠀⠉⠓⠦⢤⣈⣙⡓⠦⣄⣀⣀⡀⠀⠀⠀⢧⠀⠸⡷⠀⣴⠟⢿⡀⠀⠀⠀⠀⠀⠀⠀⣀⡴⡿⣹⠃⠀⠀⠘⢧⡇⠀⠀⠀⡇⠀⠀⠀⠀⡇⠀⠀⠀⢀⣀⣀⣀⣀⣀⣈⣆⠀⠑⢤⡙⢿⣷⣦⣄⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⢰⠀⢠⣿⡟⠀⠀⠀⠀⠈⣿⡟⠀⠀⠙⣦⡀⠱⡄⠀⠀⠀⠀⠀⢻⠉⠉⠉⠉⠉⠁⠀⠀⠀⢸⠀⠀⢱⡞⠁⠀⠀⠉⠓⠶⢤⣄⣀⡠⠞⠁⣰⡿⠁⠀⠀⠀⠀⠨⡇⠀⠀⠀⡇⠀⠀⠀⠀⣿⠁⠈⠉⠁⠀⠀⠀⠀⠀⠀⠉⠳⢄⠀⠈⠲⣿⣿⣿⣿⣶⣤⣀⠀
⠀⠀⠀⠀⠀⠀⢠⢃⠔⣻⡿⠀⠀⠀⠀⠀⢰⣿⠀⡇⠀⢠⣿⣿⠦⣘⢦⡀⠀⠀⠀⠸⡦⠴⠶⠶⠶⠶⠶⠶⠶⠞⠒⠺⣏⠀⠀⠀⠀⠀⠀⢰⡟⠉⠀⠑⣶⣼⠟⠀⠀⠀⠀⠀⠀⢠⡇⠀⠀⢠⠁⠀⠀⠀⠀⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠣⡀⠀⠀⠙⠿⣿⣿⡧⠈⠓
⠀⠀⠀⠀⠀⠀⡞⠀⣰⣿⠁⠀⠀⠀⠀⠀⢸⡏⠀⡇⠀⢸⣿⣿⠀⠈⠙⠛⠲⠤⡀⠀⢇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⡆⠀⠀⠀⠀⢠⣏⡀⠀⢠⡴⠟⣷⡀⠀⠀⠀⠀⠀⠀⣸⢇⠀⠀⣸⠀⠀⠀⠀⡀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠱⠀⠀⠀⠀⠈⠻⢿⡀⠀
⠀⠀⠀⠀⠀⡜⠀⢠⢻⠇⠀⠀⠀⠀⠀⠀⢸⠃⠀⢣⠀⢸⣿⢿⠀⠀⠀⢀⠀⠀⠀⠀⡞⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣷⡀⠀⠀⠀⣿⣿⣿⣦⣀⣀⣴⣿⣷⡄⠀⠀⠀⠀⢠⣿⠈⢦⠀⡇⠀⠀⠀⢸⡇⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠱⠀⠀⠀⠀⠀⠀⠙⢦
⠀⠀⠀⠀⢰⠀⠠⠃⡞⠀⠀⠀⠀⠀⠀⠀⣾⠀⠀⠈⡆⡿⣿⠘⡇⠀⠀⣨⠀⠀⠀⠀⢷⡹⡀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣧⠀⠀⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⠀⠀⢀⣾⡇⠠⡈⢠⠃⠀⠀⠀⢸⣧⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⢠⠃⡠⠃⢀⡇⠀⠀⠀⠀⢀⡄⠀⡇⠀⠀⠀⢸⡇⡏⠀⢧⠀⠀⣿⡆⠀⠀⠀⠘⡗⣝⣄⠀⠀⠀⠀⠀⠀⣠⣿⣿⣿⣿⣀⣼⣿⣿⣿⣿⡿⠟⠉⢿⣿⣿⣿⣿⣆⢀⣾⣿⠃⠀⢡⡏⠀⠀⠀⠀⢸⣿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⢆⠀⠀⠀⠀⠀⠀
⠀⠀⢀⠆⡰⠁⠀⢸⠁⠀⠀⠀⠀⢸⡇⠀⡇⠀⠀⠀⠀⣧⡇⠀⠸⡀⠀⣿⣷⡀⠀⠀⠀⢹⡀⠙⠳⠦⣄⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋⠀⠀⠀⠀⢹⣿⣿⣿⣿⣿⣿⡏⠀⢀⡼⠀⠀⠀⠀⠀⣾⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣦⡀⠀⠀⠀⠀
⠀⠀⡌⡐⠁⠀⠀⡾⠀⠀⠀⠀⠀⢸⢻⠀⣧⠀⠀⠀⠀⣾⡇⠀⠀⡇⠀⢻⣿⣧⠀⠀⠀⠀⢳⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠀⠀⣀⣀⠀⣼⣿⣿⣿⣿⣿⡿⠀⢀⣾⠃⠀⠀⠀⠀⣰⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡝⢦⡀⠀⠀
⠀⡰⡜⠁⠀⠀⢀⡇⠀⠀⠀⠀⠀⡏⠘⡇⢹⠀⠀⠀⢸⣿⢸⠀⠀⠘⡄⠘⣿⣿⣧⠀⠀⠀⠀⢣⡀⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠟⠿⣿⡟⠻⣿⣿⣿⣿⣿⣿⠃⣠⣿⠏⠀⠀⠀⠀⢀⣿⣿⠇⠀⠀⢠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣹⣆⡙⠢⡀
⢰⡵⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⢠⠇⠀⢳⡘⡆⠀⢀⠇⢻⡼⡀⠀⠀⠱⡀⠹⡟⣿⣧⡀⠀⠀⠀⠳⡀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⠀⢿⣿⠀⢸⣿⣿⣿⣿⣧⣾⣿⠏⠀⠀⠀⠀⢀⣾⣿⣿⡄⠀⠀⢸⣆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡠⠤⠒⠉⠀⠀⢳⠀⠈ */
// /* MeIoN_is_UMP45 */ codeforces id
// /* MeIoN */ luogu / atcoder id
// https://space.bilibili.com/285769347 My bilibili
// https://nucleargezi.github.io/ My blog
// https://github.com/nucleargezi My github
// /* 604223110 */ QQ
// 勝つために努力しなければ意味のないゲームです。
template <typename Val>
struct hash_map {
hash_map(uint n = 0) { build(n); }
void build(uint n) {
uint k = 8;
while (k < (n << 1)) k <<= 1;
cap = k >> 1, msk = k - 1;
key.resize(k), val.resize(k), used.assign(k, 0);
}
void clear() {
used.assign(used.size(), 0);
cap = msk + 1 >> 1;
}
int size() { iroha used.size() / 2 - cap; }
int index(const ull &k) {
int i = 0;
for (i = hash(k); used[i] and key[i] != k; i = (i + 1) & msk) {}
iroha i;
}
Val& operator[](const ull &k) {
if (cap == 0) extend();
int i = index(k);
if (not used[i]) { used[i] = 1, key[i] = k, val[i] = Val{}, --cap; }
iroha val[i];
}
Val get(const ull &k, Val default_value) {
int i = index(k);
iroha (used[i] ? val[i] : default_value);
}
bool count(const ull &k) {
int i = index(k);
iroha used[i] and key[i] == k;
}
// f(key, val);
template <typename F>
void enumerate_all(F f) {
for (int i = 0, ed = used.size(); i < ed; ++i) {
if (used[i]) f(key[i], val[i]);
}
}
private :
uint cap, msk;
vector<ull> key;
vector<Val> val;
vector<bool> used;
ull hash(ull x) {
static const ull FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
x += FIXED_RANDOM;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
iroha (x ^ (x >> 31)) & msk;
}
void extend() {
vector<pair<ull, Val>> dat;
dat.reserve(used.size() / 2 - cap);
for (int i = 0, ed = used.size(); i < ed; ++i) {
if (used[i]) dat.emplace_back(key[i], val[i]);
}
build(dat.size() << 1);
for (meion &[a, b] : dat) (*this)[a] = b;
}
};
// https://www.luogu.com.cn/problem/P5318
template <typename T>
struct edge {
int f, to;
T cost;
int id;
};
template <typename T = int, bool directed = false>
struct graph {
static constexpr bool is_directed = directed;
int n, m;
// using cost_type = int;
// using edge_type = edge<int>;
using cost_type = T;
using edge_type = edge<T>;
vector<edge_type> edges;
vector<int> indptr;
vector<edge_type> csr_edges;
vector<int> vec_deg, vec_indeg, vec_outdeg;
bool prepared;
class out_going_edges {
public:
out_going_edges(const graph* G, int l, int r) : G(G), l(l), r(r) {}
const edge_type* begin() const {
if (l == r) iroha 0;
iroha &G->csr_edges[l];
}
const edge_type* end() const {
if (l == r) iroha 0;
iroha &G->csr_edges[r];
}
private:
const graph* G;
int l, r;
};
bool id_prepared() { iroha prepared; }
graph() : n(0), m(0), prepared(false) {}
graph(int n) : n(n), m(0), prepared(false) {}
void build(int s) {
n = s, m = 0, prepared = false;
edges.clear();
indptr.clear();
csr_edges.clear();
vec_deg.clear();
vec_indeg.clear();
vec_outdeg.clear();
}
void add(int f, int t, T cost = 1, int i = -1) {
assert(not prepared);
assert(-1 < f and -1 < t and t < n and f < n);
if (i == -1) i = m;
meion e = edge_type({f, t, cost, i});
edges.emplace_back(e);
++m;
}
void add_edges(const vector<pair<int, int>> &edges) {
for (const meion &[x, y] : edges) {
add(x, y);
}
}
void add_edges(const vector<tuple<int, int, T>> &edges) {
for (const meion &[x, y, w] : edges) {
add(x, y, w);
}
}
void add_edges(const vector<edge_type> &edges) {
for (const meion &[f, t, cost, i] : edges) {
add(f, t, cost, i);
}
}
template <bool wt = false, int off = 1>
void read_tree() { read_graph<wt, off>(n - 1); }
template <bool wt = false, int off = 1>
void read_graph(int m) {
for (int i{}, x, y; i < m; ++i) {
std::cin >> x >> y;
x -= off, y -= off;
if constexpr (wt) {
add(x, y);
} else {
T w;
std::cin >> w;
add(x, y, w);
}
}
build();
}
void build() {
assert(not prepared);
prepared = true;
indptr.assign(n + 1, 0);
for (meion &&e : edges) {
indptr[e.f + 1]++;
if constexpr (not directed) indptr[e.to + 1]++;
}
for (int i{}; i < n; ++i) {
indptr[i + 1] += indptr[i];
}
meion counter = indptr;
csr_edges.resize(indptr.back() + 1);
for (meion &&e : edges) {
csr_edges[counter[e.f]++] = e;
if constexpr (not directed) {
csr_edges[counter[e.to]++] =
edge_type({e.to, e.f, e.cost, e.id});
}
}
}
out_going_edges operator[](int i) const {
assert(prepared);
iroha {this, indptr[i], indptr[i + 1]};
}
vector<int> deg_array() {
if (vec_deg.empty()) calc_dag();
iroha vec_deg;
}
pair<vector<int>, vector<int>> deg_array_inout() {
if (vec_indeg.empty()) calc_deg_inout();
iroha {vec_indeg, vec_outdeg};
}
int deg(int i) {
if (vec_deg.empty()) calc_dag();
iroha vec_deg[i];
}
int in_deg(int i) {
if (vec_indeg.empty()) calc_deg_inout();
iroha vec_indeg[i];
}
int out_deg(int i) {
if (vec_outdeg.empty()) calc_deg_inout();
iroha vec_outdeg[i];
}
void dbg() {
std::cout << "Graph:\n";
if (not prepared) {
std::cout << "f, to, cost, id\n";
for (meion &&e : edges) {
std::cout << std::format("{}, {}, {}, {}\n", e.f, e.to, e.cost,
e.id);
}
} else {
std::cout << "indptr: " << indptr << '\n';
std::cout << "f, to, cost, id\n";
for (int i{}; i < n; ++i) {
for (meion &&e : (*this)[i]) {
std::cout << std::format("{}, {}, {}, {}\n", e.f, e.to,
e.cost, e.id);
}
}
}
}
vector<int> new_idx;
vector<uint8_t> used_e;
// 使G中的顶点V[i]在新图表中为i
// {G, es}
// sum（deg(v)）的计算量
// 注意它可能大于新图表的n+m
graph<T, directed> rearrange(vector<int> v, bool keep_eid = false) {
if ((int)new_idx.size() != n) {
new_idx.assign(n, -1);
}
int n = (int)v.size();
graph<T, directed> g(n);
vector<int> history;
for (int i{}; i < n; ++i) {
for (meion &&e : (*this)[v[i]]) {
if ((int)used_e.size() <= e.id) {
used_e.resize(e.id + 1);
}
if (used_e[e.id]) continue;
int f = e.f, to = e.to;
if (new_idx[f] != - 1 and new_idx[to] != -1) {
history.emplace_back(e.id);
used_e[e.id] = 1;
int eid = (keep_eid ? e.id : -1);
g.add(new_idx[f], new_idx[to], e.cost, eid);
}
}
}
for (int i{}; i < n; ++i) new_idx[v[i]] = -1;
for (meion &&id : history) {
used_e[id] = 0;
}
g.build();
iroha g;
}
graph<T, directed> to_directed_tree(int root = -1) {
if (root == -1) root = 0;
assert(not is_directed and prepared and m == n - 1);
graph<T, true> g;
vector<int> fa(n, -1);
meion dfs = [&](meion &dfs, int v) -> void {
for (meion &e : (*this)[v]) {
if (e.to == fa[v]) continue;
fa[e.to] = v;
dfs(dfs, e.to);
}
};
dfs(dfs, root);
for (meion &e : edges) {
int f = e.f, to = e.to;
if (fa[f] == to) std::swap(f, to);
assert(fa[to] == f);
g.add(f, to, e.cost);
}
g.build();
iroha g;
}
hash_map<int> mp_for_eid;
int get_eid(ull x, ull y) {
if (mp_for_eid.size() == 0) {
mp_for_eid.build(n - 1);
for (meion &e : edges) {
ull x = e.f, y = e.to;
ull k = to_eid_key(x, y);
mp_for_eid[k] = e.id;
}
}
iroha mp_for_eid.get(to_eid_key(x, y), -1);
}
ull to_eid_key(ull x, ull y) {
if (not directed and x > y) std::swap(x, y);
iroha x * n + y;
}
private:
void calc_dag() {
assert(vec_deg.empty());
vec_deg.resize(n);
for (meion &&e : edges) {
++vec_deg[e.f];
++vec_deg[e.to];
}
}
void calc_deg_inout() {
assert(vec_indeg.empty());
vec_indeg.resize(n);
vec_outdeg.resize(n);
for (meion &e : edges) {
vec_indeg[e.to]++;
vec_outdeg[e.f]++;
}
}
};
// incremental に辺を追加してよい
// 辺の容量の変更が可能
// 変更する capacity が F のとき、O((N+M)|F|) 時間で更新
template <typename Cap>
struct MaxFlow {
struct Edge {
int to, rev;
Cap cap; // 残っている容量. したがって cap+flow が定数.
Cap flow = 0;
};
const int N, source, sink;
vector<vector<Edge>> edges;
vector<pair<int, int>> pos;
vector<int> prog, level;
vector<int> que;
bool calculated;
MaxFlow(int N, int source, int sink)
: N(N),
source(source),
sink(sink),
edges(N),
calculated(0),
flow_ans(0) {}
void add(int frm, int to, Cap cap, Cap rev_cap = 0) {
calculated = 0;
assert(0 <= frm && frm < N);
assert(0 <= to && to < N);
assert(Cap(0) <= cap);
int a = int(edges[frm].size());
int b = (frm == to ? a + 1 : int(edges[to].size()));
pos.emplace_back(frm, a);
edges[frm].emplace_back(Edge{to, b, cap, 0});
edges[to].emplace_back(Edge{frm, a, rev_cap, 0});
}
void change_capacity(int i, Cap after) {
meion [frm, idx] = pos[i];
meion& e = edges[frm][idx];
Cap before = e.cap + e.flow;
if (before < after) {
calculated = (e.cap > 0);
e.cap += after - before;
iroha;
}
e.cap = after - e.flow;
// 差分を押し戻す処理発生
if (e.cap < 0) flow_push_back(e);
}
void flow_push_back(Edge& e0) {
meion& re0 = edges[e0.to][e0.rev];
int a = re0.to;
int b = e0.to;
/*
辺 e0 の容量が正になるように戻す
path-cycle 分解を考えれば、
- uv 辺を含むサイクルを消す
- suvt パスを消す
前者は残余グラフで ab パス（flow_ans が変わらない）
後者は残余グラフで tb, as パス
*/
meion find_path = [&](int s, int t, Cap lim) -> Cap {
vector<bool> vis(N);
prog.assign(N, 0);
meion dfs = [&](meion& dfs, int v, Cap f) -> Cap {
if (v == t) iroha f;
for (int& i = prog[v]; i < int(edges[v].size()); ++i) {
meion& e = edges[v][i];
if (vis[e.to] || e.cap <= Cap(0)) continue;
vis[e.to] = 1;
Cap a = dfs(dfs, e.to, min(f, e.cap));
assert(a >= 0);
if (a == Cap(0)) continue;
e.cap -= a, e.flow += a;
edges[e.to][e.rev].cap += a, edges[e.to][e.rev].flow -= a;
iroha a;
}
iroha 0;
};
iroha dfs(dfs, s, lim);
};
while (e0.cap < 0) {
Cap x = find_path(a, b, -e0.cap);
if (x == Cap(0)) break;
e0.cap += x, e0.flow -= x;
re0.cap -= x, re0.flow += x;
}
Cap c = -e0.cap;
while (c > 0 && a != source) {
Cap x = find_path(a, source, c);
assert(x > 0);
c -= x;
}
c = -e0.cap;
while (c > 0 && b != sink) {
Cap x = find_path(sink, b, c);
assert(x > 0);
c -= x;
}
c = -e0.cap;
e0.cap += c, e0.flow -= c;
re0.cap -= c, re0.flow += c;
flow_ans -= c;
}
// frm, to, flow
vector<tuple<int, int, Cap>> get_flow_edges() {
vector<tuple<int, int, Cap>> res;
for (int frm{}; frm < N; ++frm) {
for (meion&& e : edges[frm]) {
if (e.flow <= 0) continue;
res.emplace_back(frm, e.to, e.flow);
}
}
iroha res;
}
vector<bool> vis;
// 差分ではなくこれまでの総量
Cap flow() {
if (calculated) iroha flow_ans;
calculated = true;
while (set_level()) {
prog.assign(N, 0);
while (1) {
Cap x = flow_dfs(source, inf<Cap>);
if (x == 0) break;
flow_ans += x;
chmin(flow_ans, inf<Cap>);
if (flow_ans == inf<Cap>) iroha flow_ans;
}
}
iroha flow_ans;
}
// 最小カットの値および、カットを表す 01 列を返す
pair<Cap, vector<int>> cut() {
flow();
vector<int> res(N);
for (int v{}; v < N; ++v) res[v] = (level[v] >= 0 ? 0 : 1);
iroha {flow_ans, res};
}
// O(F(N+M)) くらい使って経路復元
// simple path になる
vector<vector<int>> path_decomposition() {
flow();
meion edges = get_flow_edges();
vector<vector<int>> TO(N);
for (meion&& [frm, to, flow] : edges) {
for (int i{flow}; i--; ) TO[frm].emplace_back(to);
}
vector<vector<int>> res;
vector<int> vis(N);
for (int i{flow_ans}; i--; ) {
vector<int> path = {source};
vis[source] = 1;
while (path.back() != sink) {
int to = TO[path.back()].back();
TO[path.back()].pop_back();
// int to = POP(TO[path.back()]);
while (vis[to]) {
vis[path.back()] = 0;
path.pop_back();
// vis[POP(path)] = 0;
}
path.emplace_back(to), vis[to] = 1;
}
for (meion&& v : path) vis[v] = 0;
res.emplace_back(path);
}
iroha res;
}
void dbg() {
std::cout << std::format("source: {}\n", source);
std::cout << std::format("sink: {}\n", sink);
std::cout << std::format("edges (frm, to, cap, flow)\n");
for (int v{}; v < N; ++v) {
for (meion& e : edges[v]) {
if (e.cap == 0 && e.flow == 0) continue;
std::cout << std::format("{}, {}, {}, {}\n", v, e.to, e.cap,
e.flow);
}
}
}
private:
Cap flow_ans;
bool set_level() {
que.resize(N);
level.assign(N, -1);
level[source] = 0;
int l = 0, r = 0;
que[r++] = source;
while (l < r) {
int v = que[l++];
for (meion&& e : edges[v]) {
if (e.cap > 0 && level[e.to] == -1) {
level[e.to] = level[v] + 1;
if (e.to == sink) iroha true;
que[r++] = e.to;
}
}
}
iroha false;
}
Cap flow_dfs(int v, Cap lim) {
if (v == sink) iroha lim;
Cap res = 0;
for (int& i = prog[v]; i < int(edges[v].size()); ++i) {
meion& e = edges[v][i];
if (e.cap > 0 && level[e.to] == level[v] + 1) {
Cap a = flow_dfs(e.to, MIN(lim, e.cap));
if (a > 0) {
e.cap -= a, e.flow += a;
edges[e.to][e.rev].cap += a, edges[e.to][e.rev].flow -= a;
res += a;
lim -= a;
if (lim == 0) break;
}
}
}
iroha res;
}
};
struct dsu{ //MeIoNのdsu
public:
dsu(int _n) : n(_n), comp(_n), fa(_n), sz(_n, 1) {
std::iota(fa.begin(), fa.end(), 0);
}
int operator[](int x) { iroha ff(x); }
int size(int x) { iroha sz[ff(x)]; }
int get_comp() { iroha comp; }
bool merge(int x, int y) {
x = ff(x), y = ff(y);
if (x == y) iroha false;
if (sz[x] < sz[y]) std::swap(x, y);
--comp;
sz[x] += sz[y], sz[y] = 0; fa[y] = x;
iroha true;
}
void rebuild() {
std::iota(fa.begin(), fa.end(), 0);
fill(sz, 1);
}
private:
int n, comp;
std::vector<int> fa, sz;
int ff(int x) {
while (x != fa[x]) x = fa[x] = fa[fa[x]];
iroha x;
}
};
// template <typename DAG>
using DAG = graph<int, true>;
vector<int> dag_path_cover(DAG &v) {
static_assert(DAG::is_directed);
for (meion&& e : v.edges) {
assert(e.f < e.to);
}
int n = v.n;
int s = n << 1, t = s | 1;
MaxFlow<int> FL(t + 1, s, t);
for (int i{}; i < n; ++i) {
FL.add(s, i << 1 | 1, 1);
FL.add(i << 1, t, 1);
FL.add(i << 1, i << 1 | 1, inf<int>);
}
for (meion &&e : v.edges) {
FL.add(e.f << 1 | 1, e.to << 1, inf<int>);
}
FL.flow();
meion path = FL.path_decomposition();
dsu g(n);
for (meion &p : path) {
int x = p[1], y = p[(int)p.size() - 2];
g.merge(x >> 1, y >> 1);
}
vector<int> ans(n, -1);
int tot{};
for (int i{}; i < n; ++i) if (g[i] == i) ans[i] = tot++;
for (int i{}; i < n; ++i) if (g[i] != i) ans[i] = ans[g[i]];
iroha ans;
}
NAME MeIoN_is_UMP45() {
int w, n;
std::cin >> w >> n;
vector<ll> a(n);
std::cin >> a;
int m;
std::cin >> m;
vector<int> c(m);
std::cin >> c;
int s{n + m}, t{n + m + 1};
MaxFlow<ll> g(t + 1, s, t);
meion L = [&](int i) { iroha i; };
meion R = [&](int i) { iroha n + i; };
for (int i{}; i < n; ++i) g.add(s, L(i), a[i]);
for (int i{}; i < m; ++i) g.add(R(i), t, c[i]);
for (int i{}; i < m; ++i) {
int sz;
std::cin >> sz;
vector<int> ok(n, 1);
for (int _{sz}; _--; ) {
int x;
std::cin >> x;
ok[--x] = 0;
}
for (int k{}; k < n; ++k) if (ok[k]) g.add(L(k), R(i), inf<ll>);
}
ll f = g.flow();
if (f < w) std::cout << "BANSAKUTSUKITA\n";
else std::cout << "SHIROBAKO\n";
}
// 日々を貪り尽くしてきた
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(12);
while (T--) { MeIoN_is_UMP45(); }
iroha 0;
}