#include//入出力 #include//アルゴリズム #include//配列 #include//文字列 #include//関数型変数 #include//セット #include//ハッシュセット #include//木構造マップ #include//ハッシュマップ #include//キュー、優先度付きキュー #include//スタックとキュー #include//出力形式調整 #include//pairの複数型 #include//数学。ルートとか #include//大文字小文字のチェックなど #include//ファイル入出力 #include//乱数 using namespace std; #define rep(i,n) for (long long i=0;i #define vvl vector> #define vdbg(a) rep(ii,a.size()){cout<(sqrt(n)); return sqrtN * sqrtN == n; } //整数同士の累乗の計算をする。 ll power(ll A, ll B) { ll result = 1; for (ll i=0;i makePrime(ll n){ vector factors; while (n % 2 == 0) { factors.push_back(2); n /= 2; } for (ll i=3; i*i<=n;i+=2) { while (n%i == 0) { factors.push_back(i); n /= i; } } if (n > 2) { factors.push_back(n); } return factors; } // nのk乗をmodで割った余りを計算 ll power_mod(ll n, ll k) { long long result = 1; while (k > 0){ if ((k&1) ==1)result=(result*n)%mod; n=n*n%mod; k >>= 1; } return result; } //場合の数 nCr を求める ll ncr(ll n,ll r) { if(n 0) { ll remainder = num % to_base; result.push_back(remainder < 10 ? remainder + '0' : remainder - 10 + 'A'); num /= to_base; } // 結果を逆順にして返す reverse(result.begin(), result.end()); return result.empty() ? "0" : result; } //底がaの対数xを計算。ただし小数点は繰り上げ。 ll logax(ll a, ll x){ ll result = 0; ll power = 1; while (power < x){ power *= a; result++; } return result; } //第一引数を第二引数で割った余りを計算、割る数はint範囲 ll bigmd(const string &num, int md) { ll ans = 0; ll SIZ = 9; //9桁のチャンク ll base = 1000000000;//SIZ個の0 rep(i,(num.size()-1)/SIZ+1){ ll chunk = 0; ll l = i*SIZ; ll r = min((ll)num.size(),l+SIZ); if(r!=num.size()){ ans = (ans*base+stoll(num.substr(l,r-l)))%md; }else{ rep(i,r-l)ans*=10; ans=(ans+stoll(num.substr(l,r-l)))%md; } } return ans; } //受け取った2次元文字の外側に、文字pをコーティングする。 vector pad(vector &s,char p){ ll h=s.size(); ll w=s[0].size(); vector res(h+2,string(w+2,p)); rep(i,h)rep(j,w)res[i+1][j+1]=s[i][j]; return res; } //ax+by=cの整数解を得る ただし、cはgcd(a,b)の倍数でない場合、0,0になる pair ex_euclid(ll a,ll b,ll c){ if(a<0||b<0||c<0){ pairans=ex_euclid(abs(a),abs(b),abs(c)); if(a<0)ans.first*=-1; if(b<0)ans.second*=-1; if(c<0)ans.first*=-1,ans.second*=-1; return ans; } if(c!=1){ ll d=gcd(a,b); if(c%d!=0)return make_pair(0,0); pairans = ex_euclid(a/d,b/d,1); ans.first*=c/d; ans.second*=c/d; return ans; } if(aans=ex_euclid(b,a,c); swap(ans.first,ans.second); return ans; } if(a==1&&b==0)return make_pair(1,0); else if(b==0) return make_pair(0,0); ll x,y; tie(x,y)=ex_euclid(b,a%b,c); pair ans=make_pair(y,x-(a/b)*y); return ans; } // Union-Find struct UnionFind { vector par, siz; UnionFind(int n) : par(n, -1) , siz(n, 1) { } // 根を求める int root(int x) { if (par[x] == -1) return x; else return par[x] = root(par[x]); } // x と y が同じグループに属するかどうか (根が一致するかどうか) bool issame(int x, int y) { return root(x) == root(y); } // x を含むグループと y を含むグループとを併合する bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; return true; } // x を含むグループのサイズ int size(int x) { return siz[root(x)]; } }; //重み付きUF struct PotentialUnionFind { ll n; vl par, siz, pot; PotentialUnionFind(ll N) : par(N,-1) , siz(N,1) , pot(N,0){n=N;} // 根を求める ll root(ll x) { if (par[x] == -1) return x; ll tmp = root(par[x]); pot[x] += pot[par[x]]; par[x] = tmp; return par[x]; } // x と y が同じグループに属するかどうか (根が一致するかどうか) bool issame(ll x, ll y) { return root(x) == root(y); } //x よりいくつ大きい所に y があるか。根が一致しない場合は"0" ll potential(ll x,ll y){ if(root(x) != root(y)) return 0; else return pot[y]-pot[x]; } //x より w だけ大きい状態として y を併合。 bool unite(ll x, ll y, ll w) { ll rx = root(x),ry = root(y); if (rx == ry) return false; w += pot[x]-pot[y]; if (siz[rx] < siz[ry]) swap(rx, ry),w*=-1; par[ry] = rx; siz[rx] += siz[ry]; siz[ry] = 0; pot[ry] = w; return true; } // x を含むグループのサイズ ll size(ll x) { return siz[root(x)]; } //小さい順にUnionFindグラフを調整、O(n log n) void regulation(){ vvl r(n); rep(i,n)r[root(i)].push_back(i); rep(i,n){ if(r[i].size()==0)continue; ll mn = i; rep(j,r[i].size())if(pot[mn]>pot[r[i][j]])mn=r[i][j]; siz[mn]=siz[i]; siz[i]=0; ll tmp = pot[mn]; rep(j,r[i].size()){ pot[r[i][j]]-=tmp; par[r[i][j]] = mn; } par[mn]=-1; } } void debug(){ rep(i,n)cout< struct SegTree{ ll size; ll tall; vector data; function p; //セグ木に乗せる値の初期値をa配列にし、putの関数をセグ木に乗せる、dをデフォルト値に。 SegTree(vector a,function put,T d) : data(power(2,logax(2,a.size())+1)) { size = data.size()/2; tall=logax(2,size)+1; p=put; ll tmp=size; data = vector(size*2,d); while(tmp!=0){ if(tmp==size)rep(i,a.size())data[tmp+i]=a[i]; else rep(i,tmp) data[tmp+i]=p(data[2*(tmp+i)],data[2*(tmp+i)+1]); tmp/=2; } } //更新、t番目の値をxにする。 void update(ll t,T x){ t+=size; while(t!=0){ if(t>=size)data[t]=x; else data[t]=p(data[2*t],data[2*t+1]); t/=2; } } //取得、l~r区間内の評価値を取得する。 T get(ll l,ll r){ //lとrが範囲外なら範囲内に正す l=max(0LL,l); r=min(r,size-1); r++; T ans=data[0]; ll pos=l+size; ll wid=1; //出来る限り上に上げきる。 while(l+(wid*2)<=r){ while(l%(wid*2)==0&&l+(wid*2)<=r)pos/=2,wid*=2; ans=p(ans,data[pos]); pos++; l+=wid; } //上げ終わったので今度は下げる while(l!=r){ while(l+wid>r)pos*=2,wid/=2; ans=p(ans,data[pos]); pos++; l+=wid; } return ans; } //セグ木デバッグ用、丸ごと出力 void print(){ rep(i,size)cout<>n>>k; vector a(n); rep(i,n)cin>>a[i]; rep(i,n){ rep(j,k){ rep(g,n){ rep(h,k)cout<