Đây là bài toán tương tác. Sau khi in mỗi dòng, bạn cần xóa bộ đệm đầu ra (flush). Bạn có thể dùng cout << flush trong C++, System.out.flush() trong Java, và sys.stdout.flush() trong Python. Bạn phải tuân thủ nghiêm ngặt các hướng dẫn trong phần Tương tác; nếu không bạn có thể nhận các kết quả như sai (Wrong Answer), quá thời gian (Time Limit Exceeded) hoặc các lỗi khác.

Vì công việc trong hầm mỏ rất vất vả và tốn thời gian, các chú lùn quyết định tìm kiếm sự trợ giúp để tự động hóa một số công việc của mình. Nhiệm vụ hiện tại của họ là phân loại $N$ khoáng sản (được định danh bởi các số từ $1$ đến $N$) vào các lớp khác nhau. Để hỗ trợ việc này, Chú lùn Công nhân đã lắp đặt một băng chuyền mới. Các chú lùn có thể thêm các mẫu khoáng sản vào đầu băng chuyền và lấy chúng ra khỏi cuối băng chuyền (tức là lấy ra những khoáng sản được thêm vào sớm nhất).

Thật không may, băng chuyền này không có cơ sở tri thức, nên nó không thể xác định lớp của bất kỳ khoáng sản nào trên đó. Tuy nhiên, nó có một tính năng hữu ích khác: nó hiển thị số lượng các lớp khoáng sản phân biệt hiện đang có trên băng chuyền. Hóa ra điều này là đủ cho hầm mỏ, vì các chú lùn không cần biết lớp của từng khoáng sản: họ chỉ cần tách các khoáng sản thành các đống có cùng lớp.

Bạn có thể giúp các chú lùn giải quyết nhiệm vụ này bằng cách sử dụng băng chuyền không?

Tương tác

Các lớp của khoáng sản được cố định ngay từ đầu và không phụ thuộc vào các truy vấn được thực hiện.

Đầu tiên, đọc một dòng chứa một số nguyên $N$, số lượng khoáng sản cần phân loại. Sau đó, bạn có thể thực hiện các thao tác thuộc hai loại sau:

• + id — khoáng sản có định danh id được thêm vào đầu băng chuyền.
• - — khoáng sản ở cuối băng chuyền được lấy ra. Nếu băng chuyền trống, không có gì xảy ra.

Sau mỗi thao tác, băng chuyền xuất ra một dòng chứa số lượng các lớp phân biệt hiện có trên đó.

Để in ra câu trả lời, trước tiên hãy in một dòng chứa ! theo sau là $k$ là số lượng các lớp phân biệt trong mỏ. Sau đó in ra $k$ dòng, mỗi dòng mô tả một lớp. Mỗi dòng chứa một số $c_i$ theo sau là $c_i$ định danh khoáng sản thuộc lớp đó. Mỗi khoáng sản trong số $N$ khoáng sản phải xuất hiện trong đúng một lớp. Bạn có thể in các lớp và các khoáng sản trong mỗi lớp theo bất kỳ thứ tự nào.

Hãy nhớ flush đầu ra sau mỗi thao tác và sau khi in câu trả lời. Nhớ đặt dấu cách giữa các số và các ký hiệu +, -, !. Bạn phải đọc tất cả dữ liệu từ trình tương tác.

Giới hạn

$1 \le N \le 500$, bạn có thể thực hiện tối đa $35\,000$ thao tác.

Ví dụ

Dữ liệu vào 1

3
1
2
2
2

Kết quả 1

+ 1
+ 2
+ 3
-
! 2
2 1 3
1 2

Giải thích

Trong ví dụ đầu tiên, $N = 3$ và lớp của các khoáng sản $1, 2, 3$ lần lượt là $1, 2, 1$.

Kiểm thử cục bộ

Trong phần Files, bạn có thể tìm thấy tệp A.zip chứa các test ví dụ và trình chấm grader.cpp. Để kiểm thử lời giải của bạn, hãy biên dịch nó, sau đó truyền tên test và tệp thực thi của bạn vào ./grader đã biên dịch:

./grader [test] [executable]

Ví dụ: ./grader 0b.in ./abc

Trình chấm ví dụ không được đảm bảo hoạt động giống hệt với trình chấm chính thức. Tuy nhiên, cả hai đều không thích ứng (non-adaptive).