一名保安在博物馆内巡逻以监视展品。巡逻路线是一条由 $n$ 个顶点（编号为 $1$ 到 $n$）组成的闭合折线，这些顶点按顺序连接（最后一个顶点连接回第一个顶点）以形成 $n$ 条连续的线段。保安按照 $1 \to 2 \to \dots \to n \to 1 \to \dots$ 的顺序进行巡逻。当保安不在折线的顶点（端点）上时，他们的视野是一个半径为 $r$、圆心角为 $2a$ 的扇形，该扇形的角平分线与巡逻线段的前进方向一致。

巡逻线段上（不含端点）的点 $P$ 能够看到位于点 $Q$ 的展品，当且仅当 $Q$ 落在以 $P$ 为顶点的扇形区域内。给定由 $n$ 个点确定的闭合折线巡逻路线以及 $m$ 个展品的位置，对于每个 $k = 0, 1, \dots, m$，求出恰好能看到 $k$ 个展品的巡逻路线总长度。

输入格式

每个测试文件中只有一组测试数据。

第一行包含四个整数 $n$、$m$、$r$ 和 $a$（$3 \le n \le 2 \times 10^3$，$1 \le m \le 2 \times 10^3$，$1 \le r \le 10^4$，$0 < a < 90$），分别表示闭合折线的顶点数、展品数量、视野半径以及视野半角（以度为单位）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^4 \le x_i, y_i \le 10^4$），表示折线第 $i$ 个顶点的坐标。相邻的顶点形成巡逻线段，且最后一个顶点连接回第一个顶点以形成闭合回路。保证任意两个相邻顶点（包括最后一个顶点和第一个顶点）不重合。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x'_i$ 和 $y'_i$（$-10^4 \le x'_i, y'_i \le 10^4$），表示第 $i$ 个展品的坐标。

输出格式

输出 $m + 1$ 行，其中第 $i$ 行包含一个实数，表示恰好能看到 $i - 1$ 个展品的巡逻路线总长度。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。具体来说，假设你的答案为 $a$，评测答案为 $b$，当且仅当 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 时，你的答案才会被接受。

样例

输入样例 1

3 2 3 45
1 1
5 5
8 1
2 3
4 2

输出样例 1

14.178145584873
2.247170915928
1.231537748691

输入样例 2

4 1 3 60
0 0
6 6
6 0
0 6
2 1

输出样例 2

25.279547784093
3.691014964384

说明

第一个样例的示意图如下。$A$ 和 $B$ 是两个展品，$G$ 是保安。

第一个样例示意图