Bạn đang chơi trò đoán số với JOI-chan. Trước tiên, JOI-chan sắp xếp mỗi số nguyên từ \(1\) đến \(N\) đúng một lần theo một thứ tự nào đó để tạo thành một dãy số. Gọi dãy này là đáp án. Bạn được thực hiện nhiều nhất \(L\) lần dự đoán; bạn thắng nếu đoán đúng đáp án trong không quá \(L\) lần.

Trong mỗi lần dự đoán, bạn đưa cho JOI-chan một dãy gồm \(N\) số nguyên từ \(1\) đến \(N\). Dãy dự đoán được phép chứa các số nguyên trùng nhau. Sau mỗi lần dự đoán, bạn được biết có bao nhiêu vị trí mà dãy dự đoán trùng với đáp án.

Yêu cầu

Hãy viết chương trình đoán đúng dãy đáp án trong số lần dự đoán cho phép. Đây là bài toán tương tác: chương trình trao đổi với hệ thống chấm qua đầu vào chuẩn và đầu ra chuẩn.

Dữ liệu vào

Khi bắt đầu, đọc một dòng từ đầu vào chuẩn chứa số nguyên \(N\).

Giới hạn \(L\) được quy định trong phần Phân nhóm; đầu vào ban đầu chỉ chứa \(N\). Các dữ liệu nhận được sau đó là phản hồi cho từng dự đoán, theo giao thức dưới đây.

Dữ liệu ra

Các dự đoán được gửi qua đầu ra chuẩn theo giao thức dưới đây.

Giao thức tương tác

Sau khi đọc \(N\), chương trình phải luân phiên gửi một dự đoán ra đầu ra chuẩn và đọc một phản hồi từ đầu vào chuẩn:

1. Để gửi một dự đoán, in đúng \(N\) dòng. Dòng thứ \(i\) chứa số nguyên thứ \(i\) của dãy dự đoán. Mọi số được in phải nằm trong đoạn từ \(1\) đến \(N\); các số trong cùng một dự đoán có thể trùng nhau. Một dự đoán chỉ gồm \(N\) số này, mỗi số trên một dòng, không có ký hiệu lệnh hay tiền tố khác.
2. Sau khi gửi dự đoán, đọc một dòng chứa một số nguyên: số vị trí mà dãy vừa dự đoán trùng với đáp án.
3. Nếu phản hồi bằng \(N\), bạn đã đoán đúng. Chương trình phải kết thúc ngay tại thời điểm đó và không được in thêm bất kỳ nội dung nào. Nếu chưa đoán đúng, có thể tiếp tục dự đoán, nhưng tổng số lần dự đoán không được vượt quá \(L\).

Để tránh việc đọc đầu vào bị chặn do dữ liệu đầu ra còn nằm trong bộ đệm, cần đẩy dữ liệu đầu ra trước khi chờ phản hồi. Gọi fflush(stdout); hoặc thực hiện thao tác tương đương trước khi đọc.

Đoạn chương trình C sau minh họa cách trao đổi với hệ thống chấm:

#include <stdio.h>
int main(void) {
    int i, N, ret;
    scanf("%d", &N);
    for (;;) {
        for (i = 1; i <= N; i++) {
            printf("%d\n", i);     // Gui du doan
        }
        fflush(stdout);           // Day dau ra truoc khi doc phan hoi
        scanf("%d", &ret);         // Doc phan hoi cua he thong cham
        if (ret == N) break;
    }
    return 0;
}

Đây là chương trình minh họa giao tiếp; nó lặp lại dự đoán \(1,2,\ldots,N\).

Ràng buộc

• Đáp án là một hoán vị của các số nguyên \(1,2,\ldots,N\).
• Mỗi dự đoán gồm đúng \(N\) số nguyên trong đoạn \([1,N]\), không nhất thiết là một hoán vị.
• Độ dài \(N\) và giới hạn số lần dự đoán \(L\) tuân theo các nhóm bên dưới.
• Với mọi bộ dữ liệu chấm, nếu dùng thuật toán thích hợp thì có thể đoán đúng trong không quá \(L\) lần, bất kể đáp án là hoán vị nào của các số nguyên từ \(1\) đến \(N\).
• Giới hạn thời gian CPU: \(2\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

• Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
• Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
• Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
• Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ dữ liệu chiếm \(10\%\) tổng số điểm thỏa mãn \(1\le N\le7\) và \(L=6000\).
• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(1\le N\le50\) và \(L=3000\).
• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(1\le N\le100\) và \(L=1000\).
• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn \(1\le N\le100\) và \(L=700\).

Ví dụ giao tiếp

Cột Input là dữ liệu hệ thống chấm gửi cho chương trình; cột Output là dữ liệu chương trình gửi cho hệ thống chấm. Mỗi số nằm trên một dòng riêng. Các nhãn cột chỉ dùng để trình bày, không thuộc dữ liệu giao tiếp.

3
1
0
3

3
2
1
1
2
3
2
3
1

Trong ví dụ này, chương trình đọc \(N=3\), rồi lần lượt dự đoán \((3,2,1)\), \((1,2,3)\) và \((2,3,1)\). Các phản hồi tương ứng là \(1\), \(0\) và \(3\). Chương trình đoán đúng sau \(3\) lần dự đoán và kết thúc khi nhận được phản hồi cuối cùng.