1. #include <bits/stdc++.h>
2. using namespace std;
3.  
4. using ll=long long;
5. //#define int ll
6.  
7. #define rng(i,a,b) for(int i=int(a);i<int(b);i++)
8. #define rep(i,b) rng(i,0,b)
9. #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
10. #define per(i,b) gnr(i,0,b)
11. #define pb push_back
12. #define eb emplace_back
13. #define a first
14. #define b second
15. #define bg begin()
16. #define ed end()
17. #define all(x) x.bg,x.ed
18. #define si(x) int(x.size())
19. #ifdef LOCAL
20. #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
21. #else
22. #define dmp(x) void(0)
23. #endif
24.  
25. template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
26. template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
27.  
28. template<class t> using vc=vector<t>;
29. template<class t> using vvc=vc<vc<t>>;
30.  
31. using pi=pair<int,int>;
32. using vi=vc<int>;
33.  
34. template<class t,class u>
35. ostream& operator<<(ostream& os,const pair<t,u>& p){
36.         return os<<"{"<<p.a<<","<<p.b<<"}";
37. }
38.  
39. template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
40.         os<<"{";
41.         for(auto e:v)os<<e<<",";
42.         return os<<"}";
43. }
44.  
45. #define mp make_pair
46. #define mt make_tuple
47. #define one(x) memset(x,-1,sizeof(x))
48. #define zero(x) memset(x,0,sizeof(x))
49. #ifdef LOCAL
50. void dmpr(ostream&os){os<<endl;}
51. template<class T,class... Args>
52. void dmpr(ostream&os,const T&t,const Args&... args){
53.         os<<t<<" ";
54.         dmpr(os,args...);
55. }
56. #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
57. #else
58. #define dmp2(...) void(0)
59. #endif
60.  
61. using uint=unsigned;
62. using ull=unsigned long long;
63.  
64. template<class t,size_t n>
65. ostream& operator<<(ostream&os,const array<t,n>&a){
66.         return os<<vc<t>(all(a));
67. }
68.  
69. template<int i,class T>
70. void print_tuple(ostream&,const T&){
71. }
72.  
73. template<int i,class T,class H,class ...Args>
74. void print_tuple(ostream&os,const T&t){
75.         if(i)os<<",";
76.         os<<get<i>(t);
77.         print_tuple<i+1,T,Args...>(os,t);
78. }
79.  
80. template<class ...Args>
81. ostream& operator<<(ostream&os,const tuple<Args...>&t){
82.         os<<"{";
83.         print_tuple<0,tuple<Args...>,Args...>(os,t);
84.         return os<<"}";
85. }
86.  
87. template<class t>
88. void print(t x,int suc=1){
89.         cout<<x;
90.         if(suc==1)
91.                 cout<<"\n";
92.         if(suc==2)
93.                 cout<<" ";
94. }
95.  
96. ll read(){
97.         ll i;
98.         cin>>i;
99.         return i;
100. }
101.  
102. vi readvi(int n,int off=0){
103.         vi v(n);
104.         rep(i,n)v[i]=read()+off;
105.         return v;
106. }
107.  
108. pi readpi(int off=0){
109.         int a,b;cin>>a>>b;
110.         return pi(a+off,b+off);
111. }
112.  
113. template<class t,class u>
114. void print(const pair<t,u>&p,int suc=1){
115.         print(p.a,2);
116.         print(p.b,suc);
117. }
118.  
119. template<class T>
120. void print(const vector<T>&v,int suc=1){
121.         rep(i,v.size())
122.                 print(v[i],i==int(v.size())-1?suc:2);
123. }
124.  
125. string readString(){
126.         string s;
127.         cin>>s;
128.         return s;
129. }
130.  
131. template<class T>
132. T sq(const T& t){
133.         return t*t;
134. }
135.  
136. //#define CAPITAL
137. void yes(bool ex=true){
138.         #ifdef CAPITAL
139.         cout<<"YES"<<"\n";
140.         #else
141.         cout<<"Yes"<<"\n";
142.         #endif
143.         if(ex)exit(0);
144.         #ifdef LOCAL
145.         cout.flush();
146.         #endif
147. }
148. void no(bool ex=true){
149.         #ifdef CAPITAL
150.         cout<<"NO"<<"\n";
151.         #else
152.         cout<<"No"<<"\n";
153.         #endif
154.         if(ex)exit(0);
155.         #ifdef LOCAL
156.         cout.flush();
157.         #endif
158. }
159. void possible(bool ex=true){
160.         #ifdef CAPITAL
161.         cout<<"POSSIBLE"<<"\n";
162.         #else
163.         cout<<"Possible"<<"\n";
164.         #endif
165.         if(ex)exit(0);
166.         #ifdef LOCAL
167.         cout.flush();
168.         #endif
169. }
170. void impossible(bool ex=true){
171.         #ifdef CAPITAL
172.         cout<<"IMPOSSIBLE"<<"\n";
173.         #else
174.         cout<<"Impossible"<<"\n";
175.         #endif
176.         if(ex)exit(0);
177.         #ifdef LOCAL
178.         cout.flush();
179.         #endif
180. }
181.  
182. constexpr ll ten(int n){
183.         return n==0?1:ten(n-1)*10;
184. }
185.  
186. const ll infLL=LLONG_MAX/3;
187.  
188. #ifdef int
189. const int inf=infLL;
190. #else
191. const int inf=INT_MAX/2-100;
192. #endif
193.  
194. int topbit(signed t){
195.         return t==0?-1:31-__builtin_clz(t);
196. }
197. int topbit(ll t){
198.         return t==0?-1:63-__builtin_clzll(t);
199. }
200. int botbit(signed a){
201.         return a==0?32:__builtin_ctz(a);
202. }
203. int botbit(ll a){
204.         return a==0?64:__builtin_ctzll(a);
205. }
206. int popcount(signed t){
207.         return __builtin_popcount(t);
208. }
209. int popcount(ll t){
210.         return __builtin_popcountll(t);
211. }
212. bool ispow2(int i){
213.         return i&&(i&-i)==i;
214. }
215. ll mask(int i){
216.         return (ll(1)<<i)-1;
217. }
218.  
219. bool inc(int a,int b,int c){
220.         return a<=b&&b<=c;
221. }
222.  
223. template<class t> void mkuni(vc<t>&v){
224.         sort(all(v));
225.         v.erase(unique(all(v)),v.ed);
226. }
227.  
228. ll rand_int(ll l, ll r) { //[l, r]
229.         #ifdef LOCAL
230.         static mt19937_64 gen;
231.         #else
232.         static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
233.         #endif
234.         return uniform_int_distribution<ll>(l, r)(gen);
235. }
236.  
237. template<class t>
238. void myshuffle(vc<t>&a){
239.         rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
240. }
241.  
242. template<class t>
243. int lwb(const vc<t>&v,const t&a){
244.         return lower_bound(all(v),a)-v.bg;
245. }
246.  
247. vvc<int> readGraph(int n,int m){
248.         vvc<int> g(n);
249.         rep(i,m){
250.                 int a,b;
251.                 cin>>a>>b;
252.                 //sc.read(a,b);
253.                 a--;b--;
254.                 g[a].pb(b);
255.                 g[b].pb(a);
256.         }
257.         return g;
258. }
259.  
260. vvc<int> readTree(int n){
261.         return readGraph(n,n-1);
262. }
263.  
264. //sz: size of the matching
265. //mt[i]: matching mate of the vertex i
266. //VERIFY: yosupo
267. //NEERC2018B
268. //Petrozavodsk 2019w Day1 A
269. struct maxmatching{
270.         struct E{int a,b;};
271.         const vvc<int>&g;
272.         int n,sz;
273.         vi p,t,mt;
274.         vc<E> f;
275.         int non(int v){
276.                 return t[v]!=sz||p[v]==-1?v:(p[v]=non(p[v]));
277.         }
278.         void R(int a,int b){
279.                 int d=mt[a];
280.                 mt[a]=b;
281.                 if(d==-1||mt[d]!=a)return;
282.                 if(f[a].b==-1){
283.                         mt[d]=f[a].a;
284.                         R(f[a].a,d);
285.                 }else{
286.                         R(f[a].a,f[a].b);
287.                         R(f[a].b,f[a].a);
288.                 }
289.         }
290.         bool arg(int rt){
291.                 queue<int> q;
292.                 t[rt]=sz;
293.                 p[rt]=-1;
294.                 f[rt]=E{-1,-1};
295.                 q.push(rt);
296.                 while(!q.empty()){
297.                         int a=q.front();q.pop();
298.                         for(auto b:g[a]){
299.                                 if(b==rt)continue;
300.                                 if(mt[b]==-1){
301.                                         mt[b]=a;
302.                                         R(a,b);
303.                                         return true;
304.                                 }
305.                                 if(t[b]==sz){
306.                                         int x=non(a),y=non(b);
307.                                         if(x==y)continue;
308.                                         int z=rt;
309.                                         while(x!=rt||y!=rt){
310.                                                 if(y!=rt)swap(x,y);
311.                                                 if(f[x].a==a&&f[x].b==b){
312.                                                         z=x;
313.                                                         break;
314.                                                 }
315.                                                 f[x]=E{a,b};
316.                                                 x=non(f[mt[x]].a);
317.                                         }
318.                                         for(auto v:{non(a),non(b)}){
319.                                                 while(v!=z){
320.                                                         t[v]=sz;
321.                                                         p[v]=z;
322.                                                         q.push(v);
323.                                                         v=non(f[mt[v]].a);
324.                                                 }
325.                                         }
326.                                         continue;
327.                                 }
328.                                 if(t[mt[b]]==sz)continue;
329.                                 f[b]=E{-1,-1};
330.                                 t[mt[b]]=sz;
331.                                 p[mt[b]]=b;
332.                                 f[mt[b]]=E{a,-1};
333.                                 q.push(mt[b]);
334.                         }
335.                 }
336.                 return false;
337.         }
338.         maxmatching(const vvc<int>&gg):g(gg),n(g.size()),sz(0),
339.                 p(n),t(n,-1),mt(n,-1),f(n){
340.                 rep(i,n)if(mt[i]==-1)
341.                         sz+=arg(i);
342.         }
343.         //codechef HAMILG
344.         //res[i]=最大マッチングに必ず含まれるべき頂点なら 1, そうでないなら 0
345.         vi need(){
346.                 rep(i,n)if(mt[i]==-1)
347.                         arg(i);
348.                 vi res(n);
349.                 rep(i,n)res[i]=(mt[i]!=-1&&t[i]!=sz);
350.                 return res;
351.         }
352. };
353.  
354. bool adj(pi x,pi y){
355.         auto [a,b]=x;
356.         auto [d,e]=y;
357.         int g=abs(a-d),h=abs(b-e);
358.         if(g==1&&h==2)return true;
359.         if(h==1&&g==2)return true;
360.         return false;
361. }
362.  
363. vi baka{640123342,149795075,435766641,962740521,655148792,415754176,376479654,870002679,720108329,159621518,11174811,387483131,378665771,561039471,331699185,126721473,443148615,932333129,537805256,560931851,365487476,533804022,740623840,763546631,538506276,874001638,94913828,147131095,947798556,252504454,124726188,728150503,340648925,846675740,753540696,201741433,457098100,242736752,101613178,179436008,422379147,716728797,130960454,582731547,879298814,327320790,601101480,712029853,666028075,};
364. int seed;
365.  
366. using T=tuple<int,int,int>;
367. vc<pi> dxy{};
368. vc<T> sub(int n){
369.         int s=0;
370.         vvc<int> idx(n,vi(n,-1));
371.         rep(i,n)rep(j,n){
372.                 if(pi(i,j)==pi(0,0))continue;
373.                 if(pi(i,j)==pi(n-1,n-1))continue;
374.                 idx[i][j]=s++;
375.         }
376.         vvc<int> g(s);
377.         rep(i,n)rep(j,n){
378.                 if(pi(i,j)==pi(0,0))continue;
379.                 if(pi(i,j)==pi(n-1,n-1))continue;
380.                 for(auto [x,y]:dxy){
381.                         x+=i;
382.                         y+=j;
383.                         if(inc(0,x,n-1)&&inc(0,y,n-1)){
384.                                 if(pi(x,y)==pi(0,0))continue;
385.                                 if(pi(x,y)==pi(n-1,n-1))continue;
386.                                 g[idx[i][j]].pb(idx[x][y]);
387.                         }
388.                 }
389.         }
390.        
391.         //find a cycle
392.         vc<pi> lf;
393.         rep(step,n/2-1){
394.                 int x=n-1-step*2,y=step*2;
395.                 lf.eb(x-2,y+1);
396.                 lf.eb(x,y+2);
397.                 lf.eb(x-1,y);
398.                 if(step<n/2-2){
399.                         lf.eb(x-3,y+1);
400.                 }
401.         }
402.         //dmp(lf);
403.         vi c{idx[n-1][0]};
404.         for(auto [i,j]:lf)c.pb(idx[i][j]);
405.         c.pb(idx[1][n-2]);
406.         reverse(all(lf));
407.         for(auto [i,j]:lf){
408.                 tie(i,j)=pi(n-1-j,n-1-i);
409.                 //dmp2(i,j);
410.                 c.pb(idx[i][j]);
411.         }
412.         //dmp(idx);
413.         rep(i,si(c)){
414.                 int j=c[(i+1)%si(c)];
415.                 //dmp2(i,j);
416.                 assert(find(all(g[c[i]]),j)!=g[c[i]].ed);
417.         }
418.        
419.         vc<pi> pos;
420.         rep(i,n)rep(j,n)if(idx[i][j]!=-1)pos.eb(i,j);
421.        
422.         while(1){
423.                 //int seed=rand_int(0,ten(9));
424.                 mt19937 rnd(seed);
425.                
426.                 vc<bool> vis(s);
427.                 for(auto i:c)vis[i]=true;
428.        
429.                 vc<T> ans;
430.                 int cur=0;
431.                 rep(i,si(c)){
432.                         int v=c[i];
433.                         vi tmp;
434.                         while(1){
435.                                 vis[v]=true;
436.                                 tmp.pb(v);
437.                                 int mn=inf;
438.                                 vi buf;
439.                                 for(auto j:g[v])if(!vis[j]){
440.                                         int cnt=0;
441.                                         for(auto k:g[j])if(!vis[k])cnt++;
442.                                         if(mn>cnt){
443.                                                 buf.clear();
444.                                                 mn=cnt;
445.                                         }
446.                                         if(mn==cnt){
447.                                                 buf.pb(j);
448.                                         }
449.                                 }
450.                                 if(buf.empty())break;
451.                                 v=buf[rnd()%si(buf)];
452.                         }
453.                         for(auto w:tmp){
454.                                 ans.eb(pos[w].a,pos[w].b,cur);
455.                         }
456.                         cur^=1;
457.                         reverse(all(tmp));
458.                         for(auto w:tmp){
459.                                 ans.eb(pos[w].a,pos[w].b,cur);
460.                         }
461.                 }
462.  
463.                 if(si(ans)==2*n*n-4){
464.                         baka.pb(seed);
465.                         return ans;
466.                 }
467.         }
468. }
469.  
470. bool adj(T x,T y){
471.         auto [a,b,c]=x;
472.         auto [d,e,f]=y;
473.         if(c!=f)return pi(a,b)==pi(d,e);
474.         int g=abs(a-d),h=abs(b-e);
475.         if(g==1&&h==2)return true;
476.         if(h==1&&g==2)return true;
477.         return false;
478. }
479.  
480. void check(int n,vc<T> z){
481.         assert(si(z)==2*n*n-4);
482.         for(auto [a,b,c]:z){
483.                 assert(inc(0,a,n-1));
484.                 assert(inc(0,b,n-1));
485.                 assert(inc(0,c,1));
486.                 assert(pi(a,b)!=pi(0,0));
487.                 assert(pi(a,b)!=pi(n-1,n-1));
488.         }
489.         rep(i,si(z)){
490.                 assert(adj(z[i],z[(i+1)%si(z)]));
491.         }
492.         mkuni(z);
493.         assert(si(z)==2*n*n-4);
494. }
495.  
496. void slv(){
497. }
498.  
499. signed main(){
500.         cin.tie(0);
501.         ios::sync_with_stdio(0);
502.         cout<<fixed<<setprecision(20);
503.        
504.         rep(i,2)rep(j,2)rep(k,2){
505.                 int a=1,b=2;
506.                 if(i)a=-a;
507.                 if(j)b=-b;
508.                 if(k)swap(a,b);
509.                 dxy.eb(a,b);
510.         }
511.        
512.         /*for(int n=4;n<=100;n+=2){
513.                 cerr<<n<<endl;
514.                 auto ans=sub(n);
515.                 check(n,ans);
516.         }
517.        
518.         cerr<<baka<<endl;*/
519.        
520.         int n;cin>>n;
521.         seed=baka[(n-4)/2];
522.         auto ans=sub(n);
523.         for(auto [i,j,k]:ans){
524.                 cout<<i+1<<" "<<j+1<<" "<<k<<"\n";
525.         }
526. }
527.