#include using namespace std; typedef long long ll; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b #define vl vector #define vii vector> #define vll vector> #define vvi vector> #define vvl vector> #define vvii vector>> #define vvll vector>> #define vst vector #define pii pair #define pll pair #define pb push_back #define all(x) (x).begin(),(x).end() #define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end()) #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=300005,INF=15<<26; // crt + floor_sum //https://github.com/atcoder/ac-library/releases/tag/v1.4 constexpr long long safe_mod(long long x, long long m) { x %= m; if (x < 0) x += m; return x; } constexpr std::pair 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}; } std::pair crt(const std::vector& r, const std::vector& 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 = 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) = 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}; } unsigned long long floor_sum_unsigned(unsigned long long n, unsigned long long m, unsigned long long a, unsigned long long b) { unsigned long long ans = 0; while (true) { if (a >= m) { ans += n * (n - 1) / 2 * (a / m); a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } unsigned long long y_max = a * n + b; if (y_max < m) break; n = (unsigned long long)(y_max / m); b = (unsigned long long)(y_max % m); std::swap(m, a); } return ans; } long long floor_sum(long long n, long long m, long long a, long long b) { assert(0 <= n && n < (1LL << 32)); assert(1 <= m && m < (1LL << 32)); unsigned long long ans = 0; if (a < 0) { unsigned long long a2 = safe_mod(a, m); ans -= 1ULL * n * (n - 1) / 2 * ((a2 - a) / m); a = a2; } if (b < 0) { unsigned long long b2 = safe_mod(b, m); ans -= 1ULL * n * ((b2 - b) / m); b = b2; } return ans + floor_sum_unsigned(n, m, a, b); } ll gcd(ll a,ll b){ if(b==0) return a; return gcd(b,a%b); } ll keta=3; string f3(ll x){ string res; for(ll q=0;q>N>>M; keta=N; ll b2=(1LL< SE; vll Z(b3/3); vl A(N); for(int i=0;iM) ans++; } if(Z[i].se-(Z[j-1].se+2)+b3*b4>M) ans++; i=j; } cout<