#include namespace clibrary{ using namespace std; namespace macro{ using ll=long long; using ld=long double; #define rep(i,n) for(ll i=0;i=0;i--) #define bit(i,n) for(ll i=0;i<(1<> #define Weightgraph vector> #define st(a) sort(a.begin(),a.end()) #define rst(a) sort(a.rbegin(),a.rend()) #define mp(a,b) make_pair(a,b) #define pb(a) push_back(a) #define fi first #define se second using vl =vector; using vi =vector; using vs =vector; using vpl =vector>; using P=pair; const ll mod = 1000000007; const ll mod1=998244353; const ll inf=1e9; const ll linf=1e18; string yn(bool a){ if(a)return "Yes"; return "No"; } string Yn(bool a){ if(a)return "YES"; return "NO"; } template bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; } template bool chmax(T &a, const T& b) { if (a < b) { a = b; return true; } return false; } class mint { ll x; public: mint(ll x=0) : x((x%mod+mod)%mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint& a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const { mint res(*this); return res+=a; } mint operator-(const mint& a) const { mint res(*this); return res-=a; } mint operator*(const mint& a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2); } mint& operator/=(const mint& a) { return (*this) *= a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } }; class UnionFind { public: vector par; // 各元の親を表す配列 vector siz; // 素集合のサイズを表す配列(1 で初期化) UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) { for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } void init(ll sz_) { par.resize(sz_); siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身 } ll root(ll x) { // 根の検索 while (par[x] != x) { x = par[x] = par[par[x]]; // x の親の親を x の親とする } return x; } bool unite(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; // merge technique(データ構造をマージするテク.小を大にくっつける) if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } bool same(ll x, ll y) { // 連結判定 return root(x) == root(y); } ll size(ll x) { // 素集合のサイズ return siz[root(x)]; } }; struct Edge { ll to; // 辺の行き先 ll weight; // 辺の重み Edge(ll t, ll w) : to(t), weight(w) { } }; //バイナリーインデックスツリー template class BIT{ public: int N; vector data; BIT(T _N):N(_N){ data.assign(N+1, 0); }; // a is 1-indexed void add1(int a, T w){ for(int x = a; x <= N; x += x & -x)data[x] += w; } // 1-indexed sum of prefix [0, a] T sum1(int a){ T res = 0; for(int x = a; x > 0; x -= x & -x)res += data[x]; return res; } // 1-indexed sum of range [l, r] T sum1(int l, int r){return sum1(r) - sum1(l-1);} // 0-indexed add void add(int a, T w){add1(a + 1, w);} // 0-indexed sum T sum(int a){return sum1(a + 1);} // 0-indexed sum of range T sum(int l, int r){return sum(r) - sum(l-1);} // show the value void debug(){print(data);} }; //区間加算BIT template struct BIT2 { int n; // 要素数 vector bit[2]; // データの格納先 BIT2(int n_) { init(n_); } void init(int n_) { n = n_ + 1; for (int p = 0; p < 2; p++) bit[p].assign(n, 0); } void add_sub(int p, int i, T x) { for (int idx = i; idx < n; idx += (idx & -idx)) { bit[p][idx] += x; } } void add(int l, int r, T x) { // [l,r) に加算 add_sub(0, l, -x * (l - 1)); add_sub(0, r, x * (r - 1)); add_sub(1, l, x); add_sub(1, r, -x); } T sum_sub(int p, int i) { T s(0); for (int idx = i; idx > 0; idx -= (idx & -idx)) { s += bit[p][idx]; } return s; } T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; } }; struct Edge3 { ll cost, from, to; Edge3() {} Edge3(ll c, ll f, ll t) : from(c), to(f), cost(t) {} friend bool operator < (const Edge3& lhs, const Edge3& rhs) { return lhs.cost < rhs.cost; }; friend bool operator > (const Edge3& lhs, const Edge3& rhs) { return rhs < lhs; }; friend bool operator <= (const Edge3& lhs, const Edge3& rhs) { return !(lhs > rhs); }; friend bool operator >= (const Edge3& lhs, const Edge3& rhs) { return !(lhs < rhs); }; }; struct kruskal{ struct UnionFind uf; uint64_t weight; // 最小全域木の辺の重みの和 kruskal(ll V, vector &edges) : uf(V), weight(0) { sort(edges.begin(), edges.end()); for (auto e : edges) { if (uf.same(e.from, e.to)) continue; uf.unite(e.from, e.to); weight += e.cost; } } }; } using namespace macro; //約数列挙 vector enum_divisors(ll N) { vector res; for (ll i = 1; i * i <= N; ++i) { if(N % i == 0) { res.push_back(i); if (N/i != i) res.push_back(N/i); } } sort(res.begin(), res.end()); return res; } //素数チェック bool prime(ll a){ if(a<=1)return false; for(int i=2;i*i<=a;i++){ if(a%i==0)return false; } return true; } //最小公倍数 ll lcm(ll a,ll b){ ll d = gcd(a,b); return a/d*b; } //aのn乗(繰り返し二乗法) template T rui(T a, T n){ T x = 1; while(n > 0){//全てのbitが捨てられるまで。 if(n&1){//1番右のbitが1のとき。 x = x*a; } a = a*a; n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。 } return x; } //xのn乗(mod) long long mpow(long long x, long long n,ll m) { ll ret=1; while (n > 0) { if (n & 1) ret =ret*x % m; // n の最下位bitが 1 ならば x^(2^i) をかける x = x * x % m; n >>= 1; // n を1bit 左にずらす } return ret; } //nCr vector> comblist(int n, int r) { vector> v(n + 1,vector(n + 1, 0)); for (int i = 0; i < v.size(); i++) { v[i][0] = 1; v[i][i] = 1; } for (int j = 1; j < v.size(); j++) { for (int k = 1; k < j; k++) { v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]); } } return v; } //nCr (mod) ll mcomb(ll n,ll x,ll mod){ ll res; ll a=1; for(ll i=0;i1)ret -=ret/n; return ret; } //拡張ユークリッド互助法 ll extGCD(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll d = extGCD(b, a%b, y, x); // 再帰的に解く y -= a / b * x; return d; } //逆元 ll modinv(ll a, ll m) { ll x, y; extGCD(a, m, x, y); return (x % m + m) % m; } //ビット本数 ll bcount(ll bits){ bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555); bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333); bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f); bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff); return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff); } //素因数分解 vector > prime_factorize(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } //ワーシャルフロイド法(iからjに行くまでの最小コスト計算,nは要素数,dはコスト表) void warshall_floyd(int n,vector> &d){ for (int k = 0; k < n; k++){ // 経由する頂点 for (int i = 0; i < n; i++) { // 始点 for (int j = 0; j < n; j++) { // 終点 d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } } //エラトステネスのふるい(n以下の素数列挙) vector eratosthenes( const ll N ){ vector is_prime( N + 1 ); for( ll i = 0; i <= N; i++ ) { is_prime[ i ] = true; } vector P; for( ll i = 2; i <= N; i++ ) { if( is_prime[ i ] ) { for( ll j = 2 * i; j <= N; j += i ) { is_prime[ j ] = false; } P.emplace_back( i ); } } return P; } //エラトステネスのふるい(素数チェック) vector eratosthenescheck( const ll N ){ vector is_prime( N + 1 ); for( ll i = 0; i <= N; i++ ) { is_prime[ i ] = true; } for( ll i = 2; i <= N; i++ ) { if( is_prime[ i ] ) { for( ll j = 2 * i; j <= N; j += i ) { is_prime[ j ] = false; } } } return is_prime; } //ダイクストラ vector dijkstra(ll s,ll n,vector> g){ priority_queue, greater

> q; vector dist(n,linf); q.push(make_pair(0, s)); dist[s] = 0; while (!q.empty()) { ll pos = q.top().second; ll cost=q.top().first; q.pop(); if(cost>dist[pos])continue; for (ll i = 0; i < g[pos].size(); i++) { ll to = g[pos][i].to, cost = g[pos][i].weight; if (dist[to] > dist[pos] + cost) { dist[to] = dist[pos] + cost; q.push(make_pair(dist[to], to)); } } } return dist; } //区間素数(l=b-a+1) ll sieve(ll a,ll b){ ll x=sqrt(b); ll l=b-a+1; vector pri(x,true); vector ans(l,true); for(ll i=2;i*i> a >> b >> c>>d>>e; ll time=0; ll ta=a,tb=c; ll sum=0; bool fa=true,fb=true; vector shuki(1100000,0); while(time