Возможно, вы слышали про следующую игру в серии Лара Крофт, которая выходит в этом году. Возможно, вы даже смотрели ее трейлер. Однако вы совершенно точно упустили главную ветку ее сюжета, так что давайте я вам приоткрою завесу тайны.
Лара собирается исследовать еще одно страшно опасное подземелье. Разработчики решили в этот раз сделать 2D графику. Подземелье можно представить, как прямоугольную матрицу из n строк и m столбцов. Ячейка (x, y) — это ячейка в x-й строке и y-м столбце. Лара может передвигаться между соседними по стороне ячейками во всех четырех направлениях.
Более того, она уже даже выбрала себе путь, чтобы обойти все ловушки. Она заходит в подземелье в ячейке (1, 1) — это левый верхний угол матрицы. Далее она спускается до конца вниз до ячейки (n, 1) — левый нижний угол. Потом она двигается змейкой — до конца вправо, на один вверх, влево до 2-го столбца, на один вверх, и так далее. Лара продолжает идти, пока не закончатся непосещенные клетки. n и m заданы такими, что она всегда закончит в клетке (1, 2).
Лара уже k раз перешла в соседнюю клетку. Можете ли вы определить ее текущую позицию?
В единственной строке записаны три целых числа n, m и k (2 ≤ n, m ≤ 109, n всегда четно, 0 ≤ k < n·m). Обратите внимание, что k не помещается в 32-битный тип данных.
Выведите ячейку (номер строки и столбца, в которых находится эта ячейка), в которой Лара окажется после того, как k раз перейдёт в соседнюю клетку.
4 3 0
1 1
4 3 11
1 2
4 3 7
3 2
Такой ее путь будет на матрице 4 на 3:
