#include #include using namespace std; using namespace atcoder; using ll=long long; using LL=__int128; using mint=modint998244353; using pll=pair; using tu=tuple; using vl=vector; using vb=vector; using vvb=vector; using vvl=vector; using vs=vector; using vld=vector; using vc=vector; using vmi=vector; using Graph=vector>>; using graph=vector>; template using rpq=priority_queue,greater>; // 小さい順priority_queue using inverse_priority_queue=rpq; const ll Inf=2147483647LL, Inf9=1000000000LL, inf=9223372036854775807LL, inf18=1000000000000000000LL, mod=998244353LL; #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--) #define rep1(i,n) for(ll i=1;i<=(ll)(n);i++) #define rep3(i,s,t) for(ll i=(ll)(s);i<(ll)(t);i++) #define pb push_back #define p(s) cout<<(s)<<'\n' #define p2(s,t) cout<<(s)<<" "<<(t)<<'\n' #define p3(s,t,u) cout<<(s)<<" "<<(t)<<" "<<(u)<<'\n' #define p4(s,t,u,v) cout<<(s)<<" "<<(t)<<" "<<(u)<<" "<<(v)<<'\n' #define pe(s) cout<<(s)<<' ' #define pval(s) cout<<(s).val()<<'\n' #define Sort(A) sort(all(A)) #define RSort(A) sort(rall(A)) #define p_yes() p("Yes") #define p_no() p("No") template inline ll sz(const T& x){return (ll)x.size();} // サイズ取得 ostream& operator<<(ostream& os,const mint& x){return os<>(istream& is,mint& x){ll v; is>>v; x=mint(v); return is;} // mint入力 template inline bool chmin(T& a,const T& b){if(a>b){a=b; return true;} return false;} // 最小値更新 template inline bool chmax(T& a,const T& b){if(a ll LB(const vector& v,const U& a){return lower_bound(all(v),a)-v.begin();} // lower_boundのindex template ll UB(const vector& v,const U& a){return upper_bound(all(v),a)-v.begin();} // upper_boundのindex template T vec_min(const vector& v){assert(!v.empty()); return *min_element(all(v));} // vectorの最小値 template T vec_max(const vector& v){assert(!v.empty()); return *max_element(all(v));} // vectorの最大値 template T vec_sum(const vector& v){T res=T(0); for(const auto& x:v) res+=x; return res;} // vectorの総和 template vector cin_vl(ll n){vector ret(n); rep(i,n) cin>>ret[i]; return ret;} // vector入力、型省略時ll template vector> cin_vvl(ll h,ll w){vector> ret(h,vector(w)); rep(i,h) rep(j,w) cin>>ret[i][j]; return ret;} // h*w入力、型省略時ll template pair,vector> cin_xy(ll n){vector x(n),y(n); rep(i,n) cin>>x[i]>>y[i]; return {x,y};} // x,y入力、型省略時ll template tuple,vector,vector> cin_xyz(ll n){vector x(n),y(n),z(n); rep(i,n) cin>>x[i]>>y[i]>>z[i]; return {x,y,z};} // x,y,z入力、型省略時ll template vector> Cin_vl(ll n,ll k){vector> ret(k,vector(n)); rep(i,n) rep(j,k) cin>>ret[j][i]; return ret;} // n行k列入力を列ごと保持、型省略時ll template vector> cin_pairs(ll n){vector> ret(n); rep(i,n) cin>>ret[i].first>>ret[i].second; return ret;} // pair列入力、型省略時ll template vector> cin_tuples(ll n){vector> ret(n); rep(i,n){T a,b,c; cin>>a>>b>>c; ret[i]={a,b,c};} return ret;} // 3要素tuple列入力、型省略時ll template void cout_vl(const vector& a,char sep=' ',char end='\n'){rep(i,sz(a)){if(i) cout< void Cout_vl(const vector& a,const vector& b){rep(i,sz(a)) cout< void cout_vvl(const vector>& a){for(const auto& e:a) cout_vl(e);} // 2次元vector出力 ll ceil_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return (a+b-1)/b; return -((-a)/b);} // 切り上げ除算 ll floor_div(ll a,ll b){assert(b!=0); if(b<0) a=-a,b=-b; if(a>=0) return a/b; return -((-a+b-1)/b);} // 切り下げ除算 ll isqrt(ll n){ll x=sqrtl(n); while((LL)(x+1)*(x+1)<=n) x++; while((LL)x*x>n) x--; return x;} // floor(sqrt(n)) template vector sort_unique_vec(vector v){sort(all(v)); v.erase(unique(all(v)),v.end()); return v;} // sortして重複削除した新vector template vector compress(const vector& v){auto xs=sort_unique_vec(v); vector ret; for(auto& x:v) ret.pb(LB(xs,x)); return ret;} // 座標圧縮後のindex列 template vector prefix_sum(const vector& v){vector s(sz(v)+1,0); rep(i,sz(v)) s[i+1]=s[i]+v[i]; return s;} // 1次元累積和 template T range_sum(const vector& s,ll l,ll r){return s[r]-s[l];} // 累積和から[l,r)の和 template vector> run_length(const vector& v){vector> ret; for(auto& x:v){if(ret.empty()||ret.back().first!=x) ret.pb({x,1}); else ret.back().second++;} return ret;} // ランレングス圧縮 vector> run_length(const string& s){vector> ret; for(char c:s){if(ret.empty()||ret.back().first!=c) ret.pb({c,1}); else ret.back().second++;} return ret;} // 文字列ランレングス圧縮 template ll argmin(const vector& v){assert(!v.empty()); return min_element(all(v))-v.begin();} // 最小値のindex template ll argmax(const vector& v){assert(!v.empty()); return max_element(all(v))-v.begin();} // 最大値のindex template bool in_vec(const vector& v,const T& x){return binary_search(all(v),x);} // sort済vectorに存在するか ll gcd(ll a,ll b){if(b==0) return abs(a); return gcd(b,a%b);} // 最大公約数 ll lcm(ll a,ll b){return a/gcd(a,b)*b;} // 最小公倍数 ll Exp(ll x,ll y){ll cnt=-1; while(x>0) x/=y,cnt++; return cnt;} // y進桁数-1 ll powmod(ll x,ll k,ll m){if(k==0) return 1%m; ll r=powmod(x,k/2,m); r=(LL)r*r%m; if(k&1) r=(LL)r*x%m; return r;} // mod累乗 template T square(T x){return x*x;} // 二乗 template void Uni_erase(vector& v){sort(all(v)); v.erase(unique(all(v)),v.end());} // sortして重複削除 inline bool OutIn(ll x,ll y,ll h,ll w){return 0<=x&&x dist(l,r-1); return dist(rng);} // [l,r)乱数 void YesNo(bool x){x?p_yes():p_no();} // Yes/No出力 vl vl_n(ll n){vl ret(n); rep(i,n) ret[i]=i; return ret;} // 0..n-1のvector生成 vl dx={0,1,0,-1}, dy={1,0,-1,0}; vl dx8={1,1,0,-1,-1,-1,0,1}, dy8={0,1,1,1,0,-1,-1,-1}; // 8近傍 vector fac,finv; void factorial(ll N=1000000LL){ll M=N+100; fac.assign(M+1,1); finv.assign(M+1,1); rep1(i,M) fac[i]=fac[i-1]*i; finv[M]=fac[M].inv(); for(ll i=M;i>=1;i--) finv[i-1]=finv[i]*i;} // N+100まで階乗・逆階乗前計算 void ensure_factorial(ll N){if((ll)fac.size()>N) return; factorial(N);} // 階乗表の不足分確保 mint nCr(ll N,ll r){if(N<0||r<0||N> n; if(n % 3 == 0){ vvl ans(3,vl(3,n/3)); cout_vvl(ans); } else{ vvl ans(3,vl(3,(n/3))); n %= 6; if(n <= 2){ rep(i,3) ans[i][0]++; } if(n == 2) rep(i,3) ans[i][1]++; if(n >= 4){ rep3(i,0,n-3)rep(j,3) ans[i][j]++; } cout_vvl(ans); } }