Robot-at#4654
Atlar diyarında bir robot-at yaşayır. Robot-atın ölçüsü n \times m olan bir matrisi var. Matrisin hər bir hüceyrəsində bir vektor yerləşir: -ci sətr və -ci sütunun kəsişməsində (x_{i,j}, y_{i,j}) vektoru yerləşir (1 \leq i \leq n, 1 \leq j \leq m).
Robot-at gəzməyə qərar verib və addımlıq bir proqram hazırlayıb. -ci addımda (1 \leq t \leq k), robot-at cari mövqeyindən, matrisin ((t-1) \bmod n) + 1 nömrəli sətrindən istənilən vektoru seçərək hərəkət edə bilər. Hər addımda, həmçinin, yerində qalmaq da olar.
Sizə robot-atın istifadə etdiyi matrisi və ədədi verilir. Robot-atın başlanğıc mövqeyindən ən çox hansı məsafəyə hərəkət edə biləcəyini tapın. Bu maksimum məsafənin kvadratını hesablayın.
Birinci sətrdə üç tam ədəd , , (1 \leq n, m \leq 10^5, 1 \leq k \leq 10^9, n \leq m \leq 10^5) — matrisin ölçüsü və addımların sayı verilir.
Növbəti sətrin hər birində 2 \cdot m ədəd verilir: -ci sətrdə 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).
Bir tam ədəd çap edin — robot-atın başlanğıcdan maksimal hərəkət imkanının kvadratını.
Nümunə 1