410533: GYM104036 3 Антон и арбузы
Description
На лето родители отправили Антона к бабушке помогать ей выращивать в огороде арбузы. Чтобы они выросли большими и вкусными, требуется поливать растения каждый день, что и было поручено мальчику. Если арбуз был полит, он вырастает на один килограмм (а если не был, то остаётся прежнего размера) за каждый день.
Сам огород представляет собой прямоугольную сетку из $$$n$$$ строк и $$$m$$$ столбцов, в каждой ячейке которой растёт арбуз, изначально имеющий массу 0 килограмм. Антон очень не любит работать, поэтому в $$$i$$$-й день из всех $$$d$$$, что он будет гостить у бабушки, планирует поливать только арбузы, лежащие на пересечении первых $$$x_i$$$ строк и первых $$$y_i$$$ столбцов.
В конце лета за свою работу мальчик получит самый большой арбуз из имеющихся в огороде (а если их несколько, то сразу все самые большие!). Антон очень любит гигантские арбузы, поэтому просит вас определить, сколько же их в итоге ему достанется, и какого они будут веса.
Входные данныеПервые три строки входных данных содержат целые числа $$$n$$$, $$$m$$$ и $$$d$$$ именно в таком порядке — количество строк и столбцов в огороде и время пребывания Антона у бабушки $$$(1 \leqslant n, m \leqslant 10^9$$$, $$$1 \leqslant d \leqslant 10^5)$$$. Далее идут $$$2d$$$ чисел $$$x_i$$$ и $$$y_i$$$, каждое в отдельной строке, обозначающих количество строк и столбцов, арбузы в которых были политы мальчиком в день номер $$$i$$$ $$$(1 \leqslant x_i \leqslant n, 1 \leqslant y_i \leqslant m)$$$. Уточним, что эти данные упорядочены по дням, т.е. сначала идёт пара чисел $$$x_1$$$, $$$y_1$$$, именно в таком порядке, затем $$$x_2$$$, $$$y_2$$$ и так далее.
Отметим отдельно, что бабушка пронумеровала все строки и столбцы в огороде, и Антон всегда поливает именно $$$x_i$$$ первых строк и $$$y_i$$$ первых столбцов.
$$$\textbf{Обратите внимание}$$$, что при заданных ограничениях для хранения ответов необходимо использовать $$$64$$$-битный тип данных, например $$$\textbf{long}$$$ $$$\textbf{long}$$$ в $$$\textbf{C++}$$$, $$$\textbf{int64}$$$ в $$$\textbf{Free}$$$ $$$\textbf{Pascal}$$$, $$$\textbf{long}$$$ в $$$\textbf{Java}$$$.
Выходные данныеВыведите два числа через пробел — количество арбузов, которые достанутся Антону, и вес каждого из них.
Система оценкиРешения, правильно работающие, когда произведение чисел $$$n$$$, $$$m$$$ и $$$d$$$ не превосходит $$$10^6$$$, будут оцениваться в 50 баллов.
ПримерыВходные данные3 3 1 2 2Выходные данные
4 1Входные данные
4 3 2 3 1 1 2Выходные данные
1 2Примечание
В первом примере Антон один раз поливает квадрат $$$2 \times 2$$$, поэтому ему достанется 4 арбуза массой 1 килограмм каждый.
Во втором примере будут политы 3 арбуза в первом столбце и 2 арбуза в первой строке. Тогда ровно один арбуз окажется полит дважды, его Антон и получит.