STL с объектами пользовательских типов, перегрузка операций 1

На с++. В магазинах сети «Закоулок» кассовая зона, состоящая из n касс, устроена следующим образом. Все кассы занумерованы целыми числами от 1 до n. Все покупатели, завершившие выбор товаров, выстраиваются в единую очередь. Как только освобождается какая-то касса, очередной покупатель отправляется к ней оплачивать свои приобретения. Если одновременно свободны две или более касс, покупатель всегда отправляется к кассе с меньшим номером. Если два покупателя пришли занимать очередь в кассовую зону одновременно, первым в очередь встанет покупатель с меньшим номером. Считайте, что покупатель перемещается к любой кассе мгновенно.

Конечно, если покупателей нет, какие-то (или даже все) кассы могут простаивать. Владельцы сети магазинов хотят проанализировать загрузку касс. Пока они просто хотят выяснить для каждой кассы два показателя: сколько покупателей касса обслужила и сколько времени она простаивала. Ваша задача — определить это.

Наблюдение за кассами начинается в момент времени 0, все кассы в этот момент считаются свободными. Моментом окончания работы касс считается момент завершения обслуживания последнего покупателя.

Входные данные

В первой строке содержатся целые числа n и m (1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000) — количество касс и количество покупателей соответственно.

В каждой из следующих m строк содержится по два целых числа tj и sj (1 ≤ tj ≤ 109, 1 ≤ s ≤ 106, j = 1, 2, ..., m) — момент времени, в который покупатель встал в очередь, и время, которое требуется на оплату его покупок (время, которое он проведёт на кассе).

Выходные данные

Выведите n строк. В строке #k содержится (через пробел) по два целых числа pk и dk — количество покупателей, которое обслужила касса #k, и количество времени, которое эта касса простаивала.

+комментарии