#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #include using namespace std; typedef long long ll; typedef long double ld; typedef pair PP; typedef tuple TTT; const ll mod=1e9+7,INF=mod*mod*3; //M_PI 998244353 #define rep(i,N) for(ll i=0; i<(N); i++) #define rep1(i,N) for(ll i=1; i<(N); i++) #define f first #define s second #define pb push_back #define mp make_pair #define all(x) x.begin(),x.end() #define si(x) x.size() #define debug(x,y) cout< inline bool chmax(T &a,const T &b){ if(a inline bool chmin(T &a,const T &b){ if(b void Fill(A (&array)[N], const T &val){ fill( (T*)array, (T*)(array+N), val ); } // a + b がオーバーフローするならtrueを返す template bool overflow_if_add(T a, T b) { return (std::numeric_limits::max() - a) < b; } // a * b がオーバーフローするならtrueを返す template bool overflow_if_mul(T a, T b) { return (std::numeric_limits::max() / a) < b; } ll mod_inverse(ll a) { ll ret=1L; ll m=1e9+5L; while(m){ if(m%2){ ret=(ret*a)%mod; } m=m/2; a=(a*a)%mod; } return ret; } const ll sze=2000005; ll fc[sze],fv[sze]; ll cb(ll n,ll r){ ll ret=0; ret=fc[n]*fv[n-r]%mod*fv[r]%mod; return ret; } ll pw(ll x,ll y){ ll ret=1; for(ll i=0; i='0'&&c<='9'){ return c-'0'; } return 0; } ll gcd(ll a,ll b){ if(a>a>>b>>c; if(a==b&&b==c){ cout<>t;rep(_,t) slv(); }