题目描述

小可可最近在学习平面几何！

给定平面上的 $n$ 个点 $(x_1, y_1), (x_2, y_2), \cdots, (x_n, y_n)$。

根据题目要求，输出下列两个值其中一个：

1. 任意两点间欧几里得距离最大值的平方，对于两个点 $(x_i, y_i)$ 和 $(x_j, y_j)$，欧几里得距离定义为 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$。

2. 任意两点间曼哈顿距离最大值，对于两个点 $(x_i, y_i)$ 和 $(x_j, y_j)$，曼哈顿距离定义为 $|x_i - x_j| + |y_i - y_j|$。

输入格式

第一行，两个整数 $n, op$，$n$ 为平面内有多少个点，$op$ 为 1 则求欧几里得距离最大值的平方，若 $op$ 为 2 则求曼哈顿距离最大值。

第 $2 \sim n+1$ 行，每行两个数 $x_i, y_i$，表示平面上的一个点。

输出格式

一行，一个整数，表示答案。

5 1
3 4
1 2
5 2
3 1
2 3

16

5 2
3 4
1 2
5 2
3 1
2 3

4

提示

数据范围

• 数据点 $1 \sim 2$，$op = 1$，$1 \leq n \leq 10^3$，$1 \leq x_i \leq 10^4$，$y_i = 1$。
• 数据点 $3 \sim 6$，$op = 1$，$1 \leq n \leq 10^3$，$1 \leq x_i \leq 10^9$，$1 \leq y_i \leq 10^9$。
• 数据点 $7 \sim 10$，$op = 2$，$1 \leq n \leq 10^3$，$1 \leq x_i \leq 10^9$，$1 \leq y_i \leq 10^9$。
• 数据点 $11 \sim 14$，$op = 2$，$1 \leq n \leq 10^6$，$1 \leq x_i \leq 10^9$，$y_i = 1$。
• 数据点 $15 \sim 20$，$op = 2$，$1 \leq n \leq 10^6$，$1 \leq x_i \leq 10^9$，$1 \leq y_i \leq 10^9$。