//
// Created by BigBag on 15.03.2024 20:18:32
//

#include <bits/stdc++.h>

using namespace std;

#ifdef BigBag
#define DEBUG for (bool ____DEBUG = true; ____DEBUG; ____DEBUG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl

template<class ...Ts>
auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }

#else
#define DEBUG while (false)
#define LOG(...)
#endif

const int max_n = -1, inf = 1000111222;

template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
    first = std::find_if(first, last, p);
    if (first != last)
        for (ForwardIt i = first; ++i != last;)
            if (!p(*i))
                *first++ = std::move(*i);
    return first;
}

template< class T, class Alloc, class Pred >
constexpr typename std::vector<T, Alloc>::size_type
erase_if( std::vector<T, Alloc>& c, Pred pred ) {
    auto it = std::remove_if(c.begin(), c.end(), pred);
    auto r = c.end() - it;
    c.erase(it, c.end());
    return r;
}

struct Vertex {
    int pr, nxt, jump;
    Vertex(int v): pr(v), nxt(v), jump(v) {}
};
struct PathHolder {
    static const int jump_sz = 100;
    vector<Vertex> a;
    PathHolder(int n) {
        a.assign(n, 0);
        iota(a.begin(), a.end(), 0);
    }
    void delEdge(int u, int v) {
        a[v].pr = v;
        a[u].nxt = u;
        for (int i = 0, x = u; i < jump_sz; ++i) {
            a[x].jump = u, x = a[x].pr;
        }
    }
    void addEdge(int u, int v) {
        a[u].nxt = v;
        a[v].pr = u;
        int x = u, steps = 0;
        while (steps + 1 < jump_sz && x != a[x].pr) {
            x = a[x].pr;
            ++steps;
        }
        int f = u;
        while ((++steps) <= jump_sz) f = a[f].nxt;
        for (; x != u; x = a[x].nxt, f = a[f].nxt) {
            a[x].jump = f;
        }
        a[x].jump = f;
    }
    int getRoot(int v) const {
        while (v != a[v].jump) v = a[v].jump;
        return v;
    }
    Vertex& operator [](int v) { return a[v]; }
    bool in(int v) const { return v != a[v].pr; }
    bool out(int v) const { return v != a[v].nxt; }
};
mt19937 gen(time(0) + clock());
struct Solver {
    long long ops = 1e9, tot = 0, n;
    PathHolder p;
    vector<vector<int>> g, rg;
    vector<int> s, t;
    vector<pair<int, int>> e;
    Solver(int n, vector<pair<int, int>> e): p(n), g(n), rg(n), s(n), t(n), n(n), e(e) {
        for (auto p: e) {
            assert(max(p.first, p.second) < n);
            g[p.first].push_back(p.second);
            rg[p.second].push_back(p.first);
        }
        iota(s.begin(), s.end(), 0);
        iota(t.begin(), t.end(), 0);
    }
    vector<int> iter() {
        while (ops >= 0 && (n == 1 || !e.empty())) {
            e.clear();
            erase_if(s, [&](int v) { return p.in(v); });
            erase_if(t, [&](int v) { return p.out(v); });
            for (int to: s)
                for (int from: rg[to])
                    if (p.out(from)) e.push_back({from, to});
            for (int from: t)
                for (int to: g[from])
                    e.push_back({from, to});
            shuffle(e.begin(), e.end(), gen);
            for (auto[u, v]: e) {
                --ops;
                if ((p.out(u) && p.in(v))) continue;
                if (p.getRoot(u) == p.getRoot(v)) continue;
                if ((p.out(u) || p.in(v)) && gen() % 2)
                    continue;
                if (p.out(u)) {
                    s.push_back(p[u].nxt);
                    p.delEdge(u, p[u].nxt);
                } else if (p.in(v)) {
                    t.push_back(p[v].pr);
                    p.delEdge(p[v].pr, v);
                } else ++tot;
                p.addEdge(u, v);
            }
            if (tot + 1 == n) {
                int v = p.getRoot(0);
                vector<int> res;
                for (int i = 0; i < n; ++i, v = p[v].pr)
                    res.push_back(v);
                return {res.rbegin(), res.rend()};
            }
        }
        return {};
    }
};

vector<int> HF(int n, vector<pair<int, int>> e) {
    vector<Solver> solvers;
    for (int i = 0; i < 47; ++i) {
        solvers.push_back(Solver(n, e));
    }
    while (true) {
        for (auto &s : solvers) {
            auto ans = s.iter();
            if (!ans.empty()) return ans;
        }
    }
}

vector<int> find_cycle(int n, vector<pair<int, int>> e) {
    vector<pair<int, int>> ne;
    int s = n, t = n + 1;
    for (auto [u, v] : e) {
        if (v == 7) {
            ne.push_back({u, t});
        } else {
            ne.push_back({u, v});
        }
    }
    ne.push_back({s, 7});
    auto res = HF(n + 2, ne);
    if (!res.empty()) {
        assert(res[0] == s && res.back() == t);
        res.pop_back();
        res.erase(res.begin());
    }
    return res;
}

const int dx[] = {-1, -1, -2, -2, 1, 1, 2, 2};
const int dy[] = {-2, 2, -1, 1, -2, 2, -1, 1};

int n;

int get_num(int tp, int x, int y) {
    return tp * (n * n - 2) + x * n + y - 1;
}

bool is_in(int x, int y) {
    return 0 <= x && 0 <= y && x < n && y < n && 0 < x + y && x + y < 2 * n - 2;
}

vector<array<int, 3>> solve() {
    vector<pair<int, int>> e;
    for (int tp = 0; tp < 2; ++tp) {
        for (int x = 0; x < n; ++x) {
            for (int y = 0; y < n; ++y) {
                if (!is_in(x, y)) {
                    continue;
                }
                e.push_back({get_num(tp, x, y), get_num(tp ^ 1, x, y)});
                for (int k = 0; k < 8; ++k) {
                    const int nx = x + dx[k], ny = y + dy[k];
                    if (is_in(nx, ny)) {
                        e.push_back({get_num(tp, x, y), get_num(tp, nx, ny)});
                    }
                }
            }
        }
    }
    auto vs = find_cycle(2 * n * n - 4, e);
    while (vs.empty()) {
        vs = find_cycle(2 * n * n - 4, e);
    }
    vector<array<int, 3>> res;
    for (int v : vs) {
        int tp = v / (n * n - 2);
        v %= (n * n - 2);
        ++v;
        int x = v / n, y = v % n;
        res.push_back({1 + x, 1 + y, tp});
    }
    return res;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    auto ans = solve();
    for (auto a : ans) {
        cout << a[0] << " " << a[1] << " " << a[2] << endl;
    }
    return 0;
}