Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWPZ06C - Autobus

W mieście, w którym mieszkają sami naukowcy, burmistrz ma pewien problem. Otrzymał wyniki badań, z których wynika, że naukowcy podczas porannej jazdy autobusem do pracy nie rozmawiają między sobą. Nie jest to wcale spowodowane tym, że się nawzajem nie lubią, bo wręcz przeciwnie, są oni bardzo przyjaźni i często się śmieją. Wynika to z tego, że każdy z nich jadąc rano do pracy obmyśla nowe odkrycia i z nikim nie chce w tym czasie rozmawiać, żeby się nie dekoncentrować. Burmistrz, który oczywiście też jest naukowcem, rozpoczął badania (naukowe naturalnie), aby określić przyczynę takiego stanu rzeczy oraz nakłonić naukowców do tego, żeby więcej ze sobą rozmawiali jeżdżąc rano do pracy. Na razie udało się ustalić tyle, że konstrukcje autobusów „sprzyjają” takiemu zachowaniu naukowców. Wyglądają one w ten sposób, że miejsca siedzące są ustawione w pojedynczym rzędzie, jedno obok drugiego, bez odstępów, ponumerowane kolejnymi liczbami naturalnymi. Ze względu na wąskie drzwi w autobusie, które znajdują się przy siedzeniu numer 1, pasażerowie wsiadają pojedynczo. Okazało się, że naukowcy wchodząc do autobusu siadają według następujących zasad:

  • jeżeli wszystkie miejsca są wolne naukowiec wybiera dowolne miejsce
  • w przeciwnym wypadku wybierane jest miejsce, którego odległość do najbliższego zajętego miejsca jest jak największa
  • jeżeli miejsc, na których może usiąść naukowiec (zgodnie z poprzednim punktem) jest więcej to wybiera on takie, które jest najbliżej wejścia (tj. z najmniejszym numerkiem)
  • naukowcy nie zwracają uwagi na fakt istnienia kierowcy w autobusie

Wiadomo, że pasażerowie wchodzą do autobusu tak długo, aż wszystkie miejsca siedzące będą zajęte. Jeśli nie ma wolnych miejsc, żaden naukowiec nie wchodzi więcej do autobusu. Badania prowadzone przez burmistrza są już na ukończeniu.

Do autobusu o pewnej liczbie miejsc siedzących wsiadają naukowcy. Wiemy na którym miejscu siada pierwszy z nich. Twoim zadaniem jest określenie, na jakich miejscach usiądą wybrani do badań burmistrza naukowcy.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 500) oznaczającą liczbę zestawów danych. Pierwsza linia zestawu składa się z dwóch liczb całkowitych N oraz M (1 ≤ M ≤ N ≤ 2*104), oddzielonych spacją, oznaczających odpowiednio liczbę miejsc siedzących w autobusie oraz liczbę naukowców do niego wsiadających. W kolejnej linii zestawu znajduje się liczba całkowita X (1 ≤ X ≤ N) oznaczająca numer miejsca zajętego przez pierwszego pasażera. Następna linia zestawu zawiera liczbę całkowitą Y (0 ≤ Y ≤ M), która oznacza liczbę naukowców objętych badaniem. Ostatnia linia zawiera Y różnych liczb oznaczających pasażerów objętych badaniem, z których każdy oznaczony jest numerem w kolejności wchodzenia do autobusu. Linia ta jest ciągiem posortowanym ściśle rosnąco.

Wyjście

Dla każdego zestawu danych należy wypisać w osobnej linii kolejne numery miejsc zajmowanych przez kolejnych badanych naukowców.

Przykład

Wejście:

2
3 2
1
2
1 2
5 5
5
3
1 3 5

Wyjście:

1 3
5 3 4


Dodane przez:Rafal Nowak
Data dodania:2006-12-07
Limit czasu wykonania programu:1s-4s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Mistrzostwa Wielkopolski w Programowaniu Zespo³owym, 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.