//generated by GPT-5.4?, modified by hamamu
namespace MatSpace{
using ll=long long;

template<class T> struct PlusTimesOps{
    static T zero(){ return T(0); }
    static T one() { return T(1); }
    static T add(const T &a,const T &b){ return a+b; }
    static T mul(const T &a,const T &b){ return a*b; }
};

template<class T,class Ops=PlusTimesOps<T>> struct mat_{
    using value_type=T;
    using row_type=std::vector<T>;
    using storage_type=std::vector<row_type>;

    storage_type a;

    mat_(){}
    mat_(initializer_list<initializer_list<T>> init): a(init.begin(),init.end()){
        assert(all_of(a.begin(),a.end(),[&](const auto &row){ return (ll)row.size()==w(); }));
    }
    mat_(ll h,ll w,T x=Ops::zero()): a(h,row_type(w,x)){}
    mat_(ll n): mat_(n,n,Ops::zero()){}
    mat_(ll n,const string &tag): mat_(n,n,Ops::zero()){
        if (tag=="E") *this=identity(n);
    }
    mat_(const std::vector<T> &v,bool istranspose=false){
        if (istranspose){
            a.assign(1,row_type((ll)v.size(),Ops::zero()));
            for (ll j=0; j<w(); ++j) a[0][j]=v[j];
        }
        else{
            a.assign((ll)v.size(),row_type(1,Ops::zero()));
            for (ll i=0; i<h(); ++i) a[i][0]=v[i];
        }
    }

    static mat_ identity(ll n){
        mat_ ret(n,n,Ops::zero());
        for (ll i=0; i<n; ++i) ret[i][i]=Ops::one();
        return ret;
    }

    ll h() const { return (ll)a.size(); }
    ll w() const { return h()==0 ? 0 : (ll)a[0].size(); }
    bool empty() const { return a.empty(); }

    row_type &operator[](ll i){ return a[i]; }
    const row_type &operator[](ll i) const { return a[i]; }
    auto begin(){ return a.begin(); }
    auto end(){ return a.end(); }
    auto begin() const { return a.begin(); }
    auto end() const { return a.end(); }

    bool operator==(const mat_ &b) const { return a==b.a; }

    mat_ &operator+=(const mat_ &b){
        assert(h()==b.h() && w()==b.w());
        for (ll i=0; i<h(); ++i) for (ll j=0; j<w(); ++j)
            a[i][j]=Ops::add(a[i][j],b[i][j]);
        return *this;
    }
    mat_ operator+(const mat_ &b) const { return mat_(*this)+=b; }
    mat_ &operator-=(const mat_ &b){
      assert(h()==b.h() && w()==b.w());
      for (ll i=0; i<h(); ++i) for (ll j=0; j<w(); ++j)
        a[i][j]-=b[i][j];
      return *this;
    }
    mat_ operator-(const mat_ &b) const { return mat_(*this)-=b; }
    mat_ operator-() const { return (*this)*(-1); }
    mat_ &operator*=(const T &x){
      for (ll i=0; i<h(); ++i) for (ll j=0; j<w(); ++j) a[i][j]*=x;
      return *this;
    }
    mat_ operator*(const T &x) const { return mat_(*this)*=x; }
    friend mat_ operator*(const T &x,const mat_ &m){ return m*x; }
    mat_ &operator*=(const mat_ &b){ return *this=*this*b; }
    mat_ operator*(const mat_ &b) const {
        assert(w()==b.h());
        mat_ ret(h(),b.w(),Ops::zero());
        for (ll i=0; i<h(); ++i) for (ll k=0; k<w(); ++k) for (ll j=0; j<b.w(); ++j){
            ret[i][j]=Ops::add(ret[i][j],Ops::mul(a[i][k],b[k][j]));
        }
        return ret;
    }
    std::vector<T> operator*(const std::vector<T> &v) const {
        assert(w()==(ll)v.size());
        std::vector<T> ret(h(),Ops::zero());
        for (ll i=0; i<h(); ++i) for (ll j=0; j<w(); ++j){
            ret[i]=Ops::add(ret[i],Ops::mul(a[i][j],v[j]));
        }
        return ret;
    }
    mat_ pow(ll n) const {
        assert(h()==w());
        mat_ ret=identity(h()),base(*this);
        for (; n>0; n>>=1,base*=base) if (n&1) ret*=base;
        return ret;
    }
    mat_ t() const {
        mat_ ret(w(),h(),Ops::zero());
        for (ll i=0; i<h(); ++i) for (ll j=0; j<w(); ++j) ret[j][i]=a[i][j];
        return ret;
    }
};
}//namespace MatSpace
using MatSpace::mat_;
using mat = mat_<mll>;
/*
mat m={{2,3,4},{1,0,5}};
mat m(2);        //2x2正方行列、all0
mat m(2,"E");    //2x2単位行列
mat m(h,w);      //h*w行列、all0
mat m(h,w,x);    //h*w行列、allx
mat m(v);        //vectorを縦(n×1)のmat型に変換
mat m(v,true);   //vectorを横(1×n)のmat型に変換
A+B A*B A+=B A*=B      //Opsのadd,mulでの行列演算
vmll u=A*v             //Opsのmulでの行列とベクトルの積
A-B A-=B -A            //Opsを無視して加減算
A*k A*=k               //Opsを無視して各要素をk倍
mat mm=m.pow(k);    //m^k
mat mm=m.t();       //転置

- ---- min-plus半環 (最短路計算など)
struct MinPlusOpsLL{
  static ll zero(){ return INF; }
  static ll one() { return 0; }
  static ll add(ll a,ll b){ return min(a,b); }
  static ll mul(ll a,ll b){
    if(a>=INF || b>=INF) return INF;
    return min(INF,a+b);
  }
};
using minmat = mat_<ll,MinPlusOpsLL>;
その他半環はメモ参照
*/