#line 2 "lib/template.hpp" #pragma GCC optimize("O3") using namespace std; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using uint=unsigned; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; using i128=__int128; templateusing vc=vector; templateusing vvc=vc>; templateusing vvvc=vvc>; #define vec(d,T,n,...) vec_##d(T,n,__VA_ARGS__) #define vec_1(T,n,a) vector n(a) #define vec_2(T,n,a,b) vector> n(a,vector(b)) #define vec_3(T,n,a,b,c) vector>> n(a,vector>(b,vector(c))) #define vec_4(T,n,a,b,c,d) vector>>> n(a,vector>>(b,vector>(c,vector(d)))) #define vec_5(T,n,a,b,c,d,e) vector>>>> n(a,vector>>>(b,vector>>(c,vector>(d,vector(e))))) #define vec_6(T,n,a,b,c,d,e,f) vector>>>>> n(a,vector>>>>(b,vector>>>(c,vector>>(d,vector>(e,vector(f)))))) #define vec_7(T,n,a,b,c,d,e,f,g) vector>>>>>> n(a,vector>>>>>(b,vector>>>>(c,vector>>>(d,vector>>(e,vector>(f,vector(g))))))) templateusing smpq=priority_queue,greater>; templateusing bipq=priority_queue; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define mp make_pair #define pb push_back #define fi first #define se second #define is insert #define bg begin() #define ed end() void scan(int&a) { cin >> a; } void scan(ll&a) { cin >> a; } void scan(string&a) { cin >> a; } void scan(char&a) { cin >> a; } void scan(uint&a) { cin >> a; } void scan(ull&a) { cin >> a; } void scan(bool&a) { cin >> a; } void scan(ld&a){ cin>> a;} template void scan(vector&a) { for(auto&x:a) scan(x); } void read() {} template void read(Head&head, Tail&... tail) { scan(head); read(tail...); } #define INT(...) int __VA_ARGS__; read(__VA_ARGS__); #define LL(...) ll __VA_ARGS__; read(__VA_ARGS__); #define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__); #define STR(...) string __VA_ARGS__; read(__VA_ARGS__); #define CHR(...) char __VA_ARGS__; read(__VA_ARGS__); #define DBL(...) double __VA_ARGS__; read(__VA_ARGS__); #define LD(...) ld __VA_ARGS__; read(__VA_ARGS__); #define VC(type, name, ...) vector name(__VA_ARGS__); read(name); #define VVC(type, name, size, ...) vector> name(size, vector(__VA_ARGS__)); read(name); templatevoid print(T a) { cout << a; } template void print(vectora) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout< void PRT(T a) { print(a); cout < void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; } template bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template bool chmax(T &x, F y){ if(x T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } template T ceil(T x, T y) { return floor(x + y - 1, y); } template T bmod(T x, T y) { return x - y * floor(x, y); } template pair divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } void YesNo(bool b){ cout<<(b?"Yes":"No")< T isqrt(T x){ T F=sqrtl(x); while((F+1)*(F+1)<=x)F++; while(F*F>x)F--; return F; } template int popcount(T n){ return __builtin_popcountll(n); } template L sum(vc&a){ return accumulate(all(a),L(0)); } template vcsubset(T S){ vcans; for(T x=S;x>0;x=(x-1)&S)ans.pb(x); ans.pb(0); return ans; } template T max(vc&a){ return *max_element(all(a)); } template T min(vc&a){ return *min_element(all(a)); } vvcreadgraph(int n,int m,int off = -1){ vvc g(n); rep(i, m){ int u,v; cin>>u>>v; u+=off,v+=off; g[u].push_back(v); g[v].push_back(u); } return g; } vvc readtree(int n,int off=-1){ return readgraph(n,n-1,off); } template vc presum(vc &a){ vc ret(a.size()+1); rep(i,a.size())ret[i+1]=ret[i]+a[i]; return ret; } template vc &operator+=(vc &a,F b){ for (auto&v:a)v += b; return a; } template vc &operator-=(vc&a,F b){ for (auto&v:a)v-=b; return a; } template vc &operator*=(vc&a,F b){ for (auto&v:a)v*=b; return a; } template constexpr T POW(T a,T b){ T res=1; while(b){ if(b&1)res*=a; a*=a; b/=2; } return res; } constexpr ll ten(ll a){ return POW(10,a); } template struct Compress{ vcv; bool worked; Compress(){worked=0;} Compress(int n){v.reserve(n);worked=0;} void push(T x){ v.push_back(x); } void work(){ if(worked)return; worked=1; sort(all(v)); v.erase(unique(all(v)),v.end()); } int find(T x){ work(); auto itr=lower_bound(all(v),x); if((*itr)==x)return itr-v.begin(); return -1; } int find_next(T x){ work(); return lower_bound(all(v),x)-v.begin(); } int find_prev(T x){ work(); return lower_bound(all(v),x)-v.begin()-1; } }; int tbit(int32_t x){return x==0?-1:31-__builtin_clz((uint32_t)x);} int lbit(int32_t x){return x==0?-1:__builtin_ctz((uint32_t)x);} int tbit(uint32_t x){return x==0?-1:31-__builtin_clz(x);} int lbit(uint32_t x){return x==0?-1:__builtin_ctz(x);} int tbit(int64_t x){return x==0?-1:63-__builtin_clzll((uint64_t)x);} int lbit(int64_t x){return x==0?-1:__builtin_ctzll((uint64_t)x);} int tbit(uint64_t x){return x==0?-1:63-__builtin_clzll(x);} int lbit(uint64_t x){return x==0?-1:__builtin_ctzll(x);} int tbit(int32_t x,int p){return p<0?-1:tbit((int32_t)(x&(p>=31?~0u:(1u<<(p+1))-1)));} int lbit(int32_t x,int p){return p>31?-1:lbit((int32_t)(x&(~0u<=31?~0u:(1u<<(p+1))-1)));} int lbit(uint32_t x,int p){return p>31?-1:lbit((uint32_t)(x&(~0u<=63?~0ULL:(1ULL<<(p+1))-1)));} int lbit(int64_t x,int p){return p>63?-1:lbit((int64_t)(x&(~0ULL<=63?~0ULL:(1ULL<<(p+1))-1)));} int lbit(uint64_t x,int p){return p>63?-1:lbit((uint64_t)(x&(~0ULL<>(std::istream& is, __int128& x) { std::streambuf* sb = is.rdbuf(); int c = sb->sgetc(); while (c <= ' ') c = sb->snextc(); bool neg = false; if (c == '-') { neg = true; c = sb->snextc(); } unsigned __int128 v = 0; while ((unsigned)(c - '0') < 10) { v = v * 10 + (c - '0'); c = sb->snextc(); } x = neg ? -(__int128)v : (__int128)v; return is; } std::ostream& operator<<(std::ostream& os, __int128 x) { std::streambuf* sb = os.rdbuf(); if (x == 0) { sb->sputc('0'); return os; } char buf[40]; int pos = 39; bool neg = x < 0; unsigned __int128 v = neg ? -(unsigned __int128)x : (unsigned __int128)x; while (v) { buf[--pos] = char('0' + (v % 10)); v /= 10; } if (neg) buf[--pos] = '-'; sb->sputn(buf + pos, 39 - pos); return os; } #ifdef LOCAL template std::ostream& operator<<(std::ostream& os, const std::pair& p); template std::ostream& operator<<(std::ostream& os, const std::vector& v); template std::ostream& operator<<(std::ostream& os, const std::deque& dq); template std::ostream& operator<<(std::ostream& os, const std::list& lst); template std::ostream& operator<<(std::ostream& os, const std::set& s); template std::ostream& operator<<(std::ostream& os, const std::unordered_set& s); template std::ostream& operator<<(std::ostream& os, const std::map& m); template std::ostream& operator<<(std::ostream& os, const std::unordered_map& m); template std::ostream& operator<<(std::ostream& os, std::stack st); template std::ostream& operator<<(std::ostream& os, std::queue q); template std::ostream& operator<<(std::ostream& os, const std::array& a); template std::ostream& operator<<(std::ostream& os, std::priority_queue pq); #define dbg(...) debug_func(0, #__VA_ARGS__, __VA_ARGS__) template void debug_func(int i, T name) { cout << endl; } template void debug_func(int i, const T1 &name, const T2 &a, const T3 &...b) { for ( ; name[i] != ',' && name[i] != '\0'; i++ ) cout << name[i]; cout << ":" << a << " "; debug_func(i + 1, name, b...); } // pair template std::ostream& operator<<(std::ostream& os, const std::pair& p) { return os << "(" << p.first << ", " << p.second << ")"; } // vector template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for (size_t i = 0; i < v.size(); ++i) { if (i > 0) os << ", "; os << v[i]; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, const std::deque& dq) { os << "["; for (size_t i = 0; i < dq.size(); ++i) { if (i > 0) os << ", "; os << dq[i]; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, const std::list& lst) { os << "["; bool first = true; for (const auto& x : lst) { if (!first) os << ", "; os << x; first = false; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, const std::set& s) { os << "{"; bool first = true; for (const auto& x : s) { if (!first) os << ", "; os << x; first = false; } os << "}"; return os; } template std::ostream& operator<<(std::ostream& os, const std::unordered_set& s) { os << "{"; bool first = true; for (const auto& x : s) { if (!first) os << ", "; os << x; first = false; } os << "}"; return os; } template std::ostream& operator<<(std::ostream& os, const std::map& m) { os << "{"; bool first = true; for (const auto& kv : m) { if (!first) os << ", "; os << kv; first = false; } os << "}"; return os; } template std::ostream& operator<<(std::ostream& os, const std::unordered_map& m) { os << "{"; bool first = true; for (const auto& kv : m) { if (!first) os << ", "; os << kv; first = false; } os << "}"; return os; } template std::ostream& operator<<(std::ostream& os, std::stack st) { os << "["; bool first = true; while (!st.empty()) { if (!first) os << ", "; os << st.top(); st.pop(); first = false; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, std::queue q) { os << "["; bool first = true; while (!q.empty()) { if (!first) os << ", "; os << q.front(); q.pop(); first = false; } os << "]"; return os; } template std::ostream& operator<<(std::ostream& os, std::priority_queue pq) { os << "["; while (!pq.empty()) { os << pq.top() << (pq.size() > 1 ? ", " : ""); pq.pop(); } return os << "]"; } template std::ostream& operator<<(std::ostream& os, const std::array& a) { os << "["; for (std::size_t i = 0; i < N; ++i) { if (i > 0) os << ", "; os << a[i]; } os << "]"; return os; } #else #define dbg(...) 1111 #endif #line 3 "lib/graph/base.hpp" struct Unweighted{ Unweighted()=default; Unweighted(int){} operator int()const{return 1;} }; template struct edge{ int from,to,id; [[no_unique_address]] T cost; #ifdef LOCAL friend ostream&operator<<(ostream&os,const edge&e){ return os<<"{from:"< struct static_graph{ constexpr static bool directed(){return is_directed;} using edge=edge; private: int n,m,added=0; mutable bool csr_built=false,inv_built=false; vc_all_edges; mutable vccsr_start; mutable vccsr_edge; mutable vcinv_start; mutable vcinv_edge; public: static_graph(int n):n(n),m(-1),csr_start(n+1){} static_graph(int n,int m):n(n),m(m),csr_start(n+1){_all_edges.reserve(m);} void add_edge(int a,int b,T cost=1,int id=-1){ assert(0<=a&&anow=csr_start; for(auto&e:_all_edges){ csr_edge[now[e.from]++]=e; if constexpr(!is_directed)csr_edge[now[e.to]++]={e.to,e.from,e.id,e.cost}; } } void build_inv()const{ if(inv_built)return; inv_built=true; inv_start.assign(n+1,0); for(auto&e:_all_edges){ inv_start[e.to+1]++; if constexpr(!is_directed)inv_start[e.from+1]++; } rep(i,n)inv_start[i+1]+=inv_start[i]; inv_edge.resize(inv_start[n]); vcnow=inv_start; for(auto&e:_all_edges){ inv_edge[now[e.to]++]={e.to,e.from,e.id,e.cost}; if constexpr(!is_directed)inv_edge[now[e.from]++]=e; } } const vc&all_edges()const{return _all_edges;} int edge_size()const{return (int)_all_edges.size();} edge get_edge(int id)const{ assert(0<=id&&id struct span{ E*l; E* r; E*begin()const{return l;} E*end()const{return r;} int size()const{return r-l;} E&operator[](int i){return l[i];} const E&operator[](int i)const{return l[i];} }; auto operator[](int u){ assert(0<=u&&u{csr_edge.data()+csr_start[u],csr_edge.data()+csr_start[u+1]}; } auto operator[](int u)const{ assert(0<=u&&u{csr_edge.data()+csr_start[u],csr_edge.data()+csr_start[u+1]}; } auto inv(int u){ assert(0<=u&&u{inv_edge.data()+inv_start[u],inv_edge.data()+inv_start[u+1]}; } auto inv(int u)const{ assert(0<=u&&u{inv_edge.data()+inv_start[u],inv_edge.data()+inv_start[u+1]}; } int size()const{return n;} templatevvcadj()const{ vvcres(n,vc(n)); for(auto&e:all_edges()){ res[e.from][e.to]=e.cost; if(directed()==false)res[e.to][e.from]=e.cost; } return res; } void clear(){ added=0; csr_built=false; inv_built=false; _all_edges.clear();_all_edges.shrink_to_fit(); csr_start.assign(n+1,0);csr_start.shrink_to_fit(); csr_edge.clear();csr_edge.shrink_to_fit(); inv_start.clear();inv_start.shrink_to_fit(); inv_edge.clear();inv_edge.shrink_to_fit(); } template void sort(int i,F f){ assert(0<=i&&i void sort_inv(int i,F f){ assert(0<=i&&i static_graphextract(F f)const{ static_graphres(n); for(auto&e:_all_edges)if(f(e))res.add_edge(e.from,e.to,e.cost,e.id); return res; } template static_graph<1,T>reorder(F f)const{ static_graph<1,T>res(n); for(auto&e:_all_edges){ if(f(e))res.add_edge(e.from,e.to,e.cost,e.id); else res.add_edge(e.to,e.from,e.cost,e.id); } return res; } }; #line 3 "a.cpp" void solve(){ INT(n); if(n==2){ cout<<"1 2 1\n"; rep(t,2)cout<<"1 1\n"; return; } static_graph<0,int>g(n); rep(i,n-1){ g.add_edge(i,i+1,2*i+1); } g.add_edge(1,2,2),g.add_edge(1,2,4); REP(i,3,n){ g.add_edge(0,i,2*i); } g.build(); PRT(g.edge_size()); vc>edges(g.edge_size()); rep(i,n)for(auto&e:g[i]){ edges[e.id]=e; } for(auto&x:edges){ cout<es; if(i==0){es.pb(Find(0,1,1));} else if(i==1)es.pb(Find(1,2,4)); else{ for(int j=i;j>2;j--){ es.pb(Find(j,j-1,(j-1)*2+1)); } es.pb(Find(2,1,3)); es.pb(Find(1,0,1)); es.pb(Find(0,i+1,2*(i+1))); } REP(j,i+1,n){ cout<sync_with_stdio(0); cout<> t; while(t--)solve(); }