Robot horse#4654
In the land of horses, there lives a robot-horse. The robot-horse has a matrix of size n \times m. Each cell of the matrix contains a vector: at the intersection of row and column is the vector (x_{i,j}, y_{i,j}) (1 \leq i \leq n, 1 \leq j \leq m).
The robot-horse decided to take a walk and prepared a program for steps. On step (1 \leq t \leq k), the robot-horse may move from its current position by choosing any vector from the matrix row numbered ((t - 1) \bmod n) + 1. It is also allowed to stay in place on any step.
You are given the matrix used by the robot-horse and the number . What is the maximum distance the robot-horse can travel from its starting position? Find the square of this maximum distance.
The first line contains three integers , , (1 \leq n, m \leq 10^5, 1 \leq k \leq 10^9, n \leq m \leq 10^5) — the size of the matrix and the number of steps.
Each of the next lines contains 2 \cdot m integers: the -th line contains 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).
Print a single integer — the square of the maximum distance the robot-horse can travel from its starting position.
Example 1