#include using namespace std; const int MAX = 510000; const int MOD = 1000000007; const double PI = 3.14159265358979323846264338327950288; long long fac[MAX], finv[MAX], inv[MAX]; #define _GLIBCXX_DEBUG #define int long long #define _yes {cout<<"yes"<=0; i--) #define rrep1(i,n) for(int i=n; i>=1; i--) #define mrep(itr,m) for(auto itr=m.begin();itr!=m.end();itr++) #define ALL(obj) (obj).begin(), (obj).end() #define rALL(obj) (obj).rbegin(), (obj).rend() #define fore(x,a) for(auto &x:a) #define forin(a) for(auto &x:a){cin>>x;} #define forvin(a) for(auto &x:a){for(auto &g:x){cin>>g;}} #define inin(n) int n;cin>>n; #define stin(s) string s;cin>>s; #define chin(c) char c;cin>>c; #define dbin(d) double d;cin>>d; using ll = long long; using vb = vector; using vc = vector; using vd = vector; using vi = vector; using vs = vector; using si = set; using ss=set; using sd = set; using qi = queue; using dqi = deque; using dqc = deque; using vvc = vector; using vvd = vector; using vvi = vector; using vvs = vector; using vvvi = vector>>; using pii = pair; using psi = pair; using pis = pair; using pic = pair; using pdd = pair; using pds = pair; using psd = pair; using pss = pair; using vpii = vector; using vpic = vector; using vpsi = vector; using vpis = vector; using vpdd = vector; using vpss = vector; using vpds = vector; using vpsd = vector; using spii=set; using tiii = tuple; using tsii = tuple; using tiis = tuple; using vtiii = vector; using mii = map; using mci = map; using msi = map; using Graph=vvi; template bool chmax(T &m, const T q) {if (m < q) {m = q; return true;} else return false; } template bool chmin(T &m, const T q) {if (m > q) {m = q; return true;} else return false; } int FACT(ll n){if(n==0){return 1;}else{ll base=1;for(ll i=1;i<=n;i++){base*=i;}return base;}}//n! int FACTmod(ll n, int mod){if(n==0){return 1;}else{ll base=1;for(ll i=1;i<=n;i++){base=base*i%mod;}return base;}}//n!%mod vi DIVISOR(int n){ vi v; for (int i=1;i*i<=n;i++){ if(n%i==0) {v.push_back(i); if(i*i!=n)v.push_back(n/i);} } sort(ALL(v)); return v;} // 整数nの約数の昇順配列を出力 int DIVISORK(int n){ int ans=0; for (int i=1;i*i<=n;i++){ if(n%i==0) {ans++; if(i*i!=n)ans++;} } return ans; }// 整数nの約数の個数を出力 bool IS_PRIME(long long N) { if (N == 1) return false; for (long long i = 2; i * i <= N; ++i) { if (N % i == 0) return false; } return true; } //素数判定 void NCRinit(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2; i0){if(n&1)ret*=x;x*=x;n>>=1;}return ret;}//x^n long long POWmod(int x,int n, int mod) {long long ret=1;while(n>0) {if(n&1)ret=ret*x%mod;x=x*x%mod;n>>=1;}return ret;}//x^n%mod ll GCD(ll x, ll y) {while(y>0){ll r=x%y;x=y;y=r;}return x;}//gcd ll LCM(ll x, ll y){return (x/GCD(x,y))*y;}//lcm int mNCR(int n,int r){ if(nn-r;i--){ ans=ans*i/x; x++; } return ans; } }//n.r小さいときのnCr 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; } res.push_back({a, ex}); } if (N != 1) res.push_back({N, 1}); return res; } //素因数分解 int MINVEC(vi v){ int min=2147483647; int ans=0; int n=v.size(); rep(i,n){ if(v[i]<=min){min=v[i];ans=i;} } return ans; } //viの最小項の番号を返す;//最大番号優先 int MAXVEC(vi v){ int max=-2147483648; int ans=0; int n=v.size(); rep(i,n){ if(v[i]>=max){max=v[i];ans=i;} } return ans; } //viの最大項の番号を返す;//最大番号優先 // aよりもbが大きいならばaをbで更新する // (更新されたならばtrueを返す) template bool chmax(T&a,const T&b){if(abool chmin(T&a,const T& b){if(a>b){a=b;return true;}return false;} int MASSVEC(vi v, int x, int y){ int ans=0; for(int i=x;i<=y;i++){ ans+=v[i]; } return ans; } //ベクトルのx番目からy番目までの総和 bool secondsort(pair a, pair b) { if(a.second != b.second){ return a.second < b.second; }else{ return a.first < b.first; } } //ABCDEFGHIJKLMNOPQRSTUVWXYZ //abcdefghijklmnopqrstuvwxyz void solve(){ int a,b; cin>>a>>b; cout<