最近点对问题是计算几何中的一个经典问题。在本题中，欧几里得平面上有 $n$ 个点 $p_1, p_2, \dots, p_n$。你将收到 $q$ 次查询。在第 $i$ 次查询中，给定两个整数 $l_i$ 和 $r_i$ ($1 \le l_i < r_i \le n$)。你需要找到一对点 $(u, v)$，使得 $l_i \le u < v \le r_i$，且点 $p_u$ 与 $p_v$ 之间的欧几里得距离 $\sqrt{(x_u - x_v)^2 + (y_u - y_v)^2}$ 最小。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 250\,000, 1 \le q \le 250\,000$)，分别表示点的数量和查询的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le 10^8$)，描述点 $p_i$ 的坐标。

接下来的 $q$ 行中，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i < r_i \le n$)，表示一次查询。

输出格式

对于每次查询，输出一行，包含一个整数，表示 $(x_u - x_v)^2 + (y_u - y_v)^2$ 的值。

样例

输入 1

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

输出 1

2
8
8
2
2

输入 2

2 1
1 1
1 1
1 2

输出 2

0