18343번 - 신탁 서브태스크

신탁이란 신이 자신의 의지를 순례자에게 전달하려는 것이고, 그렇기에 신탁을 이해하는 것은 순례자들의 기본 소양이다.

신탁을 이루는 문자는 1에서 88888888 사이에 있는 88888888가지 정수다. 즉, 123도 하나의 문자가 되고, 88888888도 하나의 문자가 된다. 하나의 문자는 하나의 뜻을 가지고 있다.

신탁은 홀수개 문자의 나열이다. 신탁을 해석하는 방법은 신탁에 변환을 거듭해서 단 하나의 문자만 남기는 것이고, 남겨진 문자가 신탁의 뜻이 된다. 신탁을 변환하는 순서에 따라 마지막에 남는 문자의 종류가 달라질 수 있기 때문에, 신탁은 여러 뜻을 가질 수 있다.

신탁을 변환하는 법은 다음과 같다.

1. 연속된 홀수개의 문자를 선택하고 신탁에서 지운다.
2. 선택된 문자들을 그 문자를 나타내는 정수를 감소하지 않는 순으로 정렬했을 때 가장 가운데에 오는 문자를 구한다.
3. 1번 단계에서 문자들이 지워진 위치에 2번 단계에서 구한 문자를 다시 집어넣는다.

예를 들어, [3,3,1,1,2,1,1]이라는 신탁이 있다고 하자. 이 신탁을 읽는 예를 들어 보면,

• [3,3,1,1,2,1,1] $\rightarrow$ [1]
• [3,3,1,1,2,1,1] $\rightarrow$ [3,3,1] $\rightarrow$ [3]

등이 방법이 있다. 그리고 놀랍게도 이 신탁을 2로 해석하는 방법은 존재하지 않는다. 그래서, [3,3,1,1,2,1,1]라는 신탁은 1 또는 3으로 해석될 수 있다. 주어진 신탁이 어떤 뜻으로 해석될 수 있는지 모두 구하여라.

첫 번째 줄에, 신탁의 개수를 나타내는 자연수 $T$가 주어진다.

그다음 줄부터 각 신탁마다 두 개의 줄이 입력으로 주어진다:

첫 번째 줄에, 신탁의 길이를 나타내는 자연수 $N$이 주어진다.

두 번째 줄에, 신탁의 구성을 나타내는 $N$ 개의 정수 $c_1, c_2, \cdots, c_N$ ($1\leq c_i \leq 88\ 888\ 888$)가 주어진다.

$T$ 개의 신탁 각각에 대해 두 개의 줄을 출력한다:

주어진 신탁이 $K$ 종류의 문자로 해석될 수 있다면, 첫 번째 줄에 $K$를 출력한다.

해석 결과로 가능한 서로 다른 $K$ 개의 문자를 정수의 오름차순으로 $C_1, C_2, \cdots, C_K$라고 할 때, 두 번째 줄에 $C_1, C_2, \cdots, C_K$를 공백으로 구분하여 출력한다.

• $1 \leq \sum N \leq 30$

• $1 \leq \sum N \leq 3\ 000$

• $1 \leq \sum N \leq 300\ 000$