Робот-кінь#4654
У країні коней живе робот-кінь. У робот-коня є матриця розміром n \times m. У кожній клітинці матриці міститься вектор: на перетині -го рядка та -го стовпця знаходиться вектор (x_{i,j}, y_{i,j}) (1 \leq i \leq n, 1 \leq j \leq m).
Робот-кінь вирішив прогулятися та підготував програму на кроків. На кроці (1 \leq t \leq k) робот-кінь може пересунутися зі своєї поточної позиції, вибравши будь-який вектор із рядка матриці з номером ((t-1) \bmod n) + 1. Також на кожному кроці дозволяється залишитися на місці.
Вам задано матрицю, яку використовує робот-кінь, а також число . Яку найбільшу відстань від початкової точки може подолати робот-кінь? Знайдіть квадрат цієї максимальної відстані.
У першому рядку міститься три цілі числа , , (1 \leq n, m \leq 10^5, 1 \leq k \leq 10^9, n \leq m \leq 10^5) — розміри матриці та кількість кроків.
Кожен із наступних рядків містить 2 \cdot m цілих чисел: -й рядок містить x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}, , x_{i,m}, y_{i,m} (|x_{i,j}|, |y_{i,j}| \leq 10^9).
Виведіть одне ціле число — квадрат максимальної відстані, яку може подолати робот-кінь від початкової точки.
Приклад 1