Робот-кінь
У країні коней живе робот-кінь. У робота коня є матриця розміром 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).
Вихідні дані
Виведіть єдине ціле число — квадрат максимальної відстаяні, на яку зможе віддалитись від своєї початкової позиції робот-кінь.