atcoder_template
| 投稿者 | ふらわぁ |
|---|---|
| 言語 | C++23 |
| 更新日時 (JST) | 2026-10-17 13:34:03 |
| サイズ | 72,658 Byte |
| 参照URL | |
日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。
//from https://yukicoder.me/users/24897/ai_code/29
#include <bits/stdc++.h>
using namespace std;
#ifdef _MSC_VER
#include <intrin.h>
#endif
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using P = pair<ll, ll>;
#define endl "\n"
#define rep1(i,n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i,a,b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define OVERLOAD_REP(_1,_2,_3,name,...) name
#define rep(...) OVERLOAD_REP(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define rrep(i,n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define all(s) (s).begin(), (s).end()
#define fi first
#define se second
constexpr int MINT_MOD = 998244353;
const ll mod = MINT_MOD;
const ll inf = 4000000000000000000ll;
const ld eps = ld(0.00000000001);
static const long double pi = 3.141592653589793;
constexpr ll MAX = 2000010;
template<class T>void vcin(vector<T> &n){for(int i=0;i<int(n.size());i++) cin>>n[i];}
template<class T,class K>void vcin(vector<T> &n,vector<K> &m){for(int i=0;i<int(n.size());i++) cin>>n[i]>>m[i];}
template<class T>void vcout(vector<T> &n){for(int i=0;i<int(n.size());i++){cout<<n[i]<<" ";}cout<<endl;}
template<class T>void vcin(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cin>>n[i][j];}}}
template<class T>void vcout(vector<vector<T>> &n){for(int i=0;i<int(n.size());i++){for(int j=0;j<int(n[i].size());j++){cout<<n[i][j]<<" ";}cout<<endl;}cout<<endl;}
void yes(bool a){cout<<(a?"yes":"no")<<endl;}
void YES(bool a){cout<<(a?"YES":"NO")<<endl;}
void Yes(bool a){cout<<(a?"Yes":"No")<<endl;}
void possible(bool a){ cout<<(a?"possible":"impossible")<<endl; }
void Possible(bool a){ cout<<(a?"Possible":"Impossible")<<endl; }
void POSSIBLE(bool a){ cout<<(a?"POSSIBLE":"IMPOSSIBLE")<<endl; }
template<class T,class F>void print(pair<T,F> a){cout<<a.fi<<" "<<a.se<<endl;}
template<class T>auto min(const T& a){ return *min_element(all(a)); }
template<class T>auto max(const T& a){ return *max_element(all(a)); }
template<class T,class U>bool chmax(T &a,const U b) { if (a<b) { a=b; return 1; } return 0;}
template<class T,class U>bool chmin(T &a,const U b) { if (b<a) { a=b; return 1; } return 0;}
template<class T> void ifmin(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template<class T> void ifmax(T t,T u){if(t>u){cout<<-1<<endl;}else{cout<<t<<endl;}}
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template <class T> using VVV = V<V<V<T>>>;
template <class T>
auto mvec(T val, ll n) { return V<T>(n, val); }
template <class T, class... Args>
auto mvec(T val, ll n, Args... args) {
return V<decltype(mvec(val, args...))>(n, mvec(val, args...));
}
vector<ll> divisor(ll x){ vector<ll> ans; for(ll i = 1; i * i <= x; i++){ if(x % i == 0) {ans.push_back(i); if(i*i!=x){ ans.push_back(x / i);}}}sort(all(ans)); return ans; }
ll pop(ll x){return __builtin_popcountll(x);}
ll poplong(ll x){ll y=-1;while(x){x/=2;y++;}return y;}
P hyou(P a){ll x=gcd(abs(a.fi),abs(a.se));a.fi/=x;a.se/=x;if(a.se<0){a.fi*=-1;a.se*=-1;}return a;}
P Pplus(P a,P b){ return hyou({a.fi*b.se+b.fi*a.se,a.se*b.se});}
P Ptimes(P a,ll b){ return hyou({a.fi*b,a.se});}
P Ptimes(P a,P b){ return hyou({a.fi*b.fi,a.se*b.se});}
P Pminus(P a,P b){ return hyou({a.fi*b.se-b.fi*a.se,a.se*b.se});}
P Pgyaku(P a){ return hyou({a.se,a.fi});}
void cincout(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout<< fixed << setprecision(15);
}
namespace atcoder {
namespace internal {
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
}
}
namespace atcoder {
namespace internal {
constexpr long long safe_mod(long long x, long long m) {
x %= m;
if (x < 0) x += m;
return x;
}
struct barrett {
unsigned int _m;
unsigned long long im;
barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
unsigned int umod() const { return _m; }
unsigned int mul(unsigned int a, unsigned int b) const {
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;
}
};
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;
}
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;
for (long long a : {2, 7, 61}) {
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);
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};
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;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
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 atcoder {
namespace internal {
#ifndef _MSC_VER
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;
#else
template <class T> using is_integral = typename std::is_integral<T>;
template <class T>
using is_signed_int =
typename std::conditional<is_integral<T>::value && std::is_signed<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,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type;
#endif
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;
}
}
namespace atcoder {
namespace internal {
struct modint_base {};
struct static_modint_base : modint_base {};
template <class T> using is_modint = std::is_base_of<modint_base, T>;
template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
}
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()); }
unsigned int val() const { return _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()); }
unsigned int val() const { return _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 atcoder {
namespace internal {
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly(std::vector<mint>& a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_e[30];
if (first) {
first = false;
mint es[30], ies[30];
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_e[i] = es[i] * now;
now *= ies[i];
}
}
for (int ph = 1; ph <= h; ph++) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint now = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p] * now;
a[i + offset] = l + r;
a[i + offset + p] = l - r;
}
now *= sum_e[bsf(~(unsigned int)(s))];
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
void butterfly_inv(std::vector<mint>& a) {
static constexpr int g = internal::primitive_root<mint::mod()>;
int n = int(a.size());
int h = internal::ceil_pow2(n);
static bool first = true;
static mint sum_ie[30];
if (first) {
first = false;
mint es[30], ies[30];
int cnt2 = bsf(mint::mod() - 1);
mint e = mint(g).pow((mint::mod() - 1) >> cnt2), ie = e.inv();
for (int i = cnt2; i >= 2; i--) {
es[i - 2] = e;
ies[i - 2] = ie;
e *= e;
ie *= ie;
}
mint now = 1;
for (int i = 0; i < cnt2 - 2; i++) {
sum_ie[i] = ies[i] * now;
now *= es[i];
}
}
for (int ph = h; ph >= 1; ph--) {
int w = 1 << (ph - 1), p = 1 << (h - ph);
mint inow = 1;
for (int s = 0; s < w; s++) {
int offset = s << (h - ph + 1);
for (int i = 0; i < p; i++) {
auto l = a[i + offset];
auto r = a[i + offset + p];
a[i + offset] = l + r;
a[i + offset + p] =
(unsigned long long)(mint::mod() + l.val() - r.val()) *
inow.val();
}
inow *= sum_ie[bsf(~(unsigned int)(s))];
}
}
}
}
template <class mint, internal::is_static_modint_t<mint>* = nullptr>
std::vector<mint> convolution(std::vector<mint> a, std::vector<mint> b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
if (std::min(n, m) <= 60) {
if (n < m) {
std::swap(n, m);
std::swap(a, b);
}
std::vector<mint> ans(n + m - 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[i + j] += a[i] * b[j];
}
}
return ans;
}
int z = 1 << internal::ceil_pow2(n + m - 1);
a.resize(z);
internal::butterfly(a);
b.resize(z);
internal::butterfly(b);
for (int i = 0; i < z; i++) {
a[i] *= b[i];
}
internal::butterfly_inv(a);
a.resize(n + m - 1);
mint iz = mint(z).inv();
for (int i = 0; i < n + m - 1; i++) a[i] *= iz;
return a;
}
template <unsigned int mod = 998244353,
class T,
std::enable_if_t<internal::is_integral<T>::value>* = nullptr>
std::vector<T> convolution(const std::vector<T>& a, const std::vector<T>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
using mint = static_modint<mod>;
std::vector<mint> a2(n), b2(m);
for (int i = 0; i < n; i++) {
a2[i] = mint(a[i]);
}
for (int i = 0; i < m; i++) {
b2[i] = mint(b[i]);
}
auto c2 = convolution(move(a2), move(b2));
std::vector<T> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
c[i] = c2[i].val();
}
return c;
}
std::vector<long long> convolution_ll(const std::vector<long long>& a,
const std::vector<long long>& b) {
int n = int(a.size()), m = int(b.size());
if (!n || !m) return {};
static constexpr unsigned long long MOD1 = 754974721;
static constexpr unsigned long long MOD2 = 167772161;
static constexpr unsigned long long MOD3 = 469762049;
static constexpr unsigned long long M2M3 = MOD2 * MOD3;
static constexpr unsigned long long M1M3 = MOD1 * MOD3;
static constexpr unsigned long long M1M2 = MOD1 * MOD2;
static constexpr unsigned long long M1M2M3 = MOD1 * MOD2 * MOD3;
static constexpr unsigned long long i1 =
internal::inv_gcd(MOD2 * MOD3, MOD1).second;
static constexpr unsigned long long i2 =
internal::inv_gcd(MOD1 * MOD3, MOD2).second;
static constexpr unsigned long long i3 =
internal::inv_gcd(MOD1 * MOD2, MOD3).second;
auto c1 = convolution<MOD1>(a, b);
auto c2 = convolution<MOD2>(a, b);
auto c3 = convolution<MOD3>(a, b);
std::vector<long long> c(n + m - 1);
for (int i = 0; i < n + m - 1; i++) {
unsigned long long x = 0;
x += (c1[i] * i1) % MOD1 * M2M3;
x += (c2[i] * i2) % MOD2 * M1M3;
x += (c3[i] * i3) % MOD3 * M1M2;
long long diff =
c1[i] - internal::safe_mod((long long)(x), (long long)(MOD1));
if (diff < 0) diff += MOD1;
static constexpr unsigned long long offset[5] = {
0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3};
x -= offset[diff % 5];
c[i] = x;
}
return c;
}
}
namespace atcoder {
struct dsu {
public:
dsu() : _n(0) {}
dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
std::vector<int> parent_or_size;
};
}
namespace atcoder {
template <class T> struct fenwick_tree {
using U = internal::to_unsigned_t<T>;
public:
fenwick_tree() : _n(0) {}
fenwick_tree(int n) : _n(n), data(n) {}
void add(int p, T x) {
assert(0 <= p && p < _n);
p++;
while (p <= _n) {
data[p - 1] += U(x);
p += p & -p;
}
}
T sum(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
return sum(r) - sum(l);
}
private:
int _n;
std::vector<U> data;
U sum(int r) {
U s = 0;
while (r > 0) {
s += data[r - 1];
r -= r & -r;
}
return s;
}
};
}
namespace atcoder {
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, 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();
}
};
}
namespace atcoder {
long long pow_mod(long long x, long long n, int m) {
assert(0 <= n && 1 <= m);
if (m == 1) return 0;
internal::barrett bt((unsigned int)(m));
unsigned int r = 1, y = (unsigned int)(internal::safe_mod(x, m));
while (n) {
if (n & 1) r = bt.mul(r, y);
y = bt.mul(y, y);
n >>= 1;
}
return r;
}
long long inv_mod(long long x, long long m) {
assert(1 <= m);
auto z = internal::inv_gcd(x, m);
assert(z.first == 1);
return z.second;
}
std::pair<long long, long long> crt(const std::vector<long long>& r,
const std::vector<long long>& m) {
assert(r.size() == m.size());
int n = int(r.size());
long long r0 = 0, m0 = 1;
for (int i = 0; i < n; i++) {
assert(1 <= m[i]);
long long r1 = internal::safe_mod(r[i], m[i]), m1 = m[i];
if (m0 < m1) {
std::swap(r0, r1);
std::swap(m0, m1);
}
if (m0 % m1 == 0) {
if (r0 % m1 != r1) return {0, 0};
continue;
}
long long g, im;
std::tie(g, im) = internal::inv_gcd(m0, m1);
long long u1 = (m1 / g);
if ((r1 - r0) % g) return {0, 0};
long long x = (r1 - r0) / g % u1 * im % u1;
r0 += x * m0;
m0 *= u1;
if (r0 < 0) r0 += m0;
}
return {r0, m0};
}
long long floor_sum(long long n, long long m, long long a, long long b) {
long long ans = 0;
if (a >= m) {
ans += (n - 1) * n * (a / m) / 2;
a %= m;
}
if (b >= m) {
ans += n * (b / m);
b %= m;
}
long long y_max = (a * n + b) / m, x_max = (y_max * m - b);
if (y_max == 0) return ans;
ans += (n - (x_max + a - 1) / a) * y_max;
ans += floor_sum(y_max, a, m, (a - x_max % a) % a);
return ans;
}
}
namespace atcoder {
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++; }
};
}
}
namespace atcoder {
template <class Cap> struct mf_graph {
public:
mf_graph() : _n(0) {}
mf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
assert(0 <= cap);
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
g[from].push_back(_edge{to, int(g[to].size()), cap});
g[to].push_back(_edge{from, int(g[from].size()) - 1, 0});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result;
for (int i = 0; i < m; i++) {
result.push_back(get_edge(i));
}
return result;
}
void change_edge(int i, Cap new_cap, Cap new_flow) {
int m = int(pos.size());
assert(0 <= i && i < m);
assert(0 <= new_flow && new_flow <= new_cap);
auto& _e = g[pos[i].first][pos[i].second];
auto& _re = g[_e.to][_e.rev];
_e.cap = new_cap - new_flow;
_re.cap = new_flow;
}
Cap flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
Cap flow(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
std::vector<int> level(_n), iter(_n);
internal::simple_queue<int> que;
auto bfs = [&]() {
std::fill(level.begin(), level.end(), -1);
level[s] = 0;
que.clear();
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (auto e : g[v]) {
if (e.cap == 0 || level[e.to] >= 0) continue;
level[e.to] = level[v] + 1;
if (e.to == t) return;
que.push(e.to);
}
}
};
auto dfs = [&](auto self, int v, Cap up) {
if (v == s) return up;
Cap res = 0;
int level_v = level[v];
for (int& i = iter[v]; i < int(g[v].size()); i++) {
_edge& e = g[v][i];
if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
Cap d =
self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
if (d <= 0) continue;
g[v][i].cap += d;
g[e.to][e.rev].cap -= d;
res += d;
if (res == up) break;
}
return res;
};
Cap flow = 0;
while (flow < flow_limit) {
bfs();
if (level[t] == -1) break;
std::fill(iter.begin(), iter.end(), 0);
while (flow < flow_limit) {
Cap f = dfs(dfs, t, flow_limit - flow);
if (!f) break;
flow += f;
}
}
return flow;
}
std::vector<bool> min_cut(int s) {
std::vector<bool> visited(_n);
internal::simple_queue<int> que;
que.push(s);
while (!que.empty()) {
int p = que.front();
que.pop();
visited[p] = true;
for (auto e : g[p]) {
if (e.cap && !visited[e.to]) {
visited[e.to] = true;
que.push(e.to);
}
}
}
return visited;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
}
namespace atcoder {
template <class Cap, class Cost> struct mcf_graph {
public:
mcf_graph() {}
mcf_graph(int n) : _n(n), g(n) {}
int add_edge(int from, int to, Cap cap, Cost cost) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
int m = int(pos.size());
pos.push_back({from, int(g[from].size())});
g[from].push_back(_edge{to, int(g[to].size()), cap, cost});
g[to].push_back(_edge{from, int(g[from].size()) - 1, 0, -cost});
return m;
}
struct edge {
int from, to;
Cap cap, flow;
Cost cost;
};
edge get_edge(int i) {
int m = int(pos.size());
assert(0 <= i && i < m);
auto _e = g[pos[i].first][pos[i].second];
auto _re = g[_e.to][_e.rev];
return edge{
pos[i].first, _e.to, _e.cap + _re.cap, _re.cap, _e.cost,
};
}
std::vector<edge> edges() {
int m = int(pos.size());
std::vector<edge> result(m);
for (int i = 0; i < m; i++) {
result[i] = get_edge(i);
}
return result;
}
std::pair<Cap, Cost> flow(int s, int t) {
return flow(s, t, std::numeric_limits<Cap>::max());
}
std::pair<Cap, Cost> flow(int s, int t, Cap flow_limit) {
return slope(s, t, flow_limit).back();
}
std::vector<std::pair<Cap, Cost>> slope(int s, int t) {
return slope(s, t, std::numeric_limits<Cap>::max());
}
std::vector<std::pair<Cap, Cost>> slope(int s, int t, Cap flow_limit) {
assert(0 <= s && s < _n);
assert(0 <= t && t < _n);
assert(s != t);
std::vector<Cost> dual(_n, 0), dist(_n);
std::vector<int> pv(_n), pe(_n);
std::vector<bool> vis(_n);
auto dual_ref = [&]() {
std::fill(dist.begin(), dist.end(),
std::numeric_limits<Cost>::max());
std::fill(pv.begin(), pv.end(), -1);
std::fill(pe.begin(), pe.end(), -1);
std::fill(vis.begin(), vis.end(), false);
struct Q {
Cost key;
int to;
bool operator<(Q r) const { return key > r.key; }
};
std::priority_queue<Q> que;
dist[s] = 0;
que.push(Q{0, s});
while (!que.empty()) {
int v = que.top().to;
que.pop();
if (vis[v]) continue;
vis[v] = true;
if (v == t) break;
for (int i = 0; i < int(g[v].size()); i++) {
auto e = g[v][i];
if (vis[e.to] || !e.cap) continue;
Cost cost = e.cost - dual[e.to] + dual[v];
if (dist[e.to] - dist[v] > cost) {
dist[e.to] = dist[v] + cost;
pv[e.to] = v;
pe[e.to] = i;
que.push(Q{dist[e.to], e.to});
}
}
}
if (!vis[t]) {
return false;
}
for (int v = 0; v < _n; v++) {
if (!vis[v]) continue;
dual[v] -= dist[t] - dist[v];
}
return true;
};
Cap flow = 0;
Cost cost = 0, prev_cost = -1;
std::vector<std::pair<Cap, Cost>> result;
result.push_back({flow, cost});
while (flow < flow_limit) {
if (!dual_ref()) break;
Cap c = flow_limit - flow;
for (int v = t; v != s; v = pv[v]) {
c = std::min(c, g[pv[v]][pe[v]].cap);
}
for (int v = t; v != s; v = pv[v]) {
auto& e = g[pv[v]][pe[v]];
e.cap -= c;
g[v][e.rev].cap += c;
}
Cost d = -dual[s];
flow += c;
cost += c * d;
if (prev_cost == d) {
result.pop_back();
}
result.push_back({flow, cost});
prev_cost = cost;
}
return result;
}
private:
int _n;
struct _edge {
int to, rev;
Cap cap;
Cost cost;
};
std::vector<std::pair<int, int>> pos;
std::vector<std::vector<_edge>> g;
};
}
namespace atcoder {
namespace internal {
template <class E> struct csr {
std::vector<int> start;
std::vector<E> elist;
csr(int n, const std::vector<std::pair<int, E>>& edges)
: start(n + 1), elist(edges.size()) {
for (auto e : edges) {
start[e.first + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
auto counter = start;
for (auto e : edges) {
elist[counter[e.first]++] = e.second;
}
}
};
struct scc_graph {
public:
scc_graph(int n) : _n(n) {}
int num_vertices() { return _n; }
void add_edge(int from, int to) { edges.push_back({from, {to}}); }
std::pair<int, std::vector<int>> scc_ids() {
auto g = csr<edge>(_n, edges);
int now_ord = 0, group_num = 0;
std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
visited.reserve(_n);
auto dfs = [&](auto self, int v) -> void {
low[v] = ord[v] = now_ord++;
visited.push_back(v);
for (int i = g.start[v]; i < g.start[v + 1]; i++) {
auto to = g.elist[i].to;
if (ord[to] == -1) {
self(self, to);
low[v] = std::min(low[v], low[to]);
} else {
low[v] = std::min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.back();
visited.pop_back();
ord[u] = _n;
ids[u] = group_num;
if (u == v) break;
}
group_num++;
}
};
for (int i = 0; i < _n; i++) {
if (ord[i] == -1) dfs(dfs, i);
}
for (auto& x : ids) {
x = group_num - 1 - x;
}
return {group_num, ids};
}
std::vector<std::vector<int>> scc() {
auto ids = scc_ids();
int group_num = ids.first;
std::vector<int> counts(group_num);
for (auto x : ids.second) counts[x]++;
std::vector<std::vector<int>> groups(ids.first);
for (int i = 0; i < group_num; i++) {
groups[i].reserve(counts[i]);
}
for (int i = 0; i < _n; i++) {
groups[ids.second[i]].push_back(i);
}
return groups;
}
private:
int _n;
struct edge {
int to;
};
std::vector<std::pair<int, edge>> edges;
};
}
}
namespace atcoder {
struct scc_graph {
public:
scc_graph() : internal(0) {}
scc_graph(int n) : internal(n) {}
void add_edge(int from, int to) {
int n = internal.num_vertices();
assert(0 <= from && from < n);
assert(0 <= to && to < n);
internal.add_edge(from, to);
}
std::vector<std::vector<int>> scc() { return internal.scc(); }
private:
internal::scc_graph internal;
};
}
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
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());
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;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
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]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(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 (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(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;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
}
namespace atcoder {
namespace internal {
std::vector<int> sa_naive(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int l, int r) {
if (l == r) return false;
while (l < n && r < n) {
if (s[l] != s[r]) return s[l] < s[r];
l++;
r++;
}
return l == n;
});
return sa;
}
std::vector<int> sa_doubling(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n), rnk = s, tmp(n);
std::iota(sa.begin(), sa.end(), 0);
for (int k = 1; k < n; k *= 2) {
auto cmp = [&](int x, int y) {
if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
int rx = x + k < n ? rnk[x + k] : -1;
int ry = y + k < n ? rnk[y + k] : -1;
return rx < ry;
};
std::sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
std::swap(tmp, rnk);
}
return sa;
}
template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
int n = int(s.size());
if (n == 0) return {};
if (n == 1) return {0};
if (n == 2) {
if (s[0] < s[1]) {
return {0, 1};
} else {
return {1, 0};
}
}
if (n < THRESHOLD_NAIVE) {
return sa_naive(s);
}
if (n < THRESHOLD_DOUBLING) {
return sa_doubling(s);
}
std::vector<int> sa(n);
std::vector<bool> ls(n);
for (int i = n - 2; i >= 0; i--) {
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
}
std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
for (int i = 0; i < n; i++) {
if (!ls[i]) {
sum_s[s[i]]++;
} else {
sum_l[s[i] + 1]++;
}
}
for (int i = 0; i <= upper; i++) {
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
auto induce = [&](const std::vector<int>& lms) {
std::fill(sa.begin(), sa.end(), -1);
std::vector<int> buf(upper + 1);
std::copy(sum_s.begin(), sum_s.end(), buf.begin());
for (auto d : lms) {
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++) {
int v = sa[i];
if (v >= 1 && !ls[v - 1]) {
sa[buf[s[v - 1]]++] = v - 1;
}
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
for (int i = n - 1; i >= 0; i--) {
int v = sa[i];
if (v >= 1 && ls[v - 1]) {
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
};
std::vector<int> lms_map(n + 1, -1);
int m = 0;
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms_map[i] = m++;
}
}
std::vector<int> lms;
lms.reserve(m);
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms.push_back(i);
}
}
induce(lms);
if (m) {
std::vector<int> sorted_lms;
sorted_lms.reserve(m);
for (int v : sa) {
if (lms_map[v] != -1) sorted_lms.push_back(v);
}
std::vector<int> rec_s(m);
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
for (int i = 1; i < m; i++) {
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) {
same = false;
} else {
while (l < end_l) {
if (s[l] != s[r]) {
break;
}
l++;
r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
auto rec_sa =
sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);
for (int i = 0; i < m; i++) {
sorted_lms[i] = lms[rec_sa[i]];
}
induce(sorted_lms);
}
return sa;
}
}
std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
assert(0 <= upper);
for (int d : s) {
assert(0 <= d && d <= upper);
}
auto sa = internal::sa_is(s, upper);
return sa;
}
template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
int n = int(s.size());
std::vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
std::vector<int> s2(n);
int now = 0;
for (int i = 0; i < n; i++) {
if (i && s[idx[i - 1]] != s[idx[i]]) now++;
s2[idx[i]] = now;
}
return internal::sa_is(s2, now);
}
std::vector<int> suffix_array(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return internal::sa_is(s2, 255);
}
template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
const std::vector<int>& sa) {
int n = int(s.size());
assert(n >= 1);
std::vector<int> rnk(n);
for (int i = 0; i < n; i++) {
rnk[sa[i]] = i;
}
std::vector<int> lcp(n - 1);
int h = 0;
for (int i = 0; i < n; i++) {
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return lcp_array(s2, sa);
}
template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {
int n = int(s.size());
if (n == 0) return {};
std::vector<int> z(n);
z[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
int& k = z[i];
k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}
std::vector<int> z_algorithm(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return z_algorithm(s2);
}
}
namespace atcoder {
struct two_sat {
public:
two_sat() : _n(0), scc(0) {}
two_sat(int n) : _n(n), _answer(n), scc(2 * n) {}
void add_clause(int i, bool f, int j, bool g) {
assert(0 <= i && i < _n);
assert(0 <= j && j < _n);
scc.add_edge(2 * i + (f ? 0 : 1), 2 * j + (g ? 1 : 0));
scc.add_edge(2 * j + (g ? 0 : 1), 2 * i + (f ? 1 : 0));
}
bool satisfiable() {
auto id = scc.scc_ids().second;
for (int i = 0; i < _n; i++) {
if (id[2 * i] == id[2 * i + 1]) return false;
_answer[i] = id[2 * i] < id[2 * i + 1];
}
return true;
}
std::vector<bool> answer() { return _answer; }
private:
int _n;
std::vector<bool> _answer;
internal::scc_graph scc;
};
}
using namespace atcoder;
template<class T>
vector<T> NTT(vector<T> a,vector<T> b){
ll nmod=T::mod();
int n=a.size();
int m=b.size();
vector<int> x1(n);
vector<int> y1(m);
for(int i=0;i<n;i++){
ll tmp1;
tmp1=a[i].val();
x1[i]=tmp1;
}
for(int i=0;i<m;i++){
ll tmp1;
tmp1=b[i].val();
y1[i]=tmp1;
}
auto z1=convolution<167772161>(x1,y1);
auto z2=convolution<469762049>(x1,y1);
auto z3=convolution<1224736769>(x1,y1);
vector<T> res(n+m-1);
ll m1=167772161;
ll m2=469762049;
ll m3=1224736769;
ll m1m2=104391568;
ll m1m2m3=721017874;
ll mm12=m1*m2%nmod;
for(int i=0;i<n+m-1;i++){
int v1=(z2[i]-z1[i])*m1m2%m2;
if(v1<0) v1+=m2;
int v2=(z3[i]-(z1[i]+v1*m1)%m3)*m1m2m3%m3;
if(v2<0) v2+=m3;
res[i]=(z1[i]+v1*m1+v2*mm12);
}
return res;
}
template<class T>
struct FormalPowerSeries:vector<T>{
using vector<T>::vector;
using F=FormalPowerSeries;
FormalPowerSeries(const FormalPowerSeries&) = default;
F &operator=(const vector<T> &g){
int n=g.size();
(*this).resize(n);
for(int i=0;i<n;i++) (*this)[i]=g[i];
return (*this);
}
F &operator=(const F &g){
int n=g.size();
(*this).resize(n);
for(int i=0;i<n;i++) (*this)[i]=g[i];
return (*this);
}
F operator-() const {
F ret(*this);
for(int i=0;i<int(ret.size());i++) ret[i]*=-1;
return ret;
}
F &operator+=(const F &g){
int n=(*this).size();
int m=g.size();
if(n<m) (*this).resize(m);
for(int i=0;i<m;i++) (*this)[i]+=g[i];
return (*this);
}
F &operator+=(const T &r){
if(int((*this).size())==0) (*this).resize(1);
(*this)[0]+=r;
return (*this);
}
F &operator-=(const F &g){
int n=(*this).size();
int m=g.size();
if(n<m) (*this).resize(m);
for(int i=0;i<m;i++) (*this)[i]-=g[i];
return (*this);
}
F &operator-=(const T &r){
if(int((*this).size())==0) (*this).resize(1);
(*this)[0]-=r;
return (*this);
}
F &operator*=(const F &g){
(*this)=convolution((*this),g);
return (*this);
}
F &operator*=(const T &r){
for(int i=0;i<int((*this).size());i++) (*this)[i]*=r;
return (*this);
}
F &operator/=(const F &g){
int n=(*this).size();
(*this)=convolution((*this),g.inv());
(*this).resize(n);
return (*this);
}
F &operator/=(T r){
r=r.inv();
for(int i=0;i<int((*this).size());i++) (*this)[i]*=r;
return (*this);
}
F &operator%=(const F &g){
(*this)=(*this).division(g).second;
return (*this);
}
F &operator<<=(const int d) {
(*this).insert((*this).begin(),d,0);
return *this;
}
F &operator>>=(const int d) {
int n=(*this).size();
(*this).erase((*this).begin(),(*this).begin()+min(n, d));
return *this;
}
F operator*(const T &g) const { return F(*this)*=g;}
F operator-(const T &g) const { return F(*this)-=g;}
F operator+(const T &g) const { return F(*this)+=g;}
F operator/(const T &g) const { return F(*this)/=g;}
F operator*(const F &g) const { return F(*this)*=g;}
F operator-(const F &g) const { return F(*this)-=g;}
F operator+(const F &g) const { return F(*this)+=g;}
F operator/(const F &g) const { return F(*this)/=g;}
F operator%(const F &g) const { return F(*this)%=g;}
F operator<<(const int d) const { return F(*this)<<=d;}
F operator>>(const int d) const { return F(*this)>>=d;}
F pre(int sz) const {
return F(begin(*this), begin(*this) + min((int)this->size(), sz));
}
F inv(int deg=-1) const {
int n=(*this).size();
if(deg==-1) deg=n;
assert(n>0&&(*this)[0]!=T(0));
F g(1);
g[0]=(*this)[0].inv();
while(int(g.size())<deg){
int m=g.size();
F f(begin(*this),begin(*this)+min(n,2*m));
F r(g);
f.resize(2*m);
r.resize(2*m);
internal::butterfly(f);
internal::butterfly(r);
for(int i=0;i<2*m;i++) f[i]*=r[i];
internal::butterfly_inv(f);
f.erase(f.begin(),f.begin()+m);
f.resize(2*m);
internal::butterfly(f);
for(int i=0;i<2*m;i++) f[i]*=r[i];
internal::butterfly_inv(f);
T in=T(2*m).inv();
in*=-in;
for(int i=0;i<m;i++) f[i]*=in;
g.insert(g.end(),f.begin(),f.begin()+m);
}
return g.pre(deg);
}
T eval(const T &a){
T x=1;
T ret=0;
for(int i=0;i<int((*this).size());i++){
ret+=(*this)[i]*x;
x*=a;
}
return ret;
}
void onemul(const int d,const T c){
int n=(*this).size();
for(int i=n-d-1;i>=0;i--){
(*this)[i+d]+=(*this)[i]*c;
}
}
void onediv(const int d,const T c){
int n=(*this).size();
for(int i=0;i<n-d;i++){
(*this)[i+d]-=(*this)[i]*c;
}
}
F diff() const {
int n=(*this).size();
if(n==0) return F{};
F ret(n);
for(int i=1;i<n;i++) ret[i-1]=(*this)[i]*i;
return ret;
}
F integral() const {
int n=(*this).size(),mod =T::mod();
if(n==0) return F{};
vector<T> inv(n+1);
inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=T(mod)-inv[mod%i]*(mod/i);
F ret(n);
for(int i=n-2;i>=0;i--) ret[i+1]=(*this)[i]*inv[i+1];
ret[0]=0;
return ret;
}
F log(int deg=-1) const {
int n=(*this).size();
if(deg==-1) deg=n;
assert((*this)[0]==T(1));
return ((*this).diff()*(*this).inv(deg)).pre(deg).integral();
}
F exp(int deg=-1) const {
int n=(*this).size();
if(deg==-1) deg=n;
assert(n==0||(*this)[0]==0);
F Inv;
Inv.reserve(deg);
Inv.push_back(T(0));
Inv.push_back(T(1));
auto inplace_integral = [&](F& f) -> void {
const int n = (int)f.size();
int mod=T::mod();
while(int(Inv.size())<=n){
int i = Inv.size();
Inv.push_back((-Inv[mod%i])*(mod/i));
}
f.insert(begin(f),T(0));
for(int i=1;i<=n;i++) f[i]*=Inv[i];
};
auto inplace_diff = [](F &f) -> void {
if(f.empty()) return;
f.erase(begin(f));
T coeff=1;
for(int i=0;i<int(f.size());i++){
f[i]*=coeff;
coeff++;
}
};
F b{1,1<(int)(*this).size()?(*this)[1]:0},c{1},z1,z2{1,1};
for(int m=2;m<=deg;m<<=1){
auto y=b;
y.resize(2*m);
internal::butterfly(y);
z1=z2;
F z(m);
for(int i=0;i<m;i++) z[i]=y[i]*z1[i];
internal::butterfly_inv(z);
T si=T(m).inv();
for(int i=0;i<m;i++) z[i]*=si;
fill(begin(z),begin(z)+m/2,T(0));
internal::butterfly(z);
for(int i=0;i<m;i++) z[i]*=-z1[i];
internal::butterfly_inv(z);
for(int i=0;i<m;i++) z[i]*=si;
c.insert(end(c),begin(z)+m/2,end(z));
z2=c;
z2.resize(2*m);
internal::butterfly(z2);
F x(begin((*this)),begin((*this))+min<int>((*this).size(),m));
x.resize(m);
inplace_diff(x);
x.push_back(T(0));
internal::butterfly(x);
for(int i=0;i<m;i++) x[i]*=y[i];
internal::butterfly_inv(x);
for(int i=0;i<m;i++) x[i]*=si;
x-=b.diff();
x.resize(2*m);
for(int i=0;i<m-1;i++) x[m+i]=x[i],x[i]=T(0);
internal::butterfly(x);
for(int i=0;i<2*m;i++) x[i]*=z2[i];
internal::butterfly_inv(x);
T si2=T(m<<1).inv();
for(int i=0;i<2*m;i++) x[i]*=si2;
x.pop_back();
inplace_integral(x);
for(int i=m;i<min<int>(int((*this).size()),2*m);i++) x[i]+=(*this)[i];
fill(begin(x),begin(x)+m,T(0));
internal::butterfly(x);
for(int i=0;i<2*m;i++) x[i]*=y[i];
internal::butterfly_inv(x);
for(int i=0;i<2*m;i++) x[i]*=si2;
b.insert(end(b),begin(x)+m,end(x));
}
return b.pre(deg);
}
F pow(ll m){
int n=(*this).size();
int x=0;
while(x<int((*this).size())&&(*this)[x]==T(0)){
x++;
}
if(m==0){
F ret(n);
ret[0]=1;
return ret;
}
if(x*m>=n){
F ret(n);
return ret;
}
F f(n-x);
T y=(*this)[x];
for(int i=x;i<n;i++) f[i-x]=(*this)[i]/y;
f=f.log();
for(int i=0;i<int(f.size());i++) f[i]*=m;
f=f.exp();
y=y.pow(m);
for(int i=0;i<int(f.size());i++) f[i]*=y;
F ret(n);
for(int i=x*m;i<n;i++) ret[i]=f[i-x*m];
return ret;
}
F shift(T c){
int n=(*this).size();
int mod=T::mod();
vector<T> inv(n+1);
inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=mod-inv[mod%i]*(mod/i);
T x=1;
for(int i=0;i<n;i++){
(*this)[i]*=x;
x*=(i+1);
}
F g(n);
T y=1;
T now=1;
for(int i=0;i<n;i++){
g[n-i-1]=now*y;
now*=c;
y*=inv[i+1];
}
auto tmp=convolution(g,(*this));
T z=1;
for(int i=0;i<n;i++){
(*this)[i]=tmp[n+i-1]*z;
z*=inv[i+1];
}
return (*this);
}
pair<F,F> division(F g){
F f=(*this);
int n=f.size();
int m=g.size();
if(n<m){
F p(0);
return {p,f};
}
F p(n-m+1),q(n-m+1);
for(int i=0;i<n-m+1;i++) p[i]=f[n-i-1];
for(int i=0;i<n-m+1&&i<m;i++) q[i]=g[m-i-1];
p/=q;
for(int i=0;i<(n-m+1)/2;i++) swap(p[i],p[(n-m+1)-i-1]);
g.resize(n);
g*=p;
for(int i=0;i<n;i++) f[i]-=g[i];
int v=n-m+1,u=0;
for(int i=0;i<n;i++) if(f[i].val()) chmax(u,i+1);
p.resize(v);
f.resize(u);
return {p,f};
}
vector<T> multieva(vector<T> p){
int m=p.size();
int M=1;
int l=0;
while(M<m){
M*=2;
l++;
}
p.resize(M);
swap(m,M);
vector<vector<F>> g(l+1);
g[0].resize(m);
for(int i=0;i<m;i++){
g[0][i].resize(2);
g[0][i][0]=-p[i];
g[0][i][1]=1;
}
for(int i=0;i<l;i++){
g[i+1].resize(m>>(i+1));
for(int j=0;j<(m>>(i+1));j++) g[i+1][j]=g[i][2*j]*g[i][2*j+1];
}
g[l][0]=(*this).division(g[l][0]).se;
for(int i=l;i>=1;i--){
for(int j=0;j<(m>>(i-1));j++){
g[i-1][j]=g[i][j/2].division(g[i-1][j]).se;
}
}
for(int i=0;i<M;i++) if(g[0][i].size()==0) g[0][i].resize(1);
vector<T> ret(M);
for(int i=0;i<M;i++) ret[i]=g[0][i][0];
return ret;
}
};
template<class T>
void GaussJordan(vector<vector<T>> &A,bool is_extended = false){
ll m=A.size(),n=A[0].size();
ll rank=0;
for(int i=0;i<n;i++){
if(is_extended&&i==n-1) break;
ll p=-1;
for(int j=rank;j<m;j++){
if(A[j][i]!=T(0)){
p=j;
break;
}
}
if(p==-1) continue;
swap(A[p],A[rank]);
auto k=A[rank][i];
for(int i2=0;i2<n;i2++){
A[rank][i2]/=k;
}
for(int j=0;j<m;j++){
if(j!=rank&&A[j][i]!=T(0)){
auto fac=A[j][i];
for(int i2=0;i2<n;i2++){
A[j][i2]-=A[rank][i2]*fac;
}
}
}
rank++;
}
}
template<class T>
void linear_equation(vector<vector<T>> a, vector<T> b, vector<T> &res) {
ll m=int(a.size()),n=int(a[0].size());
vector<vector<T>> M(m,vector<T>(n+1));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
M[i][j]=a[i][j];
}
M[i][n]=b[i];
}
GaussJordan(M,true);
res.assign(n,0);
for(int i=0;i<n;i++) res[i]=M[i][n];
}
template<class F>
pair<F,F> Characteristic_equation(const F &a) {
using T=typename F::value_type;
ll n=a.size();
ll p=n/2;
ll u=p+(p+1);
vector<vector<T>> f(u,vector<T>(u));
f[0][0]=1;
for(int i=1;i<=p;i++){
f[i][i-1]=-1;
}
for(int i=p;i<u;i++){
ll t=0;
for(int j=1+i-p;j<u;j++){
f[j][i]=a[t];
t++;
}
}
vector<T> b(u);
b[0]=1;
vector<T> res(u);
linear_equation(f,b,res);
F X(p),Y(p+1);
for(int i=0;i<p;i++) X[i]=res[i];
for(int j=p;j<int(res.size());j++) Y[j-p]=res[j];
return {X,Y};
}
template <class T>
T getK(FormalPowerSeries<T> p, FormalPowerSeries<T> q,ll k){
if(int(p.size())==0) return 0;
if(k==0) return p[0]/q[0];
if(p.size()>=q.size()){
p=p.division(q).se;
}
if(q[0].val()!=1){
for(int i=0;i<int(p.size());i++) p[i]/=q[0];
for(int i=int(q.size())-1;i>=0;i--) q[i]/=q[0];
}
if(k<0) return T(0);
ll d=q.size();
p.resize(d-1);
while(k){
auto qn=q;
for(int i=1;i<d;i+=2) qn[i]*=-1;
p*=qn;
q*=qn;
for(int i=0;i<d-1;i++){
p[i]=p[(i<<1)|(k&1)];
}
for(int i=0;i<d;i++){
q[i]=q[(i<<1)];
}
p.resize(d-1);
q.resize(d);
k/=2;
}
return p[0];
}
using fpsmint = modint998244353;
using fps=FormalPowerSeries<fpsmint>;
using mint = static_modint<MINT_MOD>;
fps mergeconv(vector<fps> a){
while(int(a.size())>1){
ll n=a.size();
vector<fps> b((n+1)/2);
for(int i=0;i<int(a.size());i+=2){
if(i+1<int(a.size())) b[i/2]=a[i]*a[i+1];
else b[i/2]=a[i];
}
a=b;
}
return a[0];
}
pair<fps,fps> mergeconvfrac(vector<pair<fps,fps>> a){
while(a.size()>1){
ll n=a.size();
vector<pair<fps,fps>> b((n+1)/2);
for(int i=0;i<int(a.size());i+=2){
if(i+1<int(a.size())) b[i/2]={a[i].fi*a[i+1].se+a[i+1].fi*a[i].se,a[i].se*a[i+1].se};
else b[i/2]=a[i];
}
a=b;
}
return a[0];
}
vector<fpsmint> chirp_z_transform(ll n,ll m,fps x,fpsmint w,fpsmint a=fpsmint(1)){
vector<fpsmint> y(n),v(n+m-1);
vector<fpsmint> u(n+m-1);
u[0]=1;
for(int i=1;i<n+m-1;i++) u[i]=u[i-1]*w;
v[0]=1;
for(int i=1;i<n+m-1;i++) v[i]=v[i-1]*u[i-1];
fpsmint ap=1;
for(int i=0;i<n;i++){
y[i]=x[i]*ap/v[i];
ap*=a;
}
reverse(all(y));
y=convolution(y,v);
vector<fpsmint> ans(m);
for(int i=0;i<m;i++) ans[i]=y[n-1+i]/v[i];
return ans;
}
template<class T>
vector<T> all_inv(vector<T> p){
ll n=p.size();
vector<T> l(n),r(n);
T all=1;
for(int i=0;i<n;i++){
l[i]=r[i]=p[i];
all*=p[i];
}
for(int i=1;i<n;i++) l[i]*=l[i-1];
for(int i=n-2;i>=0;i--) r[i]*=r[i+1];
vector<T> ret(n);
all=all.inv();
for(int i=0;i<n;i++){
ret[i]=all;
if(i) ret[i]*=l[i-1];
if(i+1<n) ret[i]*=r[i+1];
}
return ret;
}
fps interpolation_geo(ll n,fpsmint q,vector<fpsmint> v){
vector<fpsmint> w(n);
vector<fpsmint> s(n+1);
s[0]=1;
vector<fpsmint> qp(n+1);
qp[0]=1;
for(int i=1;i<=n;i++) qp[i]=qp[i-1]*q;
for(int i=1;i<=n;i++){
s[i]=s[i-1]*(1-qp[i]);
}
vector<fpsmint> sinv=all_inv(s);
vector<fpsmint> qpp(n+1);
qpp[0]=1;
q=q.inv();
vector<fpsmint> qip(n+1);
qip[0]=1;
for(int i=1;i<=n;i++) qip[i]=qip[i-1]*q;
for(int i=0;i+1<n;i++) qpp[i+1]=qpp[i]*qip[n-i-2];
for(ll i=0;i<n;i++){
w[i]=v[i]*sinv[i]*sinv[n-i-1]*qpp[i];
if(i%2) w[i]*=-1;
}
fps f(n),g(n);
g=w;
for(int i=1;i<=n;i++) qp[i]*=qp[i-1];
for(ll i=0;i<n;i++){
f[i]=s[n]*sinv[i]*sinv[n-i];
if(i) f[i]*=qp[i-1];
if(i%2) f[i]*=-1;
}
q=q.inv();
g=chirp_z_transform(n,n,g,q);
fps h=(f*g).pre(n);
for(int i=0;i<n-i-1;i++) swap(h[i],h[n-i-1]);
return h;
}
fps interpolation(vector<fpsmint> x,vector<fpsmint> y){
ll n=x.size();
vector<fps> g1(n);
for(int i=0;i<n;i++) g1[i]=fps({-x[i],1});
fps g=mergeconv(g1);
fps g2=g;
g2=g2.diff();
auto g3=g2.multieva(x);
vector<pair<fps,fps>> f1(n);
for(int i=0;i<n;i++) f1[i]={fps({y[i]}),fps({-x[i]*g3[i],g3[i]})};
pair<fps,fps> f=mergeconvfrac(f1);
while(f.se[0].val()==0){
f.se>>=1;
g>>=1;
}
fps h=f.fi;
h/=f.se;
h*=g;
h.resize(n);
return h;
}
struct graph{
struct edge{
ll to,cost;
};
ll v;
vector<ll> b;
vector<vector<edge>> g;
vector<ll> d;
vector<bool> negative;
vector<bool> diameter;
vector<ll> topological_sort;
ll diametercost;
bool bipartitecheck;
vector<ll> bipartite;
graph(ll n){
init(n);
}
void init(ll n){
v=n;
g.resize(n);
d.resize(n);
b.resize(n);
negative.resize(n);
diameter.resize(n);
bipartite.resize(n);
for(int i=0;i<v;i++){
d[i]=inf;
bipartite[i]=-1;
negative[i]=false;
diameter[i]=false;
}
}
void addedge(ll s,ll t,ll cost){
edge e;
e.to=t;
e.cost=cost;
g[s].push_back(e);
}
void dijkstra(ll s){
for(int i=0;i<v;i++){
d[i]=inf;
}
d[s]=0;
priority_queue<P,vector<P>,greater<P>> que;
que.push(P(0,s));
while(!que.empty()){
P p=que.top();
que.pop();
ll V=p.second;
if(d[V]<p.first) continue;
for(auto e:g[V]){
if(d[e.to]>d[V]+e.cost){
d[e.to]=d[V]+e.cost;
b[e.to]=V;
que.push(P(d[e.to],e.to));
}
}
}
}
void BellmanFord(ll s){
for(int i=0;i<v;i++){
d[i]=inf;
negative[i]=false;
}
d[s]=0;
for(int i=0;i+1<v;i++){
bool update=false;
for(int V=0;V<v;V++){
if(d[V]==inf){
continue;
}
for(auto e:g[V]){
if(d[e.to]>d[V]+e.cost){
d[e.to]=d[V]+e.cost;
update=true;
}
}
}
if(!update) break;
}
queue<ll> que;
for(int V=0;V<v;V++){
if(d[V]==inf){
continue;
}
for(auto e:g[V]){
if(d[e.to]>d[V]+e.cost&&!negative[e.to]){
negative[e.to]=true;
que.push(e.to);
}
}
}
while(!que.empty()){
ll V=que.front();
que.pop();
for(auto e:g[V]){
if(!negative[e.to]){
negative[e.to]=true;
que.push(e.to);
}
}
}
for(int i=0;i<v;i++){
if(negative[i]) d[i]=-inf;
}
}
void bfs(ll s){
for(int i=0;i<v;i++){
d[i]=inf;
}
d[s]=0;
queue<ll> q;
q.push(s);
while(q.size()){
ll v=q.front();
q.pop();
for(auto e:g[v]){
assert(e.cost==1);
if(chmin(d[e.to],d[v]+1)){
b[e.to]=v;
q.push(e.to);
}
}
}
}
void treediameter(){
bfs(0);
ll p=0;
ll q=0;
for(int i=0;i<v;i++){
if(q<d[i]){
q=d[i];
p=i;
}
}
diameter[p]=true;
bfs(p);
ll p2=0;
ll q2=0;
for(int i=0;i<v;i++){
if(q2<d[i]){
q2=d[i];
p2=i;
}
}
diameter[p2]=true;
diametercost=d[p2];
}
void Bipartite(){
bipartitecheck=true;
for(int i=0;i<v;i++){
if(bipartite[i]==-1){
Bipartitedfs(i);
}
}
}
void Bipartitedfs(ll s,ll cur=0){
bipartite[s]=cur;
for(auto e:g[s]){
if(bipartite[e.to]!=-1){
if((bipartite[e.to]==bipartite[s])^(e.cost%2==0)){
bipartitecheck=false;
}
}
else{
if(e.cost%2){
Bipartitedfs(e.to,1-cur);
}
else{
Bipartitedfs(e.to,cur);
}
}
}
}
void topologicalsort(){
for(int i=0;i<v;i++){
d[i]=0;
}
for(int i=0;i<v;i++){
if(d[i]) continue;
topologicaldfs(i);
}
reverse(all(topological_sort));
}
void topologicaldfs(ll a){
d[a]=1;
for(auto e:g[a]){
if(d[e.to]) continue;
topologicaldfs(e.to);
}
topological_sort.push_back(a);
}
};
ll 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%mod;
inv[i]=mod-inv[mod%i]*(mod/i)%mod;
finv[i]=finv[i-1]*inv[i]%mod;
}
}
ll binom(ll n,ll k){
if(n<k) return 0;
if(n<0||k<0) return 0;
return fac[n]*(finv[k]*finv[n-k]%mod)%mod;
}
ll pownk(ll n,ll k){
if(n==0&&k==0) return 1;
return binom(n+k-1,k);
}
ll catalan(ll n){
return binom(2*n,n)*inv[n+1]%mod;
}
int main(){
cincout();
return 0;
}