쥐덫

쥐덫은 한 명이 하는 간단한 카드 게임이다. 1부터 K까지 번호가 매겨진 카드를 섞어 뒷면이 보이게 쌓은 덱으로 진행한다. 덱의 맨 위 카드를 공개한 다음 덱의 맨 아래에 넣으며, 지금까지 공개한 카드 수를 센다. 공개한 카드의 번호가 현재 카운트와 일치하면 그 카드를 덱에서 제거하고 카운트를 초기화한다. 카운트가 K+1에 도달하는 일이 한 번이라도 생기면 패배한다. 덱의 카드가 모두 없어지면 승리한다.

5장의 카드가 2, 5, 3, 1, 4 순서로 놓인 덱이 있다고 하자. 카운트가 1일 때 2을 공개하고, 카운트가 2일 때 5을 공개한 다음, 카운트가 3일 때 3을 공개한다. 값이 카운트와 일치하므로 덱에서 3을 제거하고 카운트를 초기화한다. 이제 4장의 카드가 남아 있으며, 그 순서는 1, 4, 2, 5이다. 그런 다음 카운트가 1일 때 1을 공개하고, 이 카드도 제거한다(지금까지 아주 잘하고 있다!). 이와 같은 방식으로 계속하면 2, 이어서 4, 마지막으로 5을 제거하여 승리한다.

게임에서 승리하면서 카드를 오름차순으로 제거하도록 카드 덱을 구성하고 싶다. 이렇게 구성된 덱을 "완벽한" 덱이라고 부르겠다. 예를 들어, 카드가 4장이라면 덱을 1, 4, 2, 3 순서로 구성할 수 있으며, 카드를 1, 2, 3, 4 순서로 제거하여 승리한다.

제한

메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

시간 제한: 60초. T = 100, 1 ≤ K ≤ 5000, 1 ≤ n ≤ 100, 1 ≤ $d_{i}$ ≤ K.

큰 데이터 세트 (테스트 세트 2 - 비공개)

시간 제한: 180초. T = 10, 1 ≤ K ≤ 1000000, 1 ≤ n ≤ 100, 1 ≤ $d_{i}$ ≤ K.

입력의 첫 번째 줄에는 케이스의 수 T가 주어진다. 각 테스트 케이스는 덱의 카드 수 K가 주어진 한 줄로 시작한다. 다음 줄은 정수 n으로 시작하며, 그 뒤에 덱의 인덱스인 n개의 정수($d_{1}$,$d_{2}$, ...)가 주어진다.

각 테스트 케이스마다 "Case #x: "을 출력하고, 이어서 n개의 정수($k_{1}$,$k_{2}$, ...)를 출력한다. 여기서 $k_{i}$은 크기가 K인 완벽한 덱의 인덱스 $d_{i}$에 있는 카드의 값이다. 출력의 수들은 공백으로 구분해야 하며, 각 "Case #x:" 줄의 콜론 뒤에는 적어도 하나의 공백이 있어야 한다.