이 문제는 인터랙티브 문제입니다. 각 줄을 출력한 후에는 반드시 출력 버퍼를 비워야(flush) 합니다. C++에서는 cout << flush, Java에서는 System.out.flush(), Python에서는 sys.stdout.flush()를 사용할 수 있습니다. 상호작용 섹션의 지침을 엄격히 따라야 하며, 그렇지 않으면 오답(Wrong Answer), 시간 초과(Time Limit Exceeded) 등의 판정을 받을 수 있습니다.

광산에서의 작업은 힘들고 시간이 많이 걸리기 때문에, 드워프들은 일부 작업을 자동화하기 위해 도움을 구하기로 결정했습니다. 현재 그들의 작업은 $N$개의 광물($1$부터 $N$까지의 번호로 식별됨)을 서로 다른 등급(class)으로 분류하는 것입니다. 이를 돕기 위해 일꾼 드워프가 새로운 컨베이어 벨트를 설치했습니다. 드워프들은 벨트의 맨 앞에 광물 샘플을 추가하고 벨트의 맨 끝에서 광물을 제거할 수 있습니다(즉, 가장 먼저 추가된 광물을 제거함).

안타깝게도 이 컨베이어 벨트에는 지식 베이스가 없어서 벨트 위에 있는 어떤 광물의 등급도 식별할 수 없습니다. 하지만 또 다른 유용한 기능이 있습니다. 바로 현재 벨트 위에 있는 서로 다른 광물 등급의 개수를 표시해 주는 것입니다. 드워프들은 각 광물의 등급을 알 필요 없이 같은 등급의 광물끼리 무더기로 분리하기만 하면 되므로, 광산에서는 이 기능만으로도 충분하다는 것이 밝혀졌습니다.

컨베이어 벨트를 사용하여 드워프들이 이 작업을 해결할 수 있도록 도와주겠습니까?

상호작용

광물의 등급은 처음에 고정되어 있으며 수행하는 질의에 따라 변하지 않습니다.

먼저 분류할 광물의 개수를 나타내는 정수 $N$이 포함된 한 줄을 읽습니다. 그런 다음, 다음 두 가지 유형의 연산을 수행할 수 있습니다:

• + id — 식별자가 id인 광물을 컨베이어 벨트의 맨 앞에 추가합니다.
• - — 컨베이어 벨트의 맨 끝에 있는 광물을 제거합니다. 벨트가 비어 있으면 아무 일도 일어나지 않습니다.

각 연산 후, 컨베이어 벨트는 현재 벨트 위에 있는 서로 다른 등급의 개수를 한 줄로 출력합니다.

정답을 출력하려면 먼저 !와 광산에 있는 서로 다른 등급의 개수인 $k$를 공백으로 구분하여 한 줄에 출력합니다. 그런 다음 각 등급을 설명하는 $k$개의 줄을 출력합니다. 각 줄에는 정수 $c_i$와 해당 등급에 속하는 $c_i$개의 광물 식별자가 포함되어야 합니다. $N$개의 광물은 각각 정확히 하나의 등급에 나타나야 합니다. 등급들과 각 등급 내의 광물들은 어떤 순서로 출력해도 됩니다.

각 연산 후와 정답을 출력한 후에는 반드시 출력을 비워야(flush) 합니다. 숫자와 +, -, ! 기호 사이에는 공백을 두어야 합니다. 인터랙터로부터 모든 데이터를 읽어야 합니다.

제한

$1 \le N \le 500$, 최대 $35\,000$번의 연산을 수행할 수 있습니다.

예제

예제 입력 1

3
1
2
2
2

예제 출력 1

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

노트

첫 번째 예제 테스트에서는 $N = 3$이고, 광물 $1, 2, 3$의 등급은 각각 $1, 2, 1$입니다.

로컬 테스트

Files 섹션에서 예제 테스트와 채점기 grader.cpp가 포함된 A.zip을 찾을 수 있습니다. 솔루션을 테스트하려면 컴파일한 후 컴파일된 ./grader에 테스트 이름과 실행 파일을 전달하세요:

./grader [test] [executable]

예시: ./grader 0b.in ./abc

예제 채점기는 공식 채점기와 완전히 동일하게 동작한다고 보장되지 않습니다. 그러나 둘 다 적응형(adaptive)이 아닙니다.