Sangbeom's Magic Pancake House

Time limit1sMemory limit128 MB

Summary

Given a stack of pancakes with sizes and burn orientations, find a sequence of at most 3M-2 prefix flips that sorts them by size with burned side down.

Level: Medium6 of 10
Topics: Greedy, Simulation, Sorting
Solved: No attempts yet

Problem

The cook at Sangbeom's Magic Pancake House sometimes falls asleep while making pancakes, so one side of a pancake may get burned. A pancake with the burned side facing up should not be served. Before serving, every pancake must have its burned side facing down, and the stack must be sorted by size: the smallest pancake on top and the largest pancake on the bottom.

Each pancake has a size and an orientation. In the input, +x means the pancake of size x has its burned side down, and -x means its burned side up.

One operation chooses the top k pancakes and flips them together. Their order is reversed, and every chosen pancake changes which side faces up.

For each test case, find a sequence of flips that transforms the initial stack into +1 +2 ... +M. The sequence may contain at most 3M - 2 flips.

Input

The first line contains the number of test cases T.

Each test case is given on one line. The first value is the number of pancakes M, followed by M pancakes listed from top to bottom. Each pancake is written as +x or -x, and the sizes 1 through M each appear exactly once. (M <= 30)

Output

For each test case, output one line. First output the number of flips K, then output the K flip sizes in the order they should be performed. A flip size is the number of top pancakes flipped in that operation.

There may be more than one valid answer, and K may be 0.

Examples1

Example 1

Input

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

Expected output

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