#pragma region template // clang-format off #if (defined __INTELLISENSE__) && (!defined PROPER) #define NDEBUG namespace std { #endif #ifdef LOCAL_NDEBUG #include #endif #ifdef LOCAL_DEBUG #include #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #if (defined __INTELLISENSE__) && (!defined PROPER) using namespace std; } #endif #ifdef DEBUGGER_HPP_INCLUDED #define FILE_LINE "[Debug] ./" + std::string(__FILE__) + ":" + std::to_string(__LINE__) + " in " + std::string(__func__) #define see(...) debugger::multi_print(#__VA_ARGS__, __VA_ARGS__) #define seetype(arg) debugger::multi_print(#arg, debugger::type_name) #define here(...) do {debugger::output << FILE_LINE << ": \e[32mReached\e[39m\n"; see(__VA_ARGS__); debugger::output << (std::string(#__VA_ARGS__).empty() ? "" : "\n");} while(0) #define com(msg) debugger::output << FILE_LINE << ":\n \e[36mComment:\e[39m " << msg << "\n" #define local(x) do {x} while(0) #define alter(x, y) x #else #define see(...) (static_cast(0)) #define seetype(arg) (static_cast(0)) #define here(...) (static_cast(0)) #define com(msg) (static_cast(0)) #define local(x) (static_cast(0)) #define alter(x, y) y #endif #if (defined DEBUGGER_HPP_INCLUDED) && (!defined NOWARN) #define warn(msg) debugger::output << FILE_LINE << ":\n \e[33mWarning:\e[39m " << msg << "\n" #else #define warn(msg) (static_cast(0)) #endif #if (defined LOCAL_DEBUG) || (defined LOCAL_NDEBUG) || (defined __INTELLISENSE__) #define NOEXCEPT #define M_assert(expr) assert(expr) #define O_assert(expr) assert(expr) #else #define NOEXCEPT noexcept #define M_assert(expr) do {if(__builtin_expect(!(expr), 0)) {auto p = static_cast(std::malloc(1 << 30)); for (int i = 0; i < (1 << 27); p[i] = 1, i += (1 << 9)); std::cerr << (*p);}} while(0) #define O_assert(expr) do {if(__builtin_expect(!(expr), 0)) {const auto X = std::string(1000, '-'); for(int i = 0; i < (1 << 18); i++) std::cout << X;}} while(0) #endif #define rep(i, n) for (std::make_signed_t> i = 0; i < (n); ++i) #define rng(i, f, t, s) for (std::make_signed_t>> i = (f); ((s) > 0) ? (i < (t)) : (i > (t)); i += (s)) #define erng(i, f, t, s) for (std::make_signed_t>> i = (f); ((s) > 0) ? (i <= (t)) : (i >= (t)); i += (s)) [[maybe_unused]] constexpr int INF = 1000000005; [[maybe_unused]] constexpr long long LINF = 1000000000000000005LL; [[maybe_unused]] constexpr double EPS = 1e-9; [[maybe_unused]] constexpr long double LEPS = 1e-14L; [[maybe_unused]] constexpr int dy[9] = {1, 0, -1, 0, 1, 1, -1, -1, 0}; [[maybe_unused]] constexpr int dx[9] = {0, 1, 0, -1, -1, 1, 1, -1, 0}; template > constexpr V Min(const S a, const T b, const U... c) { if constexpr (sizeof...(U)) return std::min((V) a, (V) Min(b, c...)); else return std::min((V) a, (V) b); } template > constexpr V Max(const S a, const T b, const U... c) { if constexpr (sizeof...(U)) return std::max((V) a, (V) Max(b, c...)); else return std::max((V) a, (V) b); } // clang-format on #pragma endregion #define ROLLING_HASH_MAX_LENGTH 250000 #define NUMBER_OF_BASES 3 #pragma region lib_rolling_hash namespace lib { namespace internal { template using hash_type = std::conditional_t<(30 < N), std::uint64_t, std::uint32_t>; template constexpr hash_type mask = (static_cast>(1) << N) - 1; template constexpr hash_type mul_mod_1(const hash_type lhs, const hash_type rhs) { const hash_type lhs_u = lhs >> N, lhs_d = lhs & mask; const hash_type rhs_u = rhs >> N, rhs_d = rhs & mask; const hash_type mid = lhs_d * rhs_u + lhs_u * rhs_d; return ((lhs_u * rhs_u) << 1) + lhs_d * rhs_d + ((mid & mask) << N) + (mid >> (N - 1)); } template constexpr Tp1 mul_mod_2(const Tp1 lhs, const Tp2 rhs) { const Tp2 rhs_d = rhs & mask; const Tp1 lhs_u = lhs >> N, mid = lhs_u * rhs_d; return (lhs & mask) *rhs_d + ((mid & mask) << N) + (mid >> (N - 1)); } template constexpr hash_type clamp(const hash_type x) { if (const hash_type res = (x >> N) + (x & mask); res < mask) return res; else return res - mask; } template [[maybe_unused]] auto has_begin(int) -> decltype(std::declval().begin(), std::true_type{}); template [[maybe_unused]] auto has_begin(...) -> std::false_type; template [[maybe_unused]] constexpr bool is_iteratable_container_v = decltype(has_begin(0))::value; #if (defined _GLIBCXX_VALARRAY) || (defined _LIBCPP_VALARRAY) template [[maybe_unused]] constexpr bool is_iteratable_container_v> = true; #endif } // namespace internal #if (NUMBER_OF_BASES == 1) namespace internal::rolling_hash_61 { using HashType = hash_type<61>; constexpr int MAX_N = ROLLING_HASH_MAX_LENGTH; constexpr std::uint32_t base = 1000000007; constexpr HashType padding = mask<61> * mask::digits - 61>; struct base_pow_constexpr { HashType val[MAX_N + 1]; constexpr base_pow_constexpr() : val() { val[0] = 1; for (int i = 1; i <= MAX_N; ++i) val[i] = clamp<61>(mul_mod_2<31>(val[i - 1], base)); } }; #if ROLLING_HASH_MAX_LENGTH > 250000 // if you want MAX_N to be greater than constexpr-loop-limit (typically 262144 = 2^18 in GCC), // you should use `const` instead of `constexpr` const base_pow_constexpr base_to_the_n; #else constexpr base_pow_constexpr base_to_the_n; #endif template