#include #include using namespace std; using namespace atcoder; #define rep(i,t,n) for(long long i=t;i A(N,i) #define vd(A,N,i) vector A(N,i) #define vc(A,N,i) vector A(N,i) #define vs(A,N,i) vector A(N,i) #define vb(A,N,i) vector A(N,i) #define vp(A,N,i) vector A(N,{i,i}) #define vvi(A,N,M,i) vector> A(N,vector(M,i)) #define vvp(A,N,M,i) vector> A(N,vector(M,{i,i})) #define vvd(A,N,M,i) vector> A(N,vector(M,i)) #define vvc(A,N,M,i) vector> A(N,vector(M,i)) #define vvb(A,N,M,i) vector> A(N,vector(M,i)) #define vvs(A,N,M,i) vector> A(N,vector(M,i)) #define vvvi(A,N,M,L,i) vector>> A(N,vector>(M,vector(L,i))) #define vvvs(A,N,M,L,i) vector>> A(N,vector>(M,vector(L,i))) #define vvvvi(A,N,M,L,O,i) vector>>> A(N,vector>>(M,vector>(L,vector(O,i)))) #define ll long long #define INF ((1LL<<62)-(1LL<<31)) #define ALL(a) (a).begin(),(a).end() using VVi=vector>; using Pair=pair; using graphi=vector>; using graphp=vector>; struct Plane{ ll x; ll y; }; struct Path{ ll cost; ll to; }; template void CIN(vector &A){ rep(i,0,(ll)A.size()){ cin>>A[i]; } return; } struct ThreePlane{ ll x,y,z; ThreePlane(ll X=0,ll Y=0,ll Z=0):x(X),y(Y),z(Z){} bool operator<(const ThreePlane& other) const { return x(const ThreePlane& other) const { return x>other.x; } bool operator>=(const ThreePlane& other) const { return x>=other.x; } }; struct FourPlane{ ll dist; ll x; ll y; ll stat; }; struct Fraction{ ll p,q,r; Fraction(ll P = 0, ll Q = 1,ll R = 1): p(P), q(Q),r(R){} bool operator<(const Fraction &other)const{ if(p*other.q != other.p*q){ return p*other.q < other.p*q; }else{ return r>other.r; } } }; ll GCD(ll a,ll b){ if(b==0)return a; return GCD(b,a%b); } pair extGCD(long long a, long long b) {// ax+by=1 solver if (b == 0) return make_pair(1, 0); long long x,y; tie(y,x)=extGCD(b,a%b); y-=a/b*x; return make_pair(x,y); } ll SQRT(ll a){ ll low,high,mid; low=0; high=1LL<<31; while(high-low!=1){ mid=(low+high)/2; if(mid*mid<=a){ low=mid; }else{ high=mid; } } return low; } string strmin(string x,string y){ ll minlength=min((int)x.size(),(int)y.size()); rep(i,0,minlength){ if(x[i]>y[i])return y; if(x[i](int)y.size())return y; return x; } ll LCS(string x,string y){ ll xsize=(ll)x.size(); ll ysize=(ll)y.size(); vvi(dp,xsize+1,ysize+1,0); rep(i,1,xsize+1){ rep(j,1,ysize+1){ if(x[i-1]==y[j-1])dp[i][j]=max(max(dp[i-1][j-1]+1,dp[i][j-1]),dp[i-1][j]); else dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } } return dp[xsize][ysize]; } ll Factorial(ll n,ll mod){ ll a=1; if(n>=mod)return 0; rep(i,1,n+1){ a*=i; a%=mod; } return a; } ll Combination(ll n,ll k,ll mod){ if(n> RLE(string x,char s=' ',long long a=0,vector> res={}){ for(auto i:x){ if(s==i){ a++; }else{ if(s!=' ')res.push_back({s,a}); s=i,a=1; } } res.push_back({s,a}); return res; } vector> RLEll(vector x,ll s=-INF,long long a=0,vector> res={}){ for(auto i:x){ if(s==i){ a++; }else{ if(s!=-INF)res.push_back({s,a}); s=i,a=1; } } res.push_back({s,a}); return res; } vector cu1d(vector A){ ll cu1=A.size(); vector res(cu1+1,0); rep(i,0,cu1)res[i+1]=A[i]; rep(i,1,cu1+1)res[i]+=res[i-1]; return res; } vector> cu2d(vector> A){ ll cu1=A.size(),cu2=A[0].size(); vector> res(cu1+1,vector(cu2+1,0)); rep(i,0,cu1)rep(j,0,cu2)res[i+1][j+1]=A[i][j]; rep(i,1,cu1+1)rep(j,0,cu2+1)res[i][j]+=res[i-1][j]; rep(j,0,cu1+1)rep(i,1,cu2+1)res[j][i]+=res[j][i-1]; return res; } ll LIS(vector A){ ll a=(ll)A.size(); vector result(a,INF); ll answer=0; rep(i,0,a){ ll ok=-1; ll ng=a; while(ng-ok!=1){ ll mid=(ok+ng)/2; if(A[i]<=result[mid])ng=mid; else ok=mid; } result[ok+1]=A[i]; answer=max(answer,ok+2); } return answer; } vector zaatu(vector A){ vector B=A; Sort(B); B.erase(unique(ALL(B)),end(B)); vector res; transform(ALL(A),back_inserter(res),[&](const ll &x){ return lower_bound(ALL(B),x)-begin(B); }); return res; } vector trim(vector A){ bool frag=0; char s='#'; ll h=(ll)A.size(); ll w=(ll)A[0].size(); ll a=-1,b=h,c=-1,d=w; for(ll i=0;i=0;i--){ for(ll j=0;j=0;i--){ for(ll j=0;j B(b-a-1,""); for(ll i=a+1;i> Warshall(vector> A){ ll a=A.size(); rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]); return A; } ll bit_ceil(ll n) { ll x = 1; while (x < (ll)(n)) x *= 2; return x; } int countr_zero(ll n){ ll res=0; while(n%2==0){ res++; n>>=1; } return res; } vector make_grid(ll H,ll W,char filler='#'){ vector res(H+2); string st=""; rep(i,0,W+2)st+=filler; res[0]=res[H+1]=st; string st2; rep(i,1,H+1){ cin>>st2; res[i]=filler+st2+filler; } return res; } struct binC{ long long mod; vectorfact; vectorinv; vectorfact_inv; binC(long long mod):mod(mod){ fact.resize(5050505); inv.resize(5050505); fact_inv.resize(5050505); fact[0]=fact[1]=1; fact_inv[0]=fact_inv[1]=1; inv[1]=1; rep(i,2,5050505){ fact[i]=fact[i-1]*i%mod; inv[i]=mod-inv[mod%i]*(mod/i)%mod; fact_inv[i]=fact_inv[i-1]*inv[i]%mod; } } ll C(ll n,ll k){ if(k<0||n data; ll size; static const ll mod=385870579LL; static const ll base=258324359LL; ll base_inv=inv_mod(base,mod); static ll ie(){return 0LL;} static ll operat(ll a,ll b){return (a+b)%mod;} segtreeseg; vectorofset; vectorpower; void init(){ ofset[0]=1LL; rep(idx,1,size){ ofset[idx]=ofset[idx-1]*base_inv; ofset[idx]=ofset[idx]%mod; } power[0]=1LL; rep(idx,1,size){ power[idx]=power[idx-1]*base; power[idx]=power[idx]%mod; } } rolling_hash(ll n) : data(n), size(n), seg(n), ofset(n), power(n) { init(); rep(idx,0,size){ data[idx]=0; } } rolling_hash(const string& str) : data(str.size()), size(str.size()), seg(str.size()), ofset(str.size()), power(str.size()) { init(); rep(idx,0,size){ data[idx]=str[idx]; seg.set(idx,str[idx]*power[idx]%mod); } } rolling_hash(const vector& vec) : data(vec), size(vec.size()), seg(vec), ofset(vec.size()), power(vec.size()) { init(); rep(idx,0,size){ data[idx]=vec[idx]; seg.set(idx,vec[idx]*power[idx]%mod); } } void set(ll i,ll a){ data[i]=a; seg.set(i,a*power[i]%mod); } ll get(ll idx){ return data[idx]; } ll value(ll l,ll r){ return seg.prod(l,r)*ofset[l]%mod; } }; ll inversion(vectorA){ ll res=0; ll siz=0; rep(i,0,(ll)A.size())siz=max(siz,A[i]); fenwick_treeFT(siz); rep(i,0,A.size()){ res+=FT.sum(A[i],siz); FT.add(A[i],1); } return res; } vectorargsort(vector&A){ vectorB((ll)A.size()); rep(i,0,(ll)A.size())B[i]={A[i],i}; stable_sort(B.begin(),B.end()); vectorres((ll)A.size()); rep(i,0,(ll)A.size())res[i]=B[i].second; return res; } //Warshall rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]); long long a,b,c,d,e,f,g,h,ans=0; string w,x="",y="",z=""; char s,t,u; bool frag=false,frag1=false,frag2=false; vector X={1,0,-1,0},Y={0,1,0,-1}; int main(){ cin>>a>>b; cin>>d>>e; cin>>f>>g; d--,e--,f--,g--; ll p=abs(d-f)+abs(e-g); vvi(A,a,a,0); rep(i,0,a){ rep(j,0,a){ if((i+j)%2==(d+e)%2){ A[i][j]=0; }else{ A[i][j]=1; } } } h=0; ll q=b-p; if(q>p||b