<p>There is a <strong>hidden permutation</strong> of n integers. Recall that a permutation of n is a sequence where each integer from <strong>1 to n</strong> (both inclusive) appears <strong>exactly once</strong>.</p> <p>Your task is to unravel the permutation using queries.</p> <h3>Query Mechanism</h3>

Each query consists of:

<ul> <li>A sequence (not necessarily a permutation) with <strong>n integers</strong> ranging from 1 to n (both inclusive)</li> </ul>

Each query is answered with:

<ul> <li>An integer <strong>x</strong>, indicating the <strong>number of positions</strong> where the corresponding element in your query sequence matches that of the hidden permutation</li> </ul> <h3>Example</h3>

If the hidden permutation is <code>{1, 3, 4, 2, 5}</code> and your query is <code>{2, 3, 5, 2, 5}</code>:

<ul> <li>Position 1: 1 �?2 �?/li> <li>Position 2: 3 = 3 �?/li> <li>Position 3: 4 �?5 �?/li> <li>Position 4: 2 = 2 �?/li> <li>Position 5: 5 = 5 �?/li> </ul> <p>The answer will be <strong>3</strong> (three positions match).</p> <h2>Input</h2> <p>There is only one test case in each test file.</p> <p>The first line contains an integer <strong>n</strong> (1 �?n �?10³) indicating the length of the hidden permutation.</p> <h2>Interaction Protocol</h2> <h3>To Ask a Query</h3>

Output one line in the following format:

<pre><code class="language-">0 a[1] a[2] ... a[n]</code></pre>

Where:

<ul> <li>First output <code>0</code> followed by a space</li> <li>Then print a sequence of n integers ranging from 1 to n, separated by spaces</li> <li><strong>After flushing your output</strong>, read a single integer x indicating the answer to your query</li> </ul> <h3>To Submit Your Guess</h3>

Output one line in the following format:

<pre><code class="language-">1 p[1] p[2] ... p[n]</code></pre>

Where:

<ul> <li>First output <code>1</code> followed by a space</li> <li>Then print your guessed permutation of n, separated by spaces</li> <li><strong>After flushing your output, exit immediately</strong></li> </ul> <h3>Important Notes</h3> <ul> <li>The answer for each test case is <strong>pre-determined</strong> (the interactor is not adaptive)</li> <li>Your final guess <strong>does not count</strong> as a query</li> <li>Invalid queries or exceeding the query limit may result in a Time Limit Exceeded verdict</li> </ul> <h3>Flushing Output</h3> <p>To flush your output, use:</p> <table> <thead> <tr> <th>Language</th> <th>Flush Command</th> </tr> </thead> <tbody> <tr> <td>C (printf)</td> <td><code>fflush(stdout)</code></td> </tr> <tr> <td>C++ (cout)</td> <td><code>cout.flush()</code></td> </tr> <tr> <td>Java</td> <td><code>System.out.flush()</code></td> </tr> <tr> <td>Python</td> <td><code>stdout.flush()</code></td> </tr> </tbody> </table> <h2>Scoring</h2> <p>This problem is graded based on the <strong>number of queries</strong> you use.</p> <h3>Requirements</h3> <ul> <li>You <strong>must use fewer than 10,000 queries</strong> to receive any points</li> <li>After that, your answer will be compared to a reference solution (<code>best_queries</code>)</li> </ul> <h3>Score Calculation</h3> <p>Your final score is calculated as the <strong>average</strong> across all test cases:</p> <pre><code class="language-">Score = 100 × clamp((10000 - your_queries) / (10000 - best_queries), 0, 1)</code></pre>

Where:

<ul> <li><strong>your_queries</strong>: Number of queries you used</li> <li><strong>best_queries</strong>: Number of queries in the reference solution</li> <li>Lower query count = higher score</li> </ul> <h2>Example Interaction</h2>

<strong>Note:</strong> In the example below, <code>n = 5</code> and the hidden permutation is <code>{3, 1, 5, 2, 4}</code>.

<table> <thead> <tr> <th>Your Output</th> <th>Interactor Response</th> <th>Explanation</th> </tr> </thead> <tbody> <tr> <td><code>0 3 1 3 2 2</code></td> <td><code>3</code></td> <td>Matches at positions 1, 2, and 4</td> </tr> <tr> <td><code>0 3 1 5 2 2</code></td> <td><code>4</code></td> <td>Matches at positions 1, 2, 3, and 4</td> </tr> <tr> <td><code>0 3 5 4 4 4</code></td> <td><code>2</code></td> <td>Matches at positions 1 and 5</td> </tr> <tr> <td><code>1 3 1 5 2 4</code></td> <td>�?/td> <td>Final guess submitted</td> </tr> </tbody> </table> <h3>Example Analysis</h3> <p>From the queries: 1. Query <code>{3, 1, 3, 2, 2}</code> �?3 matches 2. Query <code>{3, 1, 5, 2, 2}</code> �?4 matches (one more match when position 3 is 5) 3. Query <code>{3, 5, 4, 4, 4}</code> �?2 matches (positions 1 and 5)</p> <p>From these queries, we can deduce the hidden permutation is <code>{3, 1, 5, 2, 4}</code>.</p> <h2>Strategy Tips</h2> <p>1. <strong>Start simple</strong>: Try systematic approaches like checking one position at a time 2. <strong>Use information wisely</strong>: Each query gives you information about multiple positions 3. <strong>Binary search</strong>: Consider strategies that eliminate multiple possibilities per query 4. <strong>Optimize</strong>: Try to minimize queries while maintaining correctness 5. <strong>Pre-determination</strong>: Since the permutation is pre-determined, you can use deterministic strategies</p> <hr> <h2>Problem Metadata</h2> <strong>Type:</strong> Interactive Problem <strong>Time Limit:</strong> 4 seconds <strong>Memory Limit:</strong> 1024 MB <hr> <h2>Model Information</h2> <p><strong>Model:</strong> GPT 5 Thinking</p> <p><strong>Score:</strong> 0.0</p> <h3>Solution Code</h3> <pre><code>#include <bits/stdc++.h> using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int n;
if (!(cin >> n)) return 0;

auto ask = [&](const vector<int>& s) -> int {
    cout << 0;
    for (int x : s) {
        cout << ' ' << x;
    }
    cout << '\n' << flush;
    int x;
    if (!(cin >> x)) exit(0);
    if (x == -1) exit(0);
    return x;
};

auto give_answer = [&](const vector<int>& perm) {
    cout << 1;
    for (int i = 0; i < (int)perm.size(); ++i) {
        cout << ' ' << perm[i];
    }
    cout << '\n' << flush;
    // exit immediately
};

if (n == 1) {
    give_answer(vector<int>{1});
    return 0;
}

int m = 0;
while ((1 << m) < n) ++m;

int b = 1, c = 2;

// Precompute masks for each bit
vector<vector<char>> mask(m, vector<char>(n, 0));
vector<int> sizeT(m, 0);
for (int t = 0; t < m; ++t) {
    int cnt = 0;
    for (int j = 0; j < n; ++j) {
        int in = ((j >> t) & 1);
        mask[t][j] = (char)in;
        if (in) ++cnt;
    }
    sizeT[t] = cnt;
}

vector<int> pos_bits(n + 1, 0); // stores value of (pos[v]-1), built bit by bit

vector<int> s(n);
vector<int> delta(n + 1);

for (int t = 0; t < m; ++t) {
    // Query r2: 'b' on T, 'c' elsewhere
    for (int j = 0; j < n; ++j) {
        s[j] = mask[t][j] ? b : c;
    }
    int r2 = ask(s);

    long long sumDelta = 0;

    // v = c: delta = 1 - r2
    delta[c] = 1 - r2;

    // v = b: delta = 0
    delta[b] = 0;

    // For other v:
    for (int v = 1; v <= n; ++v) {
        if (v == b || v == c) continue;
        for (int j = 0; j < n; ++j) {
            s[j] = mask[t][j] ? v : c;
        }
        int r1 = ask(s);
        delta[v] = r1 - r2;
    }

    for (int v = 1; v <= n; ++v) sumDelta += delta[v];

    int Ub_num = sizeT[t] - (int)sumDelta;
    int Ub = Ub_num / n; // should be 0 or 1

    for (int v = 1; v <= n; ++v) {
        int bit = delta[v] + Ub; // should be 0 or 1
        if (bit < 0) bit = 0;
        if (bit > 1) bit = 1;
        pos_bits[v] |= (bit << t);
    }
}

// Build permutation from positions
vector<int> perm(n + 1, 0);
vector<char> used(n + 1, 0);
vector<int> bad_vals;
for (int v = 1; v <= n; ++v) {
    int idx = pos_bits[v] + 1;
    if (idx >= 1 && idx <= n && !used[idx]) {
        perm[idx] = v;
        used[idx] = 1;
    } else {
        bad_vals.push_back(v);
    }
}
vector<int> free_idx;
for (int i = 1; i <= n; ++i) {
    if (!used[i]) free_idx.push_back(i);
}
for (size_t k = 0; k < bad_vals.size() && k < free_idx.size(); ++k) {
    perm[free_idx[k]] = bad_vals[k];
}

vector<int> ans(n);
for (int i = 1; i <= n; ++i) ans[i - 1] = perm[i];

give_answer(ans);
return 0;

}</code></pre>