该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

$\hspace{15pt}$神秘猫猫头因为误闯入了鼹鼠大王的后花园，并不小心把鼹鼠大王的兵马俑踢碎了，鼹鼠大王十分生气，并派出了手下的超级鼹鼠去制裁神秘猫猫头。为了逃脱鼹鼠大王的追捕，神秘猫猫头联系了驾兵来接应他。驾兵为了不被发现，需要选择一个安全的地方来接应猫猫头。

$\hspace{15pt}$鼹鼠大王的后花园是一个由 $n$ 个点构成的凸多边形，超级鼹鼠会在后花园坐标为 $(x,y)$ 的位置立正，并且手上拿着探测半径为 $r$ 的雷达。驾兵认为，安全的地方应该是以一条经过多边形任意两个顶点的直线将后花园分割成的两块面积中，不包含超级鼹鼠的探测范围的一块。为了尽可能安全撤离，神秘猫猫头需要选择所有可能情况中面积最大的那一块，然后告诉驾兵。但是猫猫头突然想起来他不会算多边形的面积，请你帮帮他。

Input

$\hspace{15pt}$有多个测试数据，第一行输入一个整数 $T$ 表示测试数据组数。对于每一组测试数据：

$\hspace{15pt}$第一行输入一个整数 $n(3 \leq n \leq 10^5)$,表示作为凸多边形的后花园的顶点数。

$\hspace{15pt}$第二行输入三个整数 $x,y$ 和 $r$ $(-10^9 \leq x,y \leq 10^9,1 \leq r \leq 10^9)$ 表示鼹鼠大王的位置和探测半径。

$\hspace{15pt}$对于接下来的 $n$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个点的坐标。顶点按逆时针顺序列出。保证任意两点不重合。但可能有三个点在同一直线上。

$\hspace{15pt}$保证超级鼹鼠的探测范围都在后花园的边界内。且所有数据 $n$ 之和不超过 $10^5$

Output

$\hspace{15pt}$每组测试数据输出一行一个整数，表示最大的安全范围的面积的两倍。可以证明这个值始终是一个整数。如果无法找到合法切割凸多边形的方法，则输出 $0$。

Example

2
4
5 12 1
0 15
2 0
17 15
2 20
5
9 12 1
0 13
15 0
19 13
12 19
1 18

85
168

Note

$\hspace{15pt}$样例图形如下