#2157 엘리베이터

1 s   128 MB  

Description

엘리베이터가 있다. 엘리베이터는 N개의 버튼을 가지고 있다. 즉 건물의 층수만큼 버튼이 있다.
 
엘리베이터에는 M명의 사람이 타고 있다. 엘리베이터에 탄 사람들은 각자 버튼 한 개를 누른다.
 
(똑같은 버튼을 눌러도 누른 버튼은 취소되지 않으며, 현재 엘리베이터가 위치한 층의 버튼도 누를 수 있다고 가정한다.)
 
엘리베이터는 처음에 P층에 위치해 있으며, 사람들이 누른 층들인 F1, F2, … , FM을 최단 거리로 이동한다.
 
엘리베이터가 멈추면 그 층에서 내려야 할 사람들은 모두 내린다.
 
 
 
엘리베이터에 타는 사람 수, 누른 버튼, 현재 엘리베이터의 위치가 주어질 때, 엘리베이터가 멈추는 층수를 차례대로 출력하는 프로그램을 작성하여라.
 
만약 최단 경로가 두 가지 이상 있다면 경로를 오름차순으로 정렬했을 때 가장 앞에 오는 경로를 출력한다.
 
단, 엘리베이터가 움직이는 도중에 내려야 할 사람이 있는 층을 만나는 경우 무조건 멈춘다.

Input

첫 줄에 테스트 케이스의 수 T가 주어진다.
 
각 테스트 케이스의 첫 번째 줄에는 사람의 수 M(1 <= M <= 200) 이 주어진다.
 
두 번째 줄에 버튼을 누른 층수 F1, F2, … , FM(1 <= F1, F2, ..., FM <= 200) 가 입력되고, 세 번째 줄에는 엘리베이터가 현재 위치한 층 P(1 <= P <= 200)가 입력된다.

Output

각 테스트 케이스 마다 엘리베이터의 이동 경로를 순서대로 공백으로 구분 하여 한 줄에 출력한다.

Sample Input

Sample Output

3
5
1 3 5 7 9
4
4
3 6 9 1
10
5
3 5 7 5 3
1
3 1 5 7 9
9 6 3 1
3 5 7

Source

2013 Ajou Programming Contest