結果
| 問題 | No.945 YKC饅頭 |
| ユーザー |
 mind_cpp
|
| 提出日時 | 2024-03-17 07:27:00 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 328 ms / 2,000 ms |
| コード長 | 60,726 bytes |
| コンパイル時間 | 6,377 ms |
| コンパイル使用メモリ | 327,304 KB |
| 実行使用メモリ | 39,916 KB |
| 最終ジャッジ日時 | 2024-09-30 04:38:47 |
| 合計ジャッジ時間 | 16,441 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,820 KB |
| testcase_01 | AC | 2 ms
6,816 KB |
| testcase_02 | AC | 3 ms
6,820 KB |
| testcase_03 | AC | 4 ms
6,820 KB |
| testcase_04 | AC | 3 ms
6,820 KB |
| testcase_05 | AC | 3 ms
6,820 KB |
| testcase_06 | AC | 3 ms
6,820 KB |
| testcase_07 | AC | 3 ms
6,816 KB |
| testcase_08 | AC | 3 ms
6,816 KB |
| testcase_09 | AC | 3 ms
6,820 KB |
| testcase_10 | AC | 4 ms
6,820 KB |
| testcase_11 | AC | 3 ms
6,816 KB |
| testcase_12 | AC | 3 ms
6,820 KB |
| testcase_13 | AC | 4 ms
6,820 KB |
| testcase_14 | AC | 4 ms
6,820 KB |
| testcase_15 | AC | 3 ms
6,816 KB |
| testcase_16 | AC | 3 ms
6,820 KB |
| testcase_17 | AC | 3 ms
6,820 KB |
| testcase_18 | AC | 3 ms
6,816 KB |
| testcase_19 | AC | 3 ms
6,816 KB |
| testcase_20 | AC | 3 ms
6,816 KB |
| testcase_21 | AC | 3 ms
6,816 KB |
| testcase_22 | AC | 3 ms
6,820 KB |
| testcase_23 | AC | 3 ms
6,820 KB |
| testcase_24 | AC | 4 ms
6,816 KB |
| testcase_25 | AC | 3 ms
6,816 KB |
| testcase_26 | AC | 3 ms
6,820 KB |
| testcase_27 | AC | 2 ms
6,816 KB |
| testcase_28 | AC | 3 ms
6,816 KB |
| testcase_29 | AC | 2 ms
6,820 KB |
| testcase_30 | AC | 3 ms
6,816 KB |
| testcase_31 | AC | 20 ms
8,576 KB |
| testcase_32 | AC | 37 ms
13,464 KB |
| testcase_33 | AC | 84 ms
25,024 KB |
| testcase_34 | AC | 141 ms
22,212 KB |
| testcase_35 | AC | 270 ms
36,840 KB |
| testcase_36 | AC | 139 ms
18,408 KB |
| testcase_37 | AC | 137 ms
18,024 KB |
| testcase_38 | AC | 139 ms
18,664 KB |
| testcase_39 | AC | 50 ms
14,820 KB |
| testcase_40 | AC | 62 ms
23,404 KB |
| testcase_41 | AC | 34 ms
13,428 KB |
| testcase_42 | AC | 229 ms
26,856 KB |
| testcase_43 | AC | 122 ms
17,640 KB |
| testcase_44 | AC | 213 ms
32,872 KB |
| testcase_45 | AC | 236 ms
28,780 KB |
| testcase_46 | AC | 20 ms
12,588 KB |
| testcase_47 | AC | 151 ms
21,988 KB |
| testcase_48 | AC | 30 ms
6,900 KB |
| testcase_49 | AC | 75 ms
16,580 KB |
| testcase_50 | AC | 248 ms
29,416 KB |
| testcase_51 | AC | 328 ms
39,912 KB |
| testcase_52 | AC | 319 ms
39,916 KB |
| testcase_53 | AC | 318 ms
39,784 KB |
| testcase_54 | AC | 319 ms
39,912 KB |
| testcase_55 | AC | 326 ms
39,912 KB |
| testcase_56 | AC | 47 ms
22,720 KB |
| testcase_57 | AC | 47 ms
22,736 KB |
| testcase_58 | AC | 194 ms
34,136 KB |
| testcase_59 | AC | 220 ms
36,968 KB |
| testcase_60 | AC | 111 ms
27,544 KB |
| testcase_61 | AC | 216 ms
35,044 KB |
| testcase_62 | AC | 203 ms
34,276 KB |
| testcase_63 | AC | 46 ms
22,876 KB |
| testcase_64 | AC | 115 ms
28,136 KB |
| testcase_65 | AC | 102 ms
26,860 KB |
| testcase_66 | AC | 102 ms
26,724 KB |
| testcase_67 | AC | 160 ms
31,188 KB |
| testcase_68 | AC | 114 ms
27,752 KB |
| testcase_69 | AC | 67 ms
24,244 KB |
| testcase_70 | AC | 77 ms
24,756 KB |
| testcase_71 | AC | 73 ms
24,804 KB |
| testcase_72 | AC | 133 ms
29,328 KB |
| testcase_73 | AC | 227 ms
36,076 KB |
ソースコード
#define SETTING_MODINT modint998244353
// #define SETTING_MODINT modint1000000007
// #define SETTING_MODINT modint
#ifdef INCLUDED_MAIN
auto solve() {
GET(N, M);
vvll LRT;
rep(i, M) {
GETSTRS(SS);
if (SS[2] == "Y") {
LRT.pb(vll{STRLL(SS[0]), STRLL(SS[1]), 1});
} else if (SS[2] == "K") {
LRT.pb(vll{STRLL(SS[0]), STRLL(SS[1]), 2});
} else {
LRT.pb(vll{STRLL(SS[0]), STRLL(SS[1]), 3});
}
}
REV(LRT);
auto LST = LazySegTreeGetMaxRangeUpdate(N);
rep(i, M) {
INI(L, R, T, LRT[i]);
LST.apply(L - 1, R, LazyUpdate{T, true});
}
vll ans(3);
rep(i, N) {
ll v = LST.get(i).x - 1;
if (IN(0, v, 2)) ans[v]++;
}
print(ans);
return _0;
}
int main() {
// mint::set_mod(1);
auto ans = solve();
// print(ans);
UNUSED(ans);
}
// 以下は動作確認未実施
#else
#define INCLUDED_MAIN
#ifdef LOCAL
#include "../mytemplate.hpp"
#else
#include <algorithm>
#include <bits/extc++.h>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cstddef>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string_view>
#include <type_traits>
#include <utility>
#include <regex>
#include <array>
#include <algorithm>
#endif
using namespace std;
// clang-format off
/* accelration */
// 高速バイナリ生成
#ifndef LOCAL
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
// cin cout の結びつけ解除, stdioと同期しない(入出力非同期化)
// cとstdの入出力を混在させるとバグるので注意
struct IOSetting {IOSetting() {std::cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15);}} iosetting;
// unordered_mapでpair, vector, tupleをkeyにするためのコード
// (参考文献) https://qiita.com/hamamu/items/4d081751b69aa3bb3557
template<class T> size_t HashCombine(const size_t seed,const T &v){
return seed^(std::hash<T>()(v)+0x9e3779b9+(seed<<6)+(seed>>2));
}
/* pair用 */
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);
}
};
/* complex用 */
template<class T> struct std::hash<complex<T>>{
size_t operator()(const complex<T> &x) const noexcept {
size_t s=0;
s=HashCombine(s,x.real());
s=HashCombine(s,x.imag());
return s;
}
};
namespace std{
template<class T> bool operator<(const complex<T> &a, const complex<T> &b){
return a.real() == b.real() ? a.imag() < b.imag() : a.real() < b.real();
}
};
/* vector用 */
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;
}
};
/* deque用 */
template<class T> struct std::hash<std::deque<T>>{
size_t operator()(const std::deque<T> &keyval) const noexcept {
size_t s=0;
for (auto&& v: keyval) s=HashCombine(s,v);
return s;
}
};
/* tuple用 */
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);
}
};
/* alias */
using ull = __uint128_t;
//using ll = long long; // __int128でTLEするときに切り替える。
using ll = __int128_t;
using ld = long double;
using vll = vector<ll>;
using vd = vector<ld>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
using vvs = vector<vs>;
using vvvs = vector<vvs>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using umpll = unordered_map<ll, ll>;
using umpsl = unordered_map<string, ll>;
using mpll = map<ll, ll>;
using sll = set<ll>;
using msll = multiset<ll>;
using heapqll = priority_queue<ll, vll, greater<ll>>;
using heapqllrev = priority_queue<ll>;
using dll = deque<ll>;
ll parse(string &s) {
ll ret = 0;
bool isplus = true;
for (ll i = 0; i < s.length(); i++)
if ('0' <= s[i] && s[i] <= '9')
ret = 10 * ret + s[i] - '0';
else if (s[i] == '-')
isplus ^= isplus;
return isplus ? ret : -ret;
}
/* REP macro */
#define _overload4(_1,_2,_3,_4,name,...) name
#define _rep(i,n) reps(i,0,n)
#define reps(i,a,n) for (ll i = (a); i < (ll)(n); ++i)
#define repsp(i,a,n,s) for (ll i = (a); i < (ll)(n); i += s)
#define rep(...) _overload4(__VA_ARGS__,repsp, reps,_rep,)(__VA_ARGS__)
#define _overload4(_1,_2,_3,_4,name,...) name
#define _rrep(i,n) rreps(i,n,0)
#define rreps(i,a,n) for (ll i = (a); i >= (ll)(n); --i)
#define rrepsp(i,a,n,s) for (ll i = (a); i >= (ll)(n); i -= s)
#define rrep(...) _overload4(__VA_ARGS__, rrepsp, rreps, _rrep,)(__VA_ARGS__)
#define repd(i,n) for(ll i=n-1;i>=0;i--)
#define rrepd(i,n) for(ll i=n;i>=1;i--)
#define repdict(key, value, dict) for (const auto& [key, value] : dict)
#define repset(x, st) for(auto x : st)
/* define short */
#define endl "\n"
#define pf emplace_front
#define pb emplace_back
#define popleft pop_front
#define popright pop_back
#define mp make_pair
#define ump unordered_map
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define len(x) (ll)(x.size())
#define MAX(x) *max_element(all(x))
#define MIN(x) *min_element(all(x))
#define ARGMAX(x) distance(x.begin(), max_element(all(x)))
#define ARGMIN(x) distance(x.begin(), min_element(all(x)))
#define CLAMP(L, X, R) min(max(L, X), R)
#define IN(L, X, R) (L <= X && X <= R)
// 型変換
#define CHARSTR(x) (""s + x)
#define STRBIN2LL(x) ((ll)std::stoull(x, nullptr, 2))
#define STRLL(x) ((ll)parse(x))
#define STRD(x) std::stod(x)
#define CHARLL(x) ((ll)std::stoll(CHARSTR(x)))
#define SET(x) sll(all(x))
#define VEC(x) vll(all(x))
// 標準入出力
// 可変長引数を使った標準入力受け取り
inline void scan(){cin.ignore();}
template<class Head,class... Tail>
inline void scan(Head&head,Tail&... tail){std::cin>>head;scan(tail...);}
inline void scanll(){cin.ignore();}
template<class Head,class... Tail>
inline void scanll(Head&head,Tail&... tail){string h; std::cin>>h; head = STRLL(h); scanll(tail...);}
#define GET(...) ll __VA_ARGS__;scanll(__VA_ARGS__);
#define GETD(...) ld __VA_ARGS__;scan(__VA_ARGS__);
#define GETVLL(x) vll x = in_lls();
#define GETVVLL(x, N) vvll x; rep(i, N) {GETVLL(ab); x.pb(ab);}
#define GETVPLL(x, N) vector<pll> x; rep(i, N) {GET(a, b); x.pb(mp(a, b));}
#define GETVD(x) vd x = in_ds();
#define GETVVD(x, N) vvd x; rep(i, N) {GETVD(ab); x.pb(ab);}
#define GETSTR(...) string __VA_ARGS__;scan(__VA_ARGS__);
#define GETSTRS(x) vs x; x = in_strs();
#define GETVVS(x, N) vvs x; rep(i, N) x.pb(in_strs());
#define GETVSTR(x, N) vs x; rep(i, N) x.pb(in_str());
#define GETPOINT(p) Point p; {GET(x, y); p = Point{x, y};}
#define GETPOINTS(p, N) vector<Point> p; rep(i, N) {GET(x, y); p.pb(Point{x, y});}
#define GETCOMPLEX(p) complex<ld> p; {GETD(x, y); p = complex<ld>{x, y};}
#define GETCOMPLEXS(p, N) vector<complex<ld>> p; rep(i, N) {GETD(x, y); p.pb(complex<ld>{x, y});}
#define _overload7(_1,_2,_3,_4,_5,_6,_7,name,...) name
#define INI1(x, vec) auto x = vec[0];
#define INI2(x, y, vec) auto x = vec[0], y = vec[1];
#define INI3(x, y, z, vec) auto x = vec[0], y = vec[1], z = vec[2];
#define INI4(x, y, z, a, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3];
#define INI5(x, y, z, a, b, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3], b = vec[4];
#define INI6(x, y, z, a, b, c, vec) auto x = vec[0], y = vec[1], z = vec[2], a = vec[3], b = vec[4], c = vec[5];
#define INI(...) _overload7(__VA_ARGS__,INI6, INI5, INI4, INI3, INI2, INI1)(__VA_ARGS__)
#define SETPERM(x, N) vll x(N); iota(all(x), 0);
#define SETPERMS(x, s, N) vll x(N); iota(all(x), s);
#define UNUSED(x) ((void)x);
#define printF(x) print(x); cout << flush;
// [INT|LLONG|DBL|LDBL]_[MAX|MIN] 最大最小表現
/* sort */
#define SORT(x) stable_sort(all(x))
#define RSORT(x) stable_sort(rall(x))
#define SORT_IDX(x, idx) stable_sort(all(x), [&](const vll &_a_, const vll &_b_){return _a_[idx] < _b_[idx];})
#define RSORT_IDX(x, idx) stable_sort(all(x), [&](const vll &_a_, const vll &_b_){return _a_[idx] > _b_[idx];})
#define LB_IDX_VEC(c, x) distance((c).begin(), lower_bound(all(c), x)) // O(log N) x未満の最大値についてその右側のidxが求まる
#define UB_IDX_VEC(c, x) distance((c).begin(), upper_bound(all(c), x)) // O(log N) x以上の最小値についてその右側のidxが求まる
#define LB_ITR_VEC(c, x) lower_bound(all(c), x)
#define UB_ITR_VEC(c, x) upper_bound(all(c), x)
// #define LB_IDX_SET(c, x) distance((c).begin(), c.lower_bound(x)) // O(N)
// #define UB_IDX_SET(c, x) distance((c).begin(), c.upper_bound(x)) // O(N)
#define LB_ITR_SET(c, x) c.lower_bound(x)
#define UB_ITR_SET(c, x) c.upper_bound(x)
#define LB_ITR_MAP(c, x) c.lower_bound(x)
#define UB_ITR_MAP(c, x) c.upper_bound(x)
#define KEY_CHANGE(c, k1, k2) { auto i_ = c.extract(k1); i_.key() = k2; c.insert(std::move(i_));}
#define EXIST(key, dict) (dict.find(key) != dict.end())
#define REV(x) reverse(all(x))
// multisetでのerase
#define ERASE(x, s) {auto itr_ = s.find((x)); if (itr_ != s.end()) s.erase(itr_); }
// vectorの連結
#define CONCAT_VEC(c1, c2) c1.insert(c1.end(), all(c2));
// 第一引数と第二引数を比較し、第一引数(a)をより大きい/小さい値に上書き
template <typename T> inline bool chmin(T& a, const T& b) {bool compare = a > b; if (a > b) a = b; return compare;}
template <typename T> inline bool chmax(T& a, const T& b) {bool compare = a < b; if (a < b) a = b; return compare;}
inline string YESNO(bool cond) {return cond ? "YES" : "NO";}
inline string yesno(bool cond) {return cond ? "yes" : "no";}
inline string YesNo(bool cond) {return cond ? "Yes" : "No";}
namespace // 直値のデフォルトの型をllに。
{
ll _0 = 0;
ll _1 = 1;
ll _2 = 2;
ll _3 = 3;
ll _4 = 4;
ll _5 = 5;
ll _6 = 6;
ll _7 = 7;
ll _8 = 8;
ll _9 = 9;
ll _10 = 10;
ll _11 = 11;
ll _12 = 12;
ll _13 = 13;
ll _14 = 14;
ll _15 = 15;
ll _16 = 16;
ll _17 = 17;
ll _30 = 30;
ll _31 = 31;
ll _32 = 32;
ll _33 = 33;
ll _63 = 63;
ll _64 = 64;
ll _65 = 65;
ll _66 = 66;
ll _126 = 126;
ll _127 = 127;
ll _128 = 128;
ll _129 = 129;
};
void ignore_warning() // ワーニング対策
{
_0 = _0;
_1 = _1;
_2 = _2;
_3 = _3;
_4 = _4;
_5 = _5;
_6 = _6;
_7 = _7;
_8 = _8;
_9 = _9;
_10 = _10;
_11 = _11;
_12 = _12;
_13 = _13;
_14 = _14;
_15 = _15;
_16 = _16;
_17 = _17;
_30 = _30;
_31 = _31;
_32 = _32;
_33 = _33;
_63 = _63;
_64 = _64;
_65 = _65;
_66 = _66;
_126 = _126;
_127 = _127;
_128 = _128;
_129 = _129;
}
/* helper func */
std::ostream &operator<<(std::ostream &dest, __int128 value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char *d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
string STR(const vector<char> &cs) {
return string(cs.begin(), cs.end());
}
string RSTR(const vector<char> &cs) {
return string(cs.rbegin(), cs.rend());
}
template <typename T>
string STR(T v) {
ostringstream ss;
ss << v;
return ss.str();
}
namespace internal {
template <class T> struct simple_queue {
std::vector<T> payload;
int pos = 0;
void reserve(int n) { payload.reserve(n); }
int size() const { return int(payload.size()) - pos; }
bool empty() const { return pos == int(payload.size()); }
void push(const T& t) { payload.push_back(t); }
T& front() { return payload[pos]; }
void clear() {
payload.clear();
pos = 0;
}
void pop() { pos++; }
};
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
is_signed_int128<T>::value ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
// Fast modular multiplication by barrett reduction
// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
unsigned long long im;
// @param m `1 <= m < 2^31`
barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
// [1] m = 1
// a = b = im = 0, so okay
// [2] m >= 2
// im = ceil(2^64 / m)
// -> im * m = 2^64 + r (0 <= r < m)
// let z = a*b = c*m + d (0 <= c, d < m)
// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im
// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2
// ((ab * im) >> 64) == c or c + 1
unsigned long long z = a;
z *= b;
#ifdef _MSC_VER
unsigned long long x;
_umul128(z, im, &x);
#else
unsigned long long x =
(unsigned long long)(((unsigned __int128)(z)*im) >> 64);
#endif
unsigned int v = (unsigned int)(z - x * _m);
if (_m <= v) v += _m;
return v;
}
};
struct modint_base {};
struct static_modint_base : modint_base {};
// @param m `1 <= m`
// @return x mod m
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
// @param n `0 <= n`
// @param m `1 <= m`
// @return `(x ** n) % m`
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
unsigned long long r = 1;
unsigned long long y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
// Reference:
// M. Forisek and J. Jancina,
// Fast Primality Testing for Integers That Fit into a Machine Word
// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr long long bases[3] = {2, 7, 61};
for (long long a : bases) {
long long t = d;
long long y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) {
return false;
}
}
return true;
}
template <int n> constexpr bool is_prime = is_prime_constexpr(n);
// @param b `1 <= b`
// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
// Contracts:
// [1] s - m0 * a = 0 (mod b)
// [2] t - m1 * a = 0 (mod b)
// [3] s * |m1| + t * |m0| <= b
long long s = b, t = a;
long long m0 = 0, m1 = 1;
while (t) {
long long u = s / t;
s -= t * u;
m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b
// [3]:
// (s - t * u) * |m1| + t * |m0 - m1 * u|
// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)
// = s * |m1| + t * |m0| <= b
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
// by [3]: |m0| <= b/g
// by g != b: |m0| < b/g
if (m0 < 0) m0 += b / s;
return {s, m0};
}
// Compile time primitive root
// @param m must be prime
// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (long long)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
divs[cnt++] = x;
}
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
} // namespace internal
template<int m, std::enable_if_t<(1 <= m)> * = nullptr>
struct static_modint : internal::static_modint_base {
using mint = static_modint;
public:
static constexpr int mod() { return m; }
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
static_modint()
: _v(0) {}
template<class T, internal::is_signed_int_t<T> * = nullptr>
static_modint(T v) {
long long x = (long long)(v % (long long)(umod()));
if (x < 0) x += umod();
_v = (unsigned int)(x);
}
template<class T, internal::is_unsigned_int_t<T> * = nullptr>
static_modint(T v) {
_v = (unsigned int)(v % umod());
}
static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }
ll val() const { return (ll)_v; }
mint &operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint &operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint &operator+=(const mint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint &operator-=(const mint &rhs) {
_v -= rhs._v;
if (_v >= umod()) _v += umod();
return *this;
}
mint &operator*=(const mint &rhs) {
unsigned long long z = _v;
z *= rhs._v;
_v = (unsigned int)(z % umod());
return *this;
}
mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
if (prime) {
assert(_v);
return pow(umod() - 2);
} else {
auto eg = internal::inv_gcd(_v, m);
assert(eg.first == 1);
return eg.second;
}
}
friend mint operator+(const mint &lhs, const mint &rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint &lhs, const mint &rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint &lhs, const mint &rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint &lhs, const mint &rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint &lhs, const mint &rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint &lhs, const mint &rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static constexpr unsigned int umod() { return m; }
static constexpr bool prime = internal::is_prime<m>;
};
template<int id>
struct dynamic_modint : internal::modint_base {
using mint = dynamic_modint;
public:
static int mod() { return (int)(bt.umod()); }
static void set_mod(int m) {
assert(1 <= m);
bt = internal::barrett(m);
}
static mint raw(int v) {
mint x;
x._v = v;
return x;
}
dynamic_modint()
: _v(0) {}
template<class T, internal::is_signed_int_t<T> * = nullptr>
dynamic_modint(T v) {
long long x = (long long)(v % (long long)(mod()));
if (x < 0) x += mod();
_v = (unsigned int)(x);
}
template<class T, internal::is_unsigned_int_t<T> * = nullptr>
dynamic_modint(T v) {
_v = (unsigned int)(v % mod());
}
dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }
ll val() const { return (ll)_v; }
mint &operator++() {
_v++;
if (_v == umod()) _v = 0;
return *this;
}
mint &operator--() {
if (_v == 0) _v = umod();
_v--;
return *this;
}
mint operator++(int) {
mint result = *this;
++*this;
return result;
}
mint operator--(int) {
mint result = *this;
--*this;
return result;
}
mint &operator+=(const mint &rhs) {
_v += rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint &operator-=(const mint &rhs) {
_v += mod() - rhs._v;
if (_v >= umod()) _v -= umod();
return *this;
}
mint &operator*=(const mint &rhs) {
_v = bt.mul(_v, rhs._v);
return *this;
}
mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return mint() - *this; }
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
auto eg = internal::inv_gcd(_v, mod());
assert(eg.first == 1);
return eg.second;
}
friend mint operator+(const mint &lhs, const mint &rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint &lhs, const mint &rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint &lhs, const mint &rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint &lhs, const mint &rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint &lhs, const mint &rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint &lhs, const mint &rhs) {
return lhs._v != rhs._v;
}
private:
unsigned int _v;
static internal::barrett bt;
static unsigned int umod() { return bt.umod(); }
};
template<int id>
internal::barrett dynamic_modint<id>::bt = 998244353;
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
using modint = dynamic_modint<-1>;
namespace internal {
template<class T>
using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
template<class T>
using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
template<class>
struct is_dynamic_modint : public std::false_type {};
template<int id>
struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
template<class T>
using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
} // namespace internal
using mint = SETTING_MODINT;
using vm = vector<mint>;
using vvm = vector<vm>;
using vvvm = vector<vvm>;
/* mint用 hash*/
template<>struct std::hash<mint>{
size_t operator()(const mint &x) const noexcept {
return x.val();
}
};
template <typename T>
T SUM(const vector<T> &v) {
T total = 0;
rep(i, len(v)) {
total += v[i];
}
return total;
}
// 文字列区間swap[L, R)
string rangeswap(const string &S, ll L, ll R) {
string T = S;
ll cnt = (R - L) >> 1;
rep (i, cnt) swap(T[L + i], T[R - i - 1]);
return T;
}
template<class... T>
constexpr auto min(T... a){
return min(initializer_list<common_type_t<T...>>{a...});
}
template<class... T>
constexpr auto max(T... a){
return max(initializer_list<common_type_t<T...>>{a...});
}
// 幾何関連データ構造
constexpr ld eps = 1e-9;
// ラジアン->度
ld rad2Deg(ld rad) { return rad * 180.0 / M_PI; }
// 度->ラジアン
ld deg2Rad(ld deg) { return deg * M_PI / 180.0; }
/* func */
inline ll in_ll() {string s; getline(cin, s); return STRLL(s);}
inline ld in_d() {string s; getline(cin, s); return STRD(s);}
inline string in_str() {string s; getline(cin, s); return s;}
inline void print(const sll& v, string s = " ")
{if (len(v) == 0) { cout << endl; return;} bool first = true; for(auto &p : v) { if(first) {first = false; cout << p;} else cout << s << p;} cout << endl;}
inline void print(const msll& v, string s = " ")
{if (len(v) == 0) { cout << endl; return;} bool first = true; for(auto &p : v) { if(first) {first = false; cout << p;} else cout << s << p;} cout << endl;}
template <typename T> inline void print(const deque<T>& v, string s = " ")
{if (len(v) == 0) { cout << endl; return;} rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
template <typename T> inline void print(const vector<T>& v, string s = " ")
{if (len(v) == 0) { cout << endl; return;} rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
inline void print(const set<vll>& v, string s = " ")
{if (len(v) == 0) { cout << endl; return;} for(auto &x : v) print(x, s);}
inline void print(const vvll& v, string s = " ")
{if (len(v) == 0) { cout << endl; return;} rep(i, len(v)) print(v[i], s);}
template <typename T, typename S> inline void print(const pair<T, S>& p)
{cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const complex<T>& p)
{cout << p.real() << " " << p.imag() << endl;}
template <typename T> inline void print(const T& x) {cout << x << endl;}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v)
{if (len(v) == 0) { cout << endl; return;} for (auto&& p : v) print(p);}
template <typename T, typename S> inline void print(const unordered_map<T, S>& d)
{if (len(d) == 0) { cout << endl; return;} for (const auto& [key, value] : d) {cout << key << " "; print(value);}}
template <typename T, typename S> inline void print(const map<T, S>& d)
{if (len(d) == 0) { cout << endl; return;} for (const auto& [key, value] : d) {cout << key << " "; print(value);}}
inline void print(const vc &d) {if (len(d) == 0) { cout << endl; return;} rep(i, len(d)) cout << d[i]; cout << endl;}
inline void print(const mint &v) {cout << v.val() << endl;}
inline void print(const vm& v, string s = " ") {rep(i, len(v)) cout << v[i].val() << (i != (ll)v.size() - 1 ? s : "\n");}
/* debug */
namespace debug_print_func {
std::ostream& os = std::cerr;
template <class Tp> auto has_cbegin(int) -> decltype(std::cbegin(std::declval<Tp>()), std::true_type {});
template <class Tp> auto has_cbegin(...) -> std::false_type;
template <class Tp> auto has_value_type(int) -> decltype(std::declval<typename Tp::value_type>(), std::true_type {});
template <class Tp> auto has_value_type(...) -> std::false_type;
template <class Tp>[[maybe_unused]] constexpr bool is_iteratable_container_v = decltype(has_cbegin<Tp>(int {}))::value;
template <class Tp>[[maybe_unused]] constexpr bool is_container_v = decltype(has_value_type<Tp>(int {}))::value
|| is_iteratable_container_v<Tp>;
template <> [[maybe_unused]] constexpr bool is_iteratable_container_v<std::string_view> = false;
template <> [[maybe_unused]] constexpr bool is_container_v<std::string_view> = false;
#if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)
template <> [[maybe_unused]] constexpr bool is_iteratable_container_v<std::string> = false;
template <> [[maybe_unused]] constexpr bool is_container_v<std::string> = false;
#endif
template <class Tp, class... Ts> struct first_element { using type = Tp; };
template <class... Ts> using first_t = typename first_element<Ts...>::type;
template <class Tp, std::enable_if_t<!decltype(has_value_type<Tp>(int {}))::value, std::nullptr_t> = nullptr>
auto check_elem(int) -> decltype(*std::cbegin(std::declval<Tp>()));
template <class Tp, std::enable_if_t<decltype(has_value_type<Tp>(int {}))::value, std::nullptr_t> = nullptr>
auto check_elem(int) -> typename Tp::value_type;
template <class Tp>
auto check_elem(...) -> void;
template <class Tp> using elem_t = decltype(check_elem<Tp>(int {}));
template <class Tp> [[maybe_unused]] constexpr bool is_multidim_container_v = is_container_v<Tp>
&& is_container_v<elem_t<Tp>>;
template <class Tp> std::enable_if_t<!is_container_v<Tp>> out(const Tp&);
void out(const char&);
void out(const char*);
void out(const std::string_view&);
#if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)
void out(const std::string&);
#endif
#ifdef __SIZEOF_INT128__
void out(const __int128&);
void out(const unsigned __int128&);
#endif
template <class Tp1, class Tp2> void out(const std::pair<Tp1, Tp2>&);
#if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE)
template <class... Ts> void out(const std::tuple<Ts...>&);
#endif
#if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK)
template <class... Ts> void out(std::stack<Ts...>);
#endif
#if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE)
template <class... Ts> void out(std::queue<Ts...>);
template <class... Ts> void out(std::priority_queue<Ts...>);
#endif
template <class C>
std::enable_if_t<is_iteratable_container_v<C>> out(const C&);
template <class Tp> std::enable_if_t<!is_container_v<Tp>> out(const Tp& arg) {
os << arg;
}
void out(const char& arg) {
os << '\'' << arg << '\'';
}
void out(const char* arg) {
os << '\"' << arg << '\"';
}
void out(const ld arg) {
if (arg == LDBL_MAX) {
os << "∞";
} else if (arg == -LDBL_MAX) {
os << "-∞";
} else {
os << arg;
}
}
template <typename T>
void out(const std::complex<T>& arg) {
os << '\"' << arg.real() << " + " << arg.imag() << "i" << '\"';
}
void out(const std::string_view& arg) {
os << '\"' << arg << '\"';
}
#if (defined _GLIBCXX_STRING) || (defined _LIBCPP_STRING)
void out(const std::string& arg) {
os << '\"' << arg << '\"';
}
#endif
#ifdef __SIZEOF_INT128__
void out(const __int128& arg) {
if (arg == ULLONG_MAX) {
os << "∞";
} else {
int sign = (arg < 0) ? (-1) : 1;
if (sign == -1) os << '-';
__int128 base = sign;
while (sign * arg >= sign * base * 10) base *= 10;
while (base) {
os << static_cast<char>('0' + (arg / base % 10));
base /= 10;
}
}
}
void out(const unsigned __int128& arg) {
if (arg == ULLONG_MAX) {
os << "∞";
} else {
unsigned __int128 base = 1;
while (arg >= base * 10) base *= 10;
while (base) {
os << static_cast<char>('0' + (arg / base % 10));
base /= 10;
}
}
}
#endif
void out(const mint &arg) {
out(arg.val());
}
template <class Tp1, class Tp2> void out(const std::pair<Tp1, Tp2>& arg) {
os << '(';
out(arg.first);
os << ", ";
out(arg.second);
os << ')';
}
#if (defined _GLIBCXX_TUPLE) || (defined _LIBCPP_TUPLE)
template <class T, std::size_t... Is> void print_tuple(const T& arg, std::index_sequence<Is...>) {
static_cast<void>(((os << (Is == 0 ? "" : ", "), out(std::get<Is>(arg))), ...));
}
template <class... Ts> void out(const std::tuple<Ts...>& arg) {
os << '(';
print_tuple(arg, std::make_index_sequence<sizeof...(Ts)>());
os << ')';
}
#endif
#if (defined _GLIBCXX_STACK) || (defined _LIBCPP_STACK)
template <class... Ts> void out(std::stack<Ts...> arg) {
if (arg.empty()) {
os << "<empty stack>";
return;
}
os << "[ ";
while (!arg.empty()) {
out(arg.top());
os << ' ';
arg.pop();
}
os << ']';
}
#endif
#if (defined _GLIBCXX_QUEUE) || (defined _LIBCPP_QUEUE)
template <class... Ts> void out(std::queue<Ts...> arg) {
if (arg.empty()) {
os << "<empty queue>";
return;
}
os << "[ ";
while (!arg.empty()) {
out(arg.front());
os << ' ';
arg.pop();
}
os << ']';
}
template <class... Ts> void out(std::priority_queue<Ts...> arg) {
if (arg.empty()) {
os << "<empty priority_queue>";
return;
}
os << "[ ";
while (!arg.empty()) {
out(arg.top());
os << ' ';
arg.pop();
}
os << ']';
}
#endif
template <class Container>
std::enable_if_t<is_iteratable_container_v<Container>> out(const Container& arg) {
if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) {
os << "<empty container>";
return;
}
os << "[ ";
std::for_each(std::cbegin(arg), std::cend(arg), [](const elem_t<Container>& elem) {
out(elem);
os << ' ';
});
os << ']';
}
template <class Tp> std::enable_if_t<!is_multidim_container_v<Tp>>
print(std::string_view name, const Tp& arg) {
os << name << ": ";
out(arg);
if constexpr (is_container_v<Tp>)
os << '\n';
}
template <class Tp> std::enable_if_t<is_multidim_container_v<Tp>>
print(std::string_view name, const Tp& arg) {
os << name << ": ";
if (std::distance(std::cbegin(arg), std::cend(arg)) == 0) {
os << "<empty multidimensional container>\n";
return;
}
std::for_each(std::cbegin(arg), std::cend(arg),
[&name, is_first_elem = true](const elem_t<Tp>& elem) mutable {
if (is_first_elem)
is_first_elem = false;
else
for (std::size_t i = 0; i < name.length() + 2; i++)
os << ' ';
out(elem);
os << '\n';
});
}
template <class Tp, class... Ts> void multi_print(std::string_view names, const Tp& arg, const Ts&... args) {
if constexpr (sizeof...(Ts) == 0) {
names.remove_suffix(
std::distance(
names.crbegin(),
std::find_if_not(names.crbegin(), names.crend(),
[](const char c) { return std::isspace(c); })
)
);
print(names, arg);
if constexpr (!is_container_v<Tp>)
os << '\n';
} else {
std::size_t comma_pos = 0;
for (std::size_t i = 0, paren_depth = 0, inside_quote = false; i < names.length(); i++) {
if (!inside_quote && paren_depth == 0 && i > 0 && names[i - 1] != '\'' && names[i] == ',') {
comma_pos = i;
break;
}
if (names[i] == '\"') {
if (i > 0 && names[i - 1] == '\\') continue;
inside_quote ^= true;
}
if (!inside_quote && names[i] == '(' && (i == 0 || names[i - 1] != '\''))
paren_depth++;
if (!inside_quote && names[i] == ')' && (i == 0 || names[i - 1] != '\''))
paren_depth--;
}
const std::size_t first_varname_length = comma_pos - std::distance(
names.crend() - comma_pos,
std::find_if_not(
names.crend() - comma_pos, names.crend(),
[](const char c) { return std::isspace(c); }
)
);
print(names.substr(0, first_varname_length), arg);
if constexpr (!is_container_v<Tp>) {
if constexpr (is_container_v<first_t<Ts...>>)
os << '\n';
else
os << " | ";
}
const std::size_t next_varname_begins_at = std::distance(
names.cbegin(),
std::find_if_not(
names.cbegin() + comma_pos + 1, names.cend(),
[](const char c) { return std::isspace(c); }
)
);
names.remove_prefix(next_varname_begins_at);
multi_print(names, args...);
}
}
} // namespace debug_print
#ifdef LOCAL
# define debug(...) do {cerr << "\033[33m(line:" << __LINE__ << ") " << endl; debug_print_func::multi_print(#__VA_ARGS__, __VA_ARGS__); cerr << "\033[m";} while(false)
#else
# define debug(...) ;
#endif
/* 標準入力 */
vs in_strs(const string &delimiter = " ")
{
string s;
getline(cin, s);
vs output;
bitset<255> delims;
for (unsigned char c: delimiter)
{
delims[c] = true;
}
string::const_iterator beg;
bool in_token = false;
for( string::const_iterator it = s.cbegin(), end = s.cend(); it != end; ++it )
{
if( delims[*it] )
{
if( in_token )
{
output.pb(beg, it);
in_token = false;
}
}
else if( !in_token )
{
beg = it;
in_token = true;
}
}
if( in_token )
output.pb(beg, s.cend());
return output;
}
inline vll in_lls()
{
vll vals;
vs tokens = in_strs();
for (string i: tokens) vals.pb(STRLL(i));
return vals;
}
inline vd in_ds()
{
vd vals;
vs tokens = in_strs();
for (string i: tokens) vals.pb(STRD(i));
return vals;
}
inline vvll in_llss(ll line) // 複数行文字列解析
{
vvll valss;
rep(i, line) valss.pb(in_lls());
return valss;
}
inline vs in_vs(ll line) // 複数行文字列解析
{
vs vecs;
rep(i, line) {
vecs.pb(in_str());
}
return vecs;
}
inline ll popcnt(ll x) { return __builtin_popcountll(x); }
template <typename T, typename U>
T ceil(T x, U y) {
return (x > 0 ? (x + y - 1) / y : x / y);
}
template <typename T, typename U>
T floor(T x, U y) {
return (x > 0 ? x / y : (x - y + 1) / y);
}
template <typename T>
vector<T> accsum(const vector<T> &vec, bool need0 = true) {
if (len(vec) == 0) return vector<T>();
vector<T> acc = {0};
ll idx = 0;
if (!need0) {
acc[0] = vec[0];
idx = 1;
}
rep (i, idx, len(vec)) acc.pb(acc[len(acc) - 1] + vec[i]);
return acc;
}
inline ll sumk(ll n)
{
return n > 0 ? n * (n + 1) / 2 : 0;
}
inline ll sumk2(ll n)
{
return n > 0 ? n * (n + 1) * (2 * n + 1) / 6 : 0;
}
inline mint sumk(mint n)
{
return n * (n + 1) / 2;
}
inline mint sumk2(mint n)
{
return n * (n + 1) * (2 * n + 1) / 6;
}
inline string alpha()
{
return "abcdefghijklmnopqrstuvwxyz";
}
inline ll alpha_num(char c)
{
return ll(c) - ll('a');
}
inline string alpha_big()
{
return "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
}
inline ll alpha_big_num(char c)
{
return ll(c) - ll('A');
}
inline char alpha_big2small(char C) {
static string s = alpha();
ll idx = alpha_big_num(C);
return IN(0, idx, 25) ? s[idx] : C;
}
inline string alpha_big2small(const string &S) {
string s;
rep(i, len(S)) s += alpha_big2small(S[i]);
return s;
}
inline char alpha_small2big(char c) {
static string s = alpha_big();
ll idx = alpha_num(c);
return IN(0, idx, 25) ? s[idx] : c;
}
inline string alpha_small2big(const string &S) {
string s;
rep(i, len(S)) s += alpha_small2big(S[i]);
return s;
}
// 10進数の値Nをb進数で表したときの桁和。
ll digitsum(ll N, ll b) {
ll ret = 0;
while (N) {
ret += N % b;
N /= b;
}
return ret;
}
// 10進数文字列の各桁和
ll digitsum(const string &s) {
ll val = 0;
rep (i, len(s)) {
val += CHARLL(s[i]);
}
return val;
}
string zerofill(ll v, ll outputlen)
{
string s = STR(v);
string zerostr(outputlen - len(s), '0');
return zerostr + s;
}
// ランレングス圧縮
// auto rle = RunLengthEncoding(S);
// rep(i, len(rle)) {
// auto &[c, cnt] = rle[i];
// }
vector<pair<char, ll>> RunLengthEncoding(const string &s) {
vector<pair<char, ll>> tbl;
char c = s[0];
ll cnt = 1;
ll N = len(s);
reps (i, 1, N) {
if (c == s[i]) {
cnt++;
}
else {
tbl.pb(mp(c, cnt));
c = s[i];
cnt = 1;
}
}
tbl.pb(mp(c, cnt));
return tbl;
}
// ランレングス圧縮
// auto rle = RunLengthEncoding(S);
// rep(i, len(rle)) {
// auto &[c, cnt] = rle[i];
// }
template <typename T>
vector<pair<T, ll>> RunLengthEncoding(const vector<T> &s) {
vector<pair<T, ll>> tbl;
T c = s[0];
ll cnt = 1;
ll N = len(s);
reps (i, 1, N) {
if (c == s[i]) {
cnt++;
}
else {
tbl.pb(mp(c, cnt));
c = s[i];
cnt = 1;
}
}
tbl.pb(mp(c, cnt));
return tbl;
}
// 文字列連結(文字)
string repeatstr(const char &c, ll num) {
return string(num, c);
}
// 文字列連結(文字列)
string repeatstr(const string &s, ll num) {
if (num == 0) return "";
string ret = "";
bitset<128> tmp = num;
bool isok = false;
repd (i, 128) {
if (!isok && tmp[i]) isok = true;
if (!isok) continue;
ret += ret;
if (tmp[i]) {
ret += s;
}
}
return ret;
}
// [lidx, ridx)の区間の文字列を取得 substr("0123456789", 2, 6) -> "2345"
// 第3引数は文字数ではない
string substr(const string &s, ll lidx, ll ridx) {
if (ridx <= lidx) return "";
return s.substr(lidx, ridx - lidx);
}
// 区間 [l1, r1), [l2, r2)の共通部分の整数の個数を算出
ll range_commonnumber_count(ll l1, ll r1, ll l2, ll r2) {
vvll ranges = {{l1, r1}, {l2, r2}};
SORT(ranges);
if (ranges[0][1] <= ranges[1][0]) return _0;
ll L = ranges[1][0], R = min(ranges[0][1], ranges[1][1]);
return R - L;
}
string ll2str(ll x, ll base) {
if(x == 0) return "0";
stringstream ss;
string ret;
auto ll2base = [&]() {
stringstream tmp;
string cs = "0123456789" + alpha() + alpha_big();
while (x != 0) {
ll idx = 0;
if (x > 0) {
idx = x % abs(base);
} else {
idx = (abs(base) - (abs(x) % abs(base))) % abs(base);
}
x = (x - idx) / base;
tmp << cs[idx];
}
ret = tmp.str();
REV(ret);
};
ll2base();
return ret;
}
template <typename T>
pair<unordered_map<T, ll>, vector<T>> compcoord(const vector<T> &vec)
{
set<T> s = set<T>(all(vec));
unordered_map<T, ll> d;
ll idx = 0;
repset (v, s) d[v] = idx++;
vector<T> revd = vector<T>(len(s));
repdict(k, v, d) revd[v] = k;
return make_pair(d, revd);
}
ll mysqrt(ll n) {
ll ok = 0, ng = n + 1;
while (ng - ok > 1) {
ll mid = (ng + ok) >> 1;
if (mid * mid <= n) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
ll POW(ll n, ll r)
{
if (r == 0) return 1;
else if (r % 2 == 0) return POW(n * n, (ll)(r / 2));
else return n * POW(n, r - 1);
}
// 小数を表す文字列を小数部分が整数で表せるように数値をオフセットして
// 整数値にして返す。
// 例えば、dblstr2ll("123.456", 3)は123456
// 例えば、dblstr2ll("123.0456", 5)は12304560
// LLONG_MAXを超えないように注意
ll dblstr2ll(const string &dblstr, ll fractional_part_cnt) {
ll idx = 0;
string X = "", Y = "";
while(idx != len(dblstr) && dblstr[idx] != '.') {
X += dblstr[idx];
idx++;
}
idx++;
while(idx < len(dblstr)) {
Y += dblstr[idx];
idx++;
}
return STRLL(X) * POW(10, fractional_part_cnt) + STRLL(Y) * POW(10, fractional_part_cnt - len(Y));
}
vvll getdir4() {
return {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
}
vvll getdir8() {
return {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};
}
constexpr ll safe_mod(ll x, ll m) {
x %= m;
if (x < 0) x += m;
return x;
}
#define mod_m2p(a, m) (((m) + (a)) % (m))
#define mod_add(a, b, m) (((a) + (b)) % (m))
#define mod_sub(a, b, m) (((m) + (a) - (b)) % (m))
#define mod_mul(a, b, m) (mod_m2p(((a) % (m)) * ((b) % (m)), (m)))
ll mod_bipow_(ll x, ll y, ll m) { // x^y by bisection method
if (y == 0) return 1 % m;
else if (y == 1) return x % m;
else if (y % 2 == 0) {
ll val = mod_bipow_(x, (ll)(y / 2), m);
return mod_mul(val, val, m);
} else {
ll val = mod_bipow_(x, (ll)(y / 2), m);
return mod_mul(mod_mul(val, val, m), x, m);
}
}
ll mod_inv(ll x, ll pm) { return mod_bipow_(mod_m2p(x, pm), pm - 2, pm); } // x^{-1} = x^{MOD-2} (MOD: prime number)
ll mod_div(ll a, ll b, ll m) { return mod_mul(mod_m2p(a, m), mod_inv(mod_m2p(b, m), m), m); } // a/b = a*b^{-1}
ll mod_bipow(ll x, ll y, ll m) {
if (y < 0) {
ll xx = mod_div((ll)1, x, m);
return mod_bipow_(xx, -y, m);
}
return mod_bipow_(x, y, m);
}
constexpr std::pair<ll, ll> inv_gcd(ll a, ll b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
ll s = b, t = a;
ll m0 = 0, m1 = 1;
while (t) {
ll u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
ll inv_mod(ll x, ll m) {
assert(1 <= m);
auto z = inv_gcd(x, m);
assert(z.first == 1);
return z.second;
}
vll make_divisors(ll n) {
vll divisors;
for(ll i = 1; i * i <= n; ++i) {
if(n % i == 0) {
divisors.pb(i);
if(i != n / i) {
divisors.pb(n / i);
}
}
}
return divisors;
}
template <class S,
S (*op)(const S&, const S&),
S (*e)(),
class F,
S (*mapping)(const F&, const S&),
F (*composition)(const F&, const F&),
F (*id)()>
struct lazy_segtree {
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
// 遅延セグ木パターン
struct LazyAdd{ll c = 0;};
struct LazyUpdate{ll c = 0; bool isChange = false;};
struct DataMax {ll x = 0;};
struct DataMin {ll x = LLONG_MAX;};
struct DataSum {ll x = 0; ll size = 1;};
DataMax Marge(const DataMax &d1, const DataMax &d2) {return {max(d1.x, d2.x)};}
DataMax EDataMax() {DataMax ret; return ret;}
DataMin Marge(const DataMin &d1, const DataMin &d2) {return {min(d1.x, d2.x)};}
DataMin EDataMin() {DataMin ret; return ret;}
DataSum Marge(const DataSum &d1, const DataSum &d2) {return {d1.x + d2.x, d1.size + d2.size};}
DataSum EDataSum() {DataSum ret; return ret;}
DataMax MappingAdd(const LazyAdd &f, const DataMax &x) {return {x.x + f.c};}
DataMin MappingAdd(const LazyAdd &f, const DataMin &x) {return {x.x + f.c};}
DataSum MappingAdd(const LazyAdd &f, const DataSum &x) {return {x.x + f.c * x.size, x.size};}
LazyAdd CompositionAdd(const LazyAdd &ct2, const LazyAdd &ct1) {return {ct2.c + ct1.c};}
LazyAdd IdentityAdd() {LazyAdd ret; return ret;}
DataMax MappingUpdate(const LazyUpdate &f, const DataMax &x) {DataMax ret = x; if (f.isChange) ret.x = f.c; return ret;}
DataMin MappingUpdate(const LazyUpdate &f, const DataMin &x) {DataMin ret = x; if (f.isChange) ret.x = f.c; return ret;}
DataSum MappingUpdate(const LazyUpdate &f, const DataSum &x) {DataSum ret = x; if (f.isChange) ret.x = f.c * x.size; return ret;}
LazyUpdate CompositionUpdate(const LazyUpdate &ct2, const LazyUpdate &ct1) {return ct2.isChange ? ct2 : ct1;}
LazyUpdate IdentityUpdate() {LazyUpdate ret; return ret;}
// 区間加算、最大値取得
// vector<DataMax> v0(limit + 10, DataMax{0});
// auto LST = LazySegTreeGetMaxRangeChangeAdd(v0);
// // [L, R) の区間に適用
// LST.apply(max(0, L), min(limit, R), LazyAdd{1});
// // [L, R) の区間の値を取得
// chmax(ans, LST.prod(max(0, L), min(limit, R)).x);
using LazySegTreeGetMaxRangeChangeAdd = lazy_segtree<DataMax, Marge, EDataMax, LazyAdd, MappingAdd, CompositionAdd, IdentityAdd>;
// 区間加算、最小値取得
// vector<DataMin> v0(limit + 10, DataMin{LLONG_MAX});
// auto LST = LazySegTreeGetMinRangeChangeAdd(v0);
// // [L, R) の区間に適用
// LST.apply(max(0, L), min(limit, R), LazyAdd{1});
// // [L, R) の区間の値を取得
// chmax(ans, LST.prod(max(0, L), min(limit, R)).x);
using LazySegTreeGetMinRangeChangeAdd = lazy_segtree<DataMin, Marge, EDataMin, LazyAdd, MappingAdd, CompositionAdd, IdentityAdd>;
// 区間加算、区間和取得
// vector<DataSum> v0(limit + 10, DataSum{0});
// auto LST = LazySegTreeGetSUMRangeChangeAdd(v0);
// // [L, R) の区間に適用
// LST.apply(max(0, L), min(limit, R), LazyAdd{1});
// // [L, R) の区間の値を取得
// chmax(ans, LST.prod(max(0, L), min(limit, R)).x);
using LazySegTreeGetSUMRangeChangeAdd = lazy_segtree<DataSum, Marge, EDataSum, LazyAdd, MappingAdd, CompositionAdd, IdentityAdd>;
// 区間更新、最大値取得
// vector<DataMax> v0(limit + 10, DataMax{0});
// auto LST = LazySegTreeGetMaxRangeUpdate(v0);
// // [L, R) の区間に適用
// LST.apply(max(0, L), min(limit, R), LazyUpdate{1, true}); // trueにすることで更新したことを伝える
// // [L, R) の区間の値を取得
// chmax(ans, LST.prod(max(0, L), min(limit, R)).x);
using LazySegTreeGetMaxRangeUpdate = lazy_segtree<DataMax, Marge, EDataMax, LazyUpdate, MappingUpdate, CompositionUpdate, IdentityUpdate>;
// 区間更新、最小値取得
// vector<DataMin> v0(limit + 10, DataMin{LLONG_MAX});
// auto LST = LazySegTreeGetMinRangeUpdate(v0);
// // [L, R) の区間に適用
// LST.apply(max(0, L), min(limit, R), LazyUpdate{1, true}); // trueにすることで更新したことを伝える
// // [L, R) の区間の値を取得
// chmax(ans, LST.prod(max(0, L), min(limit, R)).x);
using LazySegTreeGetMinRangeUpdate = lazy_segtree<DataMin, Marge, EDataMin, LazyUpdate, MappingUpdate, CompositionUpdate, IdentityUpdate>;
// 区間更新、区間和取得
// vector<DataSum> v0(limit + 10, DataSum{0});
// auto LST = LazySegTreeGetSUMRangeUpdate(v0);
// // [L, R) の区間に適用
// LST.apply(max(0, L), min(limit, R), LazyUpdate{1, true}); // trueにすることで更新したことを伝える
// // [L, R) の区間の値を取得
// chmax(ans, LST.prod(max(0, L), min(limit, R)).x);
using LazySegTreeGetSUMRangeUpdate = lazy_segtree<DataSum, Marge, EDataSum, LazyUpdate, MappingUpdate, CompositionUpdate, IdentityUpdate>;
// 値を返すときに必要な情報
struct Data {ll x = 0;};
// クエリ処理をするために必要な情報
struct Lazy{ll c = 0;};
// Dataの初期値(構造体に初期値書くのでここは何も書かなくて良いかも)
Data E() {return {};}
// Lazy型の初期値(構造体に初期値書くのでここは何も書かなくて良いかも)
Lazy Identity() {return {};}
// Data同士をマージするときの処理
Data Marge(const Data &d1, const Data &d2) {
UNUSED(d1);
UNUSED(d2);
return {};
}
// クエリ処理をDataに適用したときの値の変化を記述
Data Mapping(const Lazy &f, const Data &x) {
UNUSED(f);
UNUSED(x);
return {};
}
// クエリ処理の統合処理を記述(統合順序としては、f1適用してからg2が適用される)
Lazy Composition(const Lazy &g2, const Lazy &f1) {
UNUSED(g2);
UNUSED(f1);
return {};
}
using LazySeg = lazy_segtree<Data, Marge, E, Lazy, Mapping, Composition, Identity>;
#include __FILE__
#endif