#include "ds.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;
#define st first
#define nd second

struct Pair {
    ll v, mx;
};

vector<pair<ll, ll>> s;

vector<ll> rec(vector<Pair> a, ll l, ll max) {
    if (a.size() == 1) {
        if (l != max) {
            exchange(l, max);
            s.emplace_back(l, max);
        }
        return {a[0].v};
    }

    exchange(l, max);
    s.emplace_back(l, max);
    for (auto &[v, mx] : a) {
        mx = query(v + 1);
    }
    sort(a.begin(), a.end(), [](auto &v, auto &w) {
        return v.mx < w.mx;
    });

    vector<ll> ret;
    ret.push_back(a[0].v);
    vector<vector<Pair>> b = {{a[1]}};
    for (ll i = 2; i < a.size(); i++) {
        if (b.back()[0].mx == a[i].mx)
            b.back().push_back(a[i]);
        else {
            b.emplace_back();
            b.back().push_back(a[i]);
        }
    }

    l++;
    for (auto & part : b) {
        vector<ll> tmp = rec(part, l, part[0].mx);
        for (ll v: tmp)
            ret.push_back(v);
        l += (ll) part.size();
    }

    return ret;
}

void dlasciezki(ll n) {
    vector<Pair> a(n);
    for (ll v = 1; v < n; v++) {
        a[v].v = v;
        a[v].mx = query(v + 1);
    }
    sort(a.begin(), a.end(), [](auto &v, auto &w) {
        return v.mx < w.mx;
    });

    vector<ll> ret = {0};
    vector<vector<Pair>> b = {{a[1]}};
    for (ll i = 2; i < a.size(); i++) {
        if (b.back()[0].mx == a[i].mx)
            b.back().push_back(a[i]);
        else {
            b.emplace_back();
            b.back().push_back(a[i]);
        }
    }

    ll l = 1;
    for (auto & part : b) {
        vector<ll> tmp = rec(part, l, part[0].mx);
        for (ll v: tmp)
            ret.push_back(v);
        l += (ll) part.size();
    }

    vector<ll> ord(n - 1);
    std::iota(ord.begin(), ord.end(), 1);
    vector<ll> pos(n);
    std::iota(pos.begin(), pos.end(), -1);
    while (not s.empty()) {
        auto p = s.back();
        swap(pos[p.st], pos[p.nd]);
        swap(ord[pos[p.st]], ord[pos[p.nd]]);
        s.pop_back();
    }

    vector<ll> vord(n);
    for (ll i = 0; i < n; i++)
        vord[ret[i]] = i;

    vector<ll> parent(n - 1), val(n - 1);
    for (ll i = 1; i < n; i++) {
        parent[i - 1] = ret[vord[i] - 1] + 1;
        val[i - 1] = ord[vord[i] - 1];
    }

    answer(parent, val);
}

bool isAncestor(Pair v, Pair anc) {
    exchange(v.mx, anc.mx);
    if (query(v.v) == v.mx) {
        exchange(v.mx, anc.mx);
        return true;
    }
    exchange(v.mx, anc.mx);
    return false;
}

void on2(ll n) {
    vector<bool> u(n + 1);
    for (ll l = 1; l <= n - 1; l++) {
        ll min = n;
        for (ll v = 2; v <= n; v++) {
            if (u[v])
                continue;
            ll mx = query(v);
            if (mx < l)
                u[v] = true;
            else
                min = ::min(min, mx);
        }

        if (min > l) {
            exchange(min, l);
            s.emplace_back(min, l);
        }
    }

    vector<Pair> a(n - 1);
    for (ll i = 0; i < n - 1; i++) {
        a[i].v = i + 2;
        a[i].mx = query(a[i].v);
    }

    sort(a.begin(), a.end(), [](auto &v, auto &w) {
        return v.mx < w.mx;
    });

    vector<ll> parent(n + 1);
    for (ll i = 0; i < n - 1; i++) {
        parent[a[i].v] = 1;
        for (ll j = 0; j < i; j++) {
            if (isAncestor(a[i], a[j]))
                parent[a[i].v] = a[j].v;
        }
    }

    vector<ll> ord(n - 1);
    std::iota(ord.begin(), ord.end(), 1);
    vector<ll> pos(n);
    std::iota(pos.begin(), pos.end(), -1);
    while (not s.empty()) {
        auto p = s.back();
        swap(pos[p.st], pos[p.nd]);
        swap(ord[pos[p.st]], ord[pos[p.nd]]);
        s.pop_back();
    }

    vector<ll> vord(n + 1);
    for (ll i = 0; i < n - 1; i++)
        vord[a[i].v] = i;

    vector<ll> val(n - 1);
    for (ll v = 2; v <= n; v++) {
        val[v - 2] = ord[vord[v]];
    }
    parent.erase(parent.begin());
    parent.erase(parent.begin());

    answer(parent, val);
}

void solve(ll n, ll lim1, ll lim2) {
    if (n == 1) {
        answer(vector<ll>(), vector<ll>());
        return;
    }

    ll subtask = lim1 % 10;
    if (subtask == 1 or subtask == 3 or subtask == 6) {
        dlasciezki(n);
    }
    on2(n);
}