//generated by GPT-5.4?, modified by hamamu
namespace ArrayMatSpace{
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,ll N,class Ops=PlusTimesOps<T>> struct arraymat_{
    using value_type=T;
    using row_type=std::array<T,N>;
    using storage_type=std::array<row_type,N>;

    storage_type a;

    arraymat_(){
        for (ll i=0; i<N; ++i) a[i].fill(Ops::zero());
    }
    arraymat_(initializer_list<initializer_list<T>> init): arraymat_(){
        ll i=0;
        for (auto &&row: init){
            assert(i<N);
            ll j=0;
            for (auto &&x: row){
                assert(j<N);
                a[i][j]=x;
                ++j;
            }
            ++i;
        }
    }
    explicit arraymat_(const string &tag): arraymat_(){
        if (tag=="E") *this=identity();
    }

    static constexpr ll h(){ return N; }
    static constexpr ll w(){ return N; }
    static arraymat_ identity(){
        arraymat_ ret;
        for (ll i=0; i<N; ++i) ret[i][i]=Ops::one();
        return ret;
    }

    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 arraymat_ &b) const { return a==b.a; }

    arraymat_ &operator+=(const arraymat_ &b){
        for (ll i=0; i<N; ++i) for (ll j=0; j<N; ++j){
            a[i][j]=Ops::add(a[i][j],b[i][j]);
        }
        return *this;
    }
    arraymat_ operator+(const arraymat_ &b) const { return arraymat_(*this)+=b; }
    arraymat_ &operator-=(const arraymat_ &b){
      for (ll i=0; i<N; ++i) for (ll j=0; j<N; ++j){
        a[i][j]-=b[i][j];
      }
      return *this;
    }
    arraymat_ operator-(const arraymat_ &b) const { return arraymat_(*this)-=b; }
    arraymat_ operator-() const { return (*this)*(-1); }
    arraymat_ &operator*=(const T &x){
      for (ll i=0; i<N; ++i) for (ll j=0; j<N; ++j) a[i][j]*=x;
      return *this;
    }
    arraymat_ operator*(const T &x) const { return arraymat_(*this)*=x; }
    friend arraymat_ operator*(const T &x,const arraymat_ &m){ return m*x; }
    arraymat_ &operator*=(const arraymat_ &b){ return *this=*this*b; }
    arraymat_ operator*(const arraymat_ &b) const {
        arraymat_ ret;
        for (ll i=0; i<N; ++i) for (ll k=0; k<N; ++k) for (ll j=0; j<N; ++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((ll)v.size()==N);
        std::vector<T> ret(N,Ops::zero());
        for (ll i=0; i<N; ++i) for (ll j=0; j<N; ++j){
            ret[i]=Ops::add(ret[i],Ops::mul(a[i][j],v[j]));
        }
        return ret;
    }
    arraymat_ pow(ll n) const {
        arraymat_ ret=identity(),base(*this);
        for (; n>0; n>>=1,base*=base) if (n&1) ret*=base;
        return ret;
    }
    arraymat_ t() const {
        arraymat_ ret;
        for (ll i=0; i<N; ++i) for (ll j=0; j<N; ++j) ret[j][i]=a[i][j];
        return ret;
    }
};
}//namespace ArrayMatSpace
using ArrayMatSpace::arraymat_;
using mat2 = arraymat_<mll,2>;
using mat3 = arraymat_<mll,3>;
/*
array版行列クラス  サイズ固定、正方行列のみ対応

mat2 m={{2,3},{1,0}};
mat2 m;           //2x2,all0
mat3 m;           //3x3,all0
mat2 m("E");      //単位行列
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倍
mat2 mm=m.pow(k); //m^k
mat2 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 minmat2 = arraymat_<ll,2,MinPlusOpsLL>;
その他半環はメモ参照
*/