#include using namespace std; #if __has_include() #include using namespace atcoder; #endif using LL = long long; using VI = vector; using VL = vector; using VS = vector; using VC = vector; using VB = vector; using VVI = vector>; using VVL = vector>; using VVS = vector>; using VVC = vector>; using VVB = vector>; using SI = set; using PII = pair; const LL LINF = 1e18; const int IINF = 1e9; #define YES cout << "Yes" << endl #define NO cout << "No" << endl #define out(a) cout << a << endl #define rep(i, a, b) for (int i = a; i < (int)(b); i++) #define rrep(i, a, b) for (int i = a; i >= (int)(b); i--) #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() const double PI = acos(-1); const VI DX = {-1, 0, 1, 0}; const VI DY = {0, 1, 0, -1}; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } 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 (int i = 3; i <= sqrtNum; i += 2) if (num % i == 0) return false; return true;} LL fact(LL n) { LL res = 1; while (n > 1) res *= n--; return res; } //factorial map decomp(LL N){map res; LL num=N; for(LL i=2;i*i<=num;i++){while(N%i==0) N/=i,res[i]++; if(N==1) break;} if(N!=1) res[N]++; return res;} bool isNumber(string s){for(auto c : s){if (isdigit(c))continue;else return false;}return true;} //if string is number then true, otherwise false LL n_ary_str(string s, int n){LL ans = 0; for(char x:s){ans *= n; ans += x - '0';} return ans;} LL n_ary_VI(VI arr, int n){LL ans = 0;rep(i, 0, arr.size()){ans *= n;ans += arr[i];} return ans;} int GCD(int a, int b){if(b==0){return a;}else{return GCD(b,a%b);}} int LCM(int a, int b){return(a/GCD(a,b))*b;} VI split_digit(int a){VI res;string s=to_string(a);for(auto c:s){res.push_back(c-'0');}return res;} LL power(int a,int b){LL res=1;rep(i,0,b){res*=a;}return res;} int ctoi(char c){return c-'0';} VS VStrans(VS a){int h = a.size(); int w = a[0].size(); VS b(w, string(h, '?')); rep(i, 0, h){ rep(j, 0, w){b[j][i] = a[i][j];}} return b;} VVI VVItrans(VVI a){VVI b(a.size(), VI(a[0].size())); rep(i, 0, a.size()){rep(j, 0, a[i].size()){b[j][i] = a[i][j];}} return b;} VVC VVCtrans(VVC a){VVC b(a.size(), VC(a[0].size())); rep(i, 0, a.size()){rep(j, 0, a[i].size()) b[j][i] = a[i][j];} return b;} int VVImin(VVI a){int res = IINF;rep(i,0,a.size()){res=min(res,*min_element(all(a[i])));}return res;} int VVImax(VVI a){int res = 0;rep(i,0,a.size()){res=max(res,*max_element(all(a[i])));}return res;} VL get_divisors(LL n){vectorret;for(LL i=1;i*i<=n;i++){if(n%i==0){ret.push_back(i);if(i*i!=n)ret.push_back(n/i);}}sort(ret.begin(),ret.end());return ret;} bool Sfind(string s,string tgt){if(s.find(tgt)!=string::npos)return true;else return false;} bool VIfind(VI a,int tgt){if(count(all(a),tgt))return true;else return false;} bool VVIfind(VVI a,int tgt){for(auto A:a){if(VIfind(A,tgt))return true;}return false;} bool VCfind(VC a,char tgt){if(count(all(a),tgt))return true;else return false;} bool VVCfind(VVC a,char tgt){for(auto A:a){if(VCfind(A,tgt))return true;}return false;} bool VSfind(VS a,string tgt){if(count(all(a),tgt))return true;else return false;} bool VVSfind(VVS a,string tgt){for(auto A:a){if(VSfind(A,tgt))return true;}return false;} bool VBfind(VB a,bool tgt){if(count(all(a),tgt))return true;else return false;} bool VVBfind(VVB a,bool tgt){for(auto A:a){if(VBfind(A,tgt))return true;}return false;} void VScout(VS a){rep(i,0,a.size()){cout<