32968번 - 하노이의 큐 서브태스크스페셜 저지

문제

하노이의 탑은 1883년 프랑스의 수학자 에두아르드 뤼카가 처음으로 발표한 게임으로, 3개의 기둥과 여러 개의 원반을 가지고 하는 게임입니다. 이 문제는 하노이의 탑과 비슷하게 3개의 큐(Queue)와 $N$개의 정수가 주어집니다.

세 개의 큐 $A,ドル $B,ドル $C$가 있습니다. 처음에 큐 $A$에는 앞에서부터 $N$개의 정수 $a_1, a_2, \dots, a_N$가 들어 있으며, 나머지 두 개의 큐는 비어 있습니다. 여러분은 아래 작업을 0ドル$번 이상 반복할 수 있습니다.

• 서로 다른 두 큐 $X$와 $Y$를 선택합니다. $X$는 비어 있지 않아야 합니다.
• 큐 $X$의 맨 앞에 있는 원소를 큐 $Y$의 맨 뒤로 옮깁니다.

큐 $A$의 원소 $a_1, a_2, \dots, a_N$가 주어질 때, 여러분은 최대 $L$번 작업을 반복한 후에 아래 조건이 성립하도록 하는 방법을 찾아야 합니다.

• 세 개의 큐 중 두 개는 비어 있으며, 나머지 하나의 큐 $X$에는 $N$개의 정수가 들어 있어야 합니다.
• $X$의 원소를 앞에서부터 순서대로 나열했을 때, 값이 더 작은 원소는 반드시 값이 더 큰 원소보다 앞에 옵니다.

문제의 조건에 따라 그러한 방법이 언제나 존재함을 증명할 수 있습니다.

입력

각 입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에 테스트 케이스의 개수 $T$가 주어집니다.

그다음 줄부터 총 $T$개의 테스트 케이스가 2ドルT$개의 줄에 걸쳐 주어집니다.

각 테스트 케이스는 아래와 같이 두 줄로 구성됩니다.

• 첫 번째 줄에 큐 $A$의 원소의 개수 $N$과 작업의 최대 횟수 $L$이 공백으로 구분되어 주어집니다.
• 두 번째 줄에 큐 $A$의 원소 $a_1, a_2, \dots, a_N$이 공백으로 구분되어 주어집니다.

출력

각 테스트 케이스마다 아래와 같이 최대 두 개의 줄을 출력합니다.

• 첫 번째 줄에 사용한 연산의 횟수 $k$를 출력합니다. $(0 \le k \le L)$
• 두 번째 줄에 각 작업에 대응되는 문자열 $k$개를 공백으로 구분하여 출력합니다. 각 문자열은 작업에서 선택한 서로 다른 두 큐 $X$와 $Y$의 이름을 공백 없이 붙인 것과 같습니다. 예를 들어 큐 $X$를 $A$로, 큐 $Y$를 $B$로 선택했다면 출력할 문자열은 'AB'입니다.

단, $k = 0$이라면 두 번째 줄을 출력하지 않아도 됩니다.

$k$는 반드시 $L$ 이하여야 하지만 $k$를 최소화할 필요는 없습니다.

제한

• 1ドル \le T \le 1,円 000$
• 2ドル \le N \le 32,円 768$
• $N$은 2ドル$의 거듭제곱입니다.
• 모든 테스트 케이스에서 $N$의 합은 50ドル,円 000$ 이하입니다.
• $L \le N^2$
• 1ドル \le a_i \le N$

서브태스크

힌트