//#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll=long long; using intpair=pair; using intpv=vector; using llpair=pair; using llpv=vector; using intvec=vector; using llvec=vector; using intq=queue; using llq=queue; using intmat=vector; using llmat=vector; using pairmat=vector; #define matrix(T) vector> #define PI 3.141592653589793 #define INTINF 1<<30 #define LLINF 1LL<<60 #define MPRIME 1000000007 #define pqueue priority_queue #define pushb push_back #define all(name) name.begin(),name.end() #define rall(name) name.rbegin(),name.rend() #define ABS(x) ( (x)>0 ? (x) : -(x) ) #define gsort(vbeg,vend) sort(vbeg,vend,greater<>()) #define init(v) for(auto &a: v) cin>>a template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } ll GCD(ll a, ll b) { //最大公約数 if(a==0||b==0) return 0; if(a0) { if(ex&1) result=result*a%p; ex>>=1; a=a*a%p; } return result; } ll Fact(ll x, ll p) { //階乗 ll f=1; for(ll i=2; i<=x; i++) { f*=i; f%=p; } return f; } ll nPr(ll n, ll r) { if(n n) { return 0; } if (r > n / 2) { r = n - r; } if (n == 0) { return 0; } if (r == 0) { return 1; } if (r == 1) { return n; } double result = 1; for (double i = 1; i <= r; i++) { result *= (n - i + 1) / i; } return (ll)result; } llvec fact,inv,factinv; void prenCrP(ll n, ll p) { fact.resize(n+1); inv.resize(n+1); factinv.resize(n+1); fact[0]=fact[1]=inv[1]=factinv[0]=factinv[1]=1LL; for(ll i=2LL; i<=n; i++) { fact[i]=fact[i-1]*i%p; inv[i]=p-inv[p%i]*(p/i)%p; factinv[i]=factinv[i-1]*inv[i]%p; } } ll nCrP(ll n, ll r, ll p) { // mod pにおけるnCr if (r > n) return 0; return fact[n]*factinv[r]%p*factinv[n-r]%p; } llvec fact2,inv2,factinv2; void prenCrP2(ll n, ll r, ll p) { // nがバカでかいときに使う, 計算量はr依存 fact2.resize(r+1); inv2.resize(r+1); factinv2.resize(r+1); fact2[0]=n%p, fact2[1]=n%p*(n-1)%p; inv2[1]=factinv2[0]=factinv2[1]=1LL; for(ll i=2LL; i<=r; i++) { fact2[i]=fact2[i-1]*(n-i)%p; inv2[i]=p-inv2[p%i]*(p/i)%p; factinv2[i]=factinv2[i-1]*inv2[i]%p; } } ll nCrP2(ll r, ll p) { return fact2[r-1]*factinv2[r]%p; } ll LowerBinarySearch(llvec array, ll key, ll max, ll min) { //にぶたんlower if(max>min) { return -1LL; } else { ll mid = max + (min-max)/2; if(array[mid]>key) { return LowerBinarySearch(array,key,max,mid-1); } if(array[mid]min) { return -1LL; } else { ll mid = max + (min-max)/2; if(array[mid]key) { return GreaterBinarySearch(array,key,mid+1,min); } else { return mid; } } } int DigitNum(ll n) { //桁数 int digit=0; ll wari=1LL; while(n/wari) { digit++; wari*=10; } return digit; } bool IsPrime(ll num) { //素数判定 if (num < 2) return false; else if (num == 2) return true; else if (num % 2 == 0) return false; // 偶数はあらかじめ除く double sqrtNum = sqrt(num); for (ll i = 3; i <= sqrtNum; i += 2) { if (num % i == 0) { // 素数ではない return false; } } // 素数である return true; } vector Divisor(ll x) { // 約数列挙 vector result; ll i=1LL; for( ; i*i PrimeFact(ll x) { // 素因数分解 {素因数,指数} vector result; ll ex=0LL; if(x%2==0) { while(x%2==0) { x/=2; ex++; } result.push_back({2,ex}); } for(ll i=3LL; i*i<=x; i+=2) { if(x%i) continue; ex=0LL; while(x%i==0) { x/=i; ex++; } result.push_back({i,ex}); } if(x!=1) result.push_back({x,1}); return result; } bool Palind(string s) { //回文判定 return s == string(s.rbegin(), s.rend()); } struct Union_Find{ vector parent; vector num; Union_Find(int N) : parent(N),num(N,1) { for(int i=0; i>D1>>D2; if(D1==D2 || D1*2==D2) cout<<4<