3780 - 팔씨름 토너먼트

Time Limit: 3s Memory Limit: 128MB

Submissions: 38 Solved: 15

Description

소식 들으셨나요? WithCS 농장의 콧수염 총각이 팔씨름 대회에서 우승했다고 합니다. 대회는 토너먼트 방식으로 2^N명의 사람이 출전했으며, 1번부터 2^N번까지 출전번호가 부여되었습니다. 첫번째 선수(C1)은 두번째 선수(C2)와 경기를 하고, 세번째 선수(C3)은 네번째 선수(C4)와 경기를 합니다. 두 경기의 승자가 다시 경기를 하는 방식으로 진행됩니다. (아래 그림을 참고하세요)

각각의 선수는 P_i만큼의 체력을 가지고 시작합니다. 두 명의 선수가 맞붙었을 때 더 많은 체력을 가지고 있는 사람이 이깁니다. 만약 두 선수의 체력이 같다면 출전번호가 더 작은 사람이 이깁니다. 이긴 선수는 본인의 체력에서 상대방의 체력을 뺀 만큼의 체력을 가지게 됩니다. 다음 라운드로 넘어갈 때에 K만큼의 다시 채워지게 됩니다. 단, 회복될 때 본인이 처음 가지고 있던 기본 체력인 P_i이상을 가질 수는 없습니다.

T개의 토너먼트가 주어졌을 때, 우승자와 우승자가 꺾은 상대를 알려주세요.

Input

* Line 1 : 단일 정수 T (토너먼트의 수, 최대 100)

* Line 2 ~ (T*2)+1 : 토너먼트 별 설정 값

* Line even : 2개의 정수, N K

- N : 선수 수의 log(2) 값, 우승에 필요한 match 수 ( 1 ≤ N ≤ 15 )

- K : 경기 후 회복되는 체력량 ( 0 ≤ K ≤ 1,000 )

* Line odd : 2^N개의 정수

- P_i : 선수 별 초기 체력 (0 ≤ P_i ≤ 1,000)

Output

각각의 토너먼트에 대해 2줄의 결과 값을 출력.

* Line odd : 우승 선수 번호

* Line even : 우승 선수가 꺾은 선수 번호를 순서대로 출력

Sample Input

3
3 0
100 90 79 37 60 50 39 95
2 10
50 50 60 60
2 10
3 5 60 59

Sample Output

Source

Regionals 2010, Asia - Jakarta