Робот-конь
В стране коней живет робот-конь. У робота коня есть матрица размером n×m. В каждой ячейке матрицы записан вектор. На пересечении строки i и столбца j записан вектор (x_{i,j}, y_{i,j}) (1 ≤ i ≤ n, 1 ≤ j ≤ m).
Робот-конь решил прогуляться, для этого он составил себе программу, состоящую из k шагов. На шаге номер t (1 ≤ t ≤ k) робот-конь может подвинуться из своей текущей позиции на какой-то вектор из строки матрицы с номером ((t-1) mod n) + 1. Также на любом шаге можно никуда не двигаться, то есть остаться на месте.
Вам задана матрица, которая есть у робота-коня, и число k. На какое максимальное расстояние робот-конь сможет удалиться от своей начальной позиции? Найдите квадрат этого расстояния.
Входные данные
В первой строке записаны три целых числа n, m, k (1 ≤ n, m ≤ 10^5, 1 ≤ k ≤ 109, n ≤ m ≤ 10^5) — размеры матрицы и количество шагов робота-коня.
В каждой из следующих ^n строк записаны по 2·m целых чисел: в строке с номером i записаны числа x_{i,1}, y_{i,1}, x_{i,2},y_{i,2}, ..., x_{i,m}, y_{i,m} (|x_{i,j}|, |y_{i,j}| ≤ 10^9).
Выходные данные
Выведите единственное целое число — квадрат максимального расстояния, на которое сможет удалиться от своей начальной позиции робот-конь.