/*********** [ scopeInfinity ] ******************/ #include using namespace std; typedef long long ll; typedef long double ld; typedef std::vector vll; typedef std::vector > vpi; typedef std::vector > vpl; typedef std::vector vi; ll MOD = 1e9+7; ll PRIME = 999727999; ll PRIME2 = 999999937; ll INF = LLONG_MAX/4; #define forv(it,m) for (auto it = (m).begin(); it != (m).end(); ++it) #define rep(i,n) for (int i=0;i ostream& operator<<(ostream& os, const pair& p) { return os< istream& operator>>(istream& is, pair& p) { return is>>p.xx>>p.yy; } vector &split(const std::string &s, char delim, vector &e) { stringstream ss(s); string item; while(getline(ss, item, delim)) e.push_back(item); return e; } ll Pow(ll a ,ll b ,ll Mo){ ll ans = 1; for (; b; b >>= 1, a = a * a % Mo) if (b&1) ans = ans * a % Mo; return ans; } ll nCr(ll n,ll r) { static ll MAXF = 1e6; static std::vector fact(MAXF,1); for (int i = 1; i < MAXF; ++i) fact[i]=(fact[i-1]*i)%MOD; MAXF=0; return (fact[n]*Pow((fact[r]*fact[n-r])%MOD,MOD-2,MOD))%MOD; } vector Zfunc(string &s) { int n=s.length(); vector z(n,0); for(int i=1,l=0,r=0;i>k; ll b=k*(k+1)/2; ll a=k*(k-1)/2; ll s = solve(b)-solve(a); s = 2*s-k; cout<