<PREV Problem:
NEXT>
Solved by 46 users: vi002, JohnJones_001, KZ, fetetriste, tourist, Alexander_Afanasiev, WsemirZ, zloy_mipt, DAV, mage, soseux, dan, Chmeli_BSU, Jacob, Mishunin_Alexander, mazahaka, Agarb, UdH-WiNGeR, RAVEman, defrager, knightry, topspin, sasha_s, LiuChenheng, Philip_PV, chumbalov, Kuznetsov_S, abortmozga.ru, mikhail4021, Dest, ignat, ilnurKh, Losik, JustFun, ripatti, kornakovBSU, stupid_coder, Darii, vitar, NIGHTFIT, mikelan, mathematic, Nevermore, Robert_Gerbicz, murphy, LOD.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Прогноз погоды

Time limit = 2 second(s)

Memory limit = 64 Mb

Физкультурник, в принципе, добрый малый. Но у него свои корыстные цели. Спортивный корпус закупил свою собственную метеостанцию, и физкультурник хочет, чтобы Вы помогли ему наладить прогноз температуры на завтра и выводить онлайновую информацию на сайте спортивного корпуса МФТИ.

Для предсказания температуры метеостанция ежесекундно снимает значение температуры. Температура на датчике измеряется в некоторых условных единицах, так что значение температуры является всегда целым числом и лежит в диапазоне [-20000000, 20000000].

Но этих данных слишком много, чтобы передавать их прогнозирующему алгоритму. Необходимо осуществить "уменьшение размерности" входных данных.

Для этого нужно написать программу, которая считывет числа и периодически, через каждые M чисел, для последних N чисел, выдавала бы значение минимального и максимального числа, а также значение медианы, то есть числа, которое стояло бы в ячейке с индексом ⌊(N-1)/2 ⌋ (индексы начинаются с нуля), если N чисел упорядочить в массиве по возрастанию.

Input Первая строка входа содержит числа N и M. 1 ≤ N, M ≤ 200000.

Затем идут целые числа a0, a1, a2, … из диапазона [-20000000, 20000000], разделённые произвольным количеством пробельных символов. Их число заранее неизвестно, но оно не превосходит 200000. Их необходимо считывать до конца входа.

Output Выход должен содержать несколько строчек, в каждой из которых указано три целых числа : минимальное, медиана и максимальное из некоторого диапазона входных чисел. Строке с номером K (K = 0, 1, 2, …) соответствует диапазон из N чисел: aK⋅ M, aK⋅ M+1, …, aK⋅ M+N-1.

Последовательность {ai} не обязательно обрывается на элементе с индексом вида aK⋅ M+N-1 для некоторого K. В этом случае для последних чисел статистики не выводятся. Могут быть разные случаи: N < M, N > M, N = M.

Input#1
5 3
1 2 3 4 5 6 7
8 9 10 11 
Output#1
1 3 5
4 6 8
7 9 11
Input#2
4 1
10 1 9 2 8 3 7 4 6 5 
Output#2
1 2 10
1 2 9
2 3 9
2 3 8
3 4 8
3 4 7
4 5 7

Author:
Ворожцов Артем, индивидуальное первенство МФТИ по программированию, 21 сентября 2008 года
20 сентября 2008

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.161.108.158