Плащ для Абсолема
시간 제한2초메모리 제한1024 MB
직사각형 격자의 각 노드를 대각선 x-y=d로 분류해 d mod K로 색을 정하고, 가장 많은 색과 가장 적은 색을 찾는다.
문제
Абсолему ещё далеко до превращения в бабочку, и он вкушает все прелести молодой жизни. К сожалению, во время мероприятия, связанного с неудачным выступлением на соревнованиях по программированию, Абсолем несколько потерял связь с реальностью и где-то забыл свой любимый плащ. Алиса предложила сшить опечаленному Абсолему такой же плащ, и тот на радостях поведал Алисе тайну волшебного узора.
Плащ представляет из себя прямоугольник N ×M с внутренней сеткой, узлы которой покрашены в K цветов особым образом:
- Плащ размещается так, чтобы два его противоположных угла лежали в точках с координатами (0, 0) и (N, M).
- Рассматриваются все прямые с угловым коэффициентом 1 (лежащие под углом 45◦ к оси абсцисс и направленные вверх и вправо), которые проходят хотя бы через один узел плаща. Эти прямые упорядочиваются слева направо (по тому, какая из них раньше (левее) пересекает ось абсцисс); самая левая прямая имеет номер ноль, а самая правая — N + M.
Плащ размером 7 × 4.
Точки, лежащие на i-й прямой, красятся в цвет номер (i mod K)+1, то есть один плюс остаток от целочисленного деления i на K.
Плащ размером 7 × 4, покрашенный в три цвета (цвет 1 — красный, цвет 2 — зелёный, цвет 3 — синий).
Шляпник, подслушав тайну узора плаща Абсолема, задумался, узлов какого цвета на плаще больше всего, а какого меньше всего. Помогите ему выяснить это!
출력
В единственной строке содержатся три целых числа N, M и K — размеры плаща и количество цветов соответственно (1 ⩽ N, M ⩽ 109, 1 ⩽ K ⩽ N + M + 1).
제한
В первой строке выведите два числа: номер цвета, в который будет покрашено наибольшее число узлов на плаще, и количество узлов, покрашенных в этот цвет.
Во второй строке выведите два числа: номер цвета, в который будет покрашено наименьшее число узлов на плаще, и количество узлов, покрашенных в этот цвет.
Если правильных ответов несколько, выведите любой из них.
힌트
Плащ из первого примера изображён на рисунке из условия.
Во втором примере в каждый из двух цветов покрашено одинаковое число узлов плаща.
Плащ размером 2 × 3, покрашенный в два цвета.