Opis

Nierzadko naukowcy są oddani swoim badaniom i bardzo nie lubią zajmować się rzeczami mało ważnymi dla dobra ludzkości, aczkolwiek koniecznymi do funkcjonowania w społeczeństwie. Tak właśnie jest w przypadku prof. Atomusa Kwantopolisa (emigrant z Grecji), genialnego naukowca, który prowadzi zaawansowane badania nad zakrzywieniem czasoprzestrzeni. Otóż po miesiącach zalegania z opłatami za prąd, elektrownia zagroziła jego wyłączeniem, co uniemożliwiłoby profesorowi pracę. Dlatego, mimo ogromnej niechęci do odrywania się od swoich badań, prof. Kwantopolis musi na chwilę pójść do banku.

Z oczywistych względów profesor chce załatwić sprawę najszybciej jak się tylko da. Wszystkie banki, do których może iść są równoodległe od jego laboratorium i podróż do każdego z nich trwa tyle samo czasu. Zatem jedynym elementem rozróżniającym banki jest czas spędzany w kolejce (zakładamy, że w każdym banku jest jedna kolejka do jedynego okienka i wszystkie osoby są obsługiwane w tym samym tempie). Skąd jednak prof. Kwantopolis ma wiedzieć, w którym z banków będzie stać najkrócej? Otóż może wykorzystać do tego wehikuł czasu, który ostatnio skonstruował. Dzięki niemu będzie w stanie zrobić rekonesans bez straty czasu. Profesor uruchamia więc swój wehikuł i idzie do jednego z banków by zobaczyć jaka długa jest w nim kolejka. Następnie wraca do laboratorium, wchodzi do wehikułu i wcisnąwszy jeden guziczek przenosi się w czasie do momentu, w którym włączył maszynę. Idzie do kolejnego banku (w tym samym tempie), patrzy ile osób czeka tam w kolejce, wraca do laboratorium i ponownie cofa się w czasie. Czynność powtarza dla wszystkich banków. Zebrawszy dane o kolejkach może wyłączyć wehikuł i wybrać się, już w celu zapłacenia rachunku za prąd, do banku, w którym będzie najkrócej czekać. Należy założyć, że będzie iść tym samym tempem, więc w momencie wejścia do banku zastanie identyczną sytuację, jak podczas rekonesansu. Ponadto tak się przypadkiem złożyło, że w momencie wejścia do któregokolwiek banku żadna osoba nie była w trakcie obsługiwania i pierwsza z kolejki właśnie zaczynała podchodzić do okienka (chyba, że kolejka jest pusta — wtedy prof. Kwantopolis może podejść od razu do okienka).

Zadanie

Dane są długości kolejek w każdym z banków, w momencie, gdy prof. Atomus Kwantopolis mógłby wejść do któregoś z nich. Dana jest również informacja o tym ile osób jest obsługiwanych w ciągu godziny, we wszystkich bankach. Należy podać, w którym banku profesor zostanie obsłużony najszybciej i ile pełnych godzin minie nim opuści bank, licząc od momentu wejścia.

Specyfikacja wejścia

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 50), oznaczającą liczbę zestawów danych. Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite N i C (1 ≤ N ≤ 100, 1 ≤ C ≤ 60 oraz 60 dzieli się bez reszty przez C). Liczby te oznaczają odpowiednio liczbę banków oraz liczbę osób obsługiwanych w ciągu godziny w którymkolwiek z nich. W drugiej linii zestawu znajduje się N liczb całkowitych z zakresu od 0 do 1000, będących długościami kolejek w bankach podanymi w kolejności odwiedzania przez profesora.

Specyfikacja wyjścia

Dla każdego zestawu danych na wyjściu należy wypisać, w osobnej linii, dwie liczby całkowite. Pierwsza z nich to „numer” banku, w którym prof. Kwantopolis czekać będzie najkrócej (gdzie banki numerowane są od 1, w kolejności odwiedzania przez profesora podczas rekonesansu). W przypadku kilku takich banków należy podać ten z najmniejszym numerem. Druga liczba mówi ile pełnych godzin profesor spędzi w tym banku. (Uwaga! Wyboru banku należy dokonać według dokładnego czasu stania w kolejce, a nie liczby pełnych godzin.)

Przykład

4
1 6
11
2 3
10 6
3 60
17 29 13
4 1
5 4 6 4

1 2
2 2
3 0
2 5