POLSKI SPOJ

Operowanie samą średnią, jakkolwiek przydatną w wielu zastosowaniach, nie zawsze pozwala osiągnąć interesujące rezultaty. Najprostszy przykład ograniczeń tej miary to rozkład zarobków, który mógłby wyglądać następująco: 1500, 1600, 1750, 1900, 2500, 3000, 12000. Zatem każdy pracownik zarabia przeciętnie około 3464. Jednak dla ilu z nich jest to wystarczająco dobre przybliżenie? Średnia okazuje się zbyt czuła na wartości skrajne. Postanawiasz zautomatyzować w następnej kolejności narzędzie bardziej odporne od średniej arytmetycznej - medianę. Jest to wartość środkowa uporządkowanego zbioru danych (zazwyczaj rosnącego) pozwalająca stwierdzić, że połowa obserwacji jest od niej mniejsza, a druga połowa większa. W przypadku powyższego szeregu zarobków będzie to wartość 1900, która znacznie lepiej oddaje stan zarobków. Zgłaszasz swój postulat kierownikowi. Nie jest zadowolony, prawdopodobnie dlatego, że łatwiej odrzucać prośby o podwyżkę zasłaniając się 'i tak już bardzo wysoką' średnią płac. Żeby Cię zniechęcić proponuje abyś zaadaptował bardziej rozbudowaną funkcję, typową dla większości pakietów statystycznych, znaną jako five-number summary, czyli innymi słowy zwracającą minimum, pierwszy kwartyl, medianę, trzeci kwartyl oraz maksimum dla badanego zbioru danych.

Wymienione miary musisz obliczyć stosując interpolację liniową, dzięki czemu można będzie łatwo uzyskać porównywalność opracowanych analiz z najpopularniejszymi pakietami statystycznymi. Metoda ta, dla zbioru V uporządkowanego niemalejąco, indeksowanego od zera wygląda następująco:

1. Obliczamy rangę dla poszukiwanego percentyla według wzoru: r = P/100*(N-1), gdzie P - percentyl, N - liczebność badanego zbioru.

2. Dzielimy rangę r na część całkowitą k i część ułamkową d.

3. Odpowiedzią jest wartość: Vk + (Vk+1 - Vk)*d, gdzie Vk, to k-ty element badanego zbioru.

Minimum można uznać za zerowy percentyl, maksimum za setny i tak dalej.

Wejście

W pierwszej linii wejścia pojawią się dwie liczby całkowite t i n oznaczające kolejno ilość testów oraz całkowitą liczbę obserwacji. W kolejnej linii n liczb całkowitych c. W następnych t liniach trójka liczb całkowitych: s, e, k. Oznaczają one pierwszy element tworzonej próbki (indeksowany od zera), ostatni element oraz co który element pobieramy tworząc próbkę. Pierwszy element włączamy do próbki, ale końcowego już nie. Próbka zawsze będzie składała się przynajmniej z jednego elementu.

Wyjście

Na wyjściu należy podać dla każdego testu kolejno pięć miar rozdzielonych spacjami, z dokładnością do drugiego miejsca po przecinku: minimum, pierwszy kwartyl, medianę, trzeci kwartyl, maksimum.

Ograniczenia

0 < t <= 20000

0 < n <= 100000

-214783648 <= c <= 214783647

0 <= s < e <= n

0 < k < 10000

Przykład

Wejście:
3 11
4 7 12 1 7 2 8 5 9 8 6
3 10 2
0 11 1
2 4 3

Wyjście:
1.00 1.75 3.50 5.75 8.00
1.00 4.50 7.00 8.00 12.00
12.00 12.00 12.00 12.00 12.00

Komentarz

W pierwszym teście próbkę tworzą liczby 1,2,5,8; w drugim wszystkie, w trzecim tylko 12.