시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 3 3 100.000%

문제

상범 마법 팬케이크 하우스의 요리사는 가끔씩 팬케이크를 만들다가 잠에 빠진다. 그래서 쌓아둔 팬케이크의 한쪽이 종종 타버린다. 명백하게 탄 팬케이크를 서빙하는 건 좋은 생각이 아니다. 서빙하기 전에 웨이트리스는 팬케이크 더미를 배치해서 타버린 쪽이 아래를 향하도록 할 것이다. 또, 가장 위에는 크기가 제일 작은 팬케이크를, 가장 아래에는 크기가 제일 큰 팬케이크를 놓아 크기 순으로 정렬을 하려고 한다. 웨이트리스를 도와 올바르게 팬케이크를 쌓는 프로그램을 작성하시오.

우리는 한쪽면이 타버린 N개의 팬케이크 더미를 뒤집어야 한다. 우리가 위에서부터 k개의 팬케이크를 하나의 단위로 뒤집으면 맨 위에 있던 팬케이크는 k번째로 들어가고, k번째에 있던 팬케이크는 맨 위로 올라오게 된다.

예를 들면 다음과 같다.(+는 바닥이 탄 것, -는 위가 탄 것, 숫자는 팬케이크의 크기)

+1 -3 -2 [flip 2] => +3 -1 -2 [flip 1] => -3 -1 -2 [flip 3] => +2 +1 +3 [flip 1] => -2 +1 +3 [flip 2] => -1 +2 +3 [flip 1] => +1 +2 +3

최대 3n-2 번의 뒤집기(flip)한 수열을 찾는 프로그램을 만들어야 한다.

(수열의 처음과 마지막은 처음 주어진 상태와 아래가 모두 탄 팬케이크로 만든 상태가 된다)

입력

첫 줄에 테스트 케이스의 수 N이 입력으로 들어온다. 다음 N줄에는 각각의 줄에 팬케이크 수 M, 과 팬케이크의 크기(1~M)이 섞인 순서로 +또는 -부호를 달고 한번씩 등장한다. (M ≤ 30)

출력

각각의 케이스에 대해 한 줄씩 출력한다. 뒤집는 횟수 K(≥0), 한 번에 뒤집어야 하는 케이크 더미의 수 K개를 공백으로 구분하여 출력한다. 하나의 케이스에 대해 여러 개의 답이 존재할 수 있다. (예로 든 문제에서 3 2 3 또한 답이 될 수 있다.)

예제 입력

3
3 +1 -3 -2
4 -3 +1 -2 -4
5 +1 +2 +3 +4 -5

예제 출력

6 2 1 3 1 2 1
6 4 1 4 3 1 2
3 5 1 5

힌트