치킨 TOP N

인하대 주변 치킨집의 맛을 수치로 재는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집을 맛 점수가 감소하지 않는 순서로 정렬하려고 한다. 치킨집이 너무 많아 혼자 하기에는 시간이 오래 걸려서 동아리 회원을 동원하기로 했다.

치킨집이 $N$개 있고, 점수를 아무 순서로나 한 줄에 늘어놓았다고 하자. 첫 단계에서는 회원 $N/2$명이 왼쪽부터 차례대로 치킨집을 2개씩 맡아 각자 정렬한다. 다음 단계에서는 회원 $N/4$명이 바로 앞 단계에서 만들어진 정렬된 그룹을 왼쪽부터 2개씩 맡아 하나로 합친다. 이어서 $N/8$명, $N/16$명이 같은 방식으로 진행하고, 마지막 한 명이 정렬된 그룹 두 개를 합치면 작업이 끝난다.

점수가 1, 5, 2, 4, 2, 9, 7, 3인 치킨집 8곳을 예로 들자. 회원 4명이 (1, 5), (2, 4), (2, 9), (7, 3)을 각각 정렬하면 줄은 (1, 5), (2, 4), (2, 9), (3, 7)이 된다. 이어서 회원 2명이 ((1, 5), (2, 4))와 ((2, 9), (3, 7))을 각각 합치면 (1, 2, 4, 5), (2, 3, 7, 9)가 되고, 마지막 회원 1명이 두 그룹을 합쳐 (1, 2, 2, 3, 4, 5, 7, 9)를 만든다.

작업 중간 상태가 궁금해진 민호는 회원 $k$명이 맡은 단계가 끝난 직후의 줄을 보고 싶다. 그 줄을 출력하라.

첫째 줄에 치킨집의 개수 $N$이 주어진다. $N$은 2의 거듭제곱이고 $4 \le N \le 2^{20}$이다.

둘째 줄에 치킨집 $N$곳의 맛 점수가 왼쪽부터 순서대로 공백으로 구분되어 주어진다. 각 점수는 0 이상 1,000,000,000 이하의 정수이다.

셋째 줄에 지금 단계를 맡은 회원 수 $k$가 주어진다. $k$도 2의 거듭제곱이고 $1 \le k < N$이다.

회원 $k$명이 맡은 단계가 끝난 직후의 점수 $N$개를 왼쪽부터 순서대로 한 줄에 공백으로 구분해 출력한다.

이 단계에서 회원 한 명은 길이 $N/(2k)$인 정렬된 그룹 두 개를 합쳐 길이 $N/k$인 그룹 하나를 만든다.