Flatland 的技术进步令人印象深刻。例如，今年将建造一种新型太阳能发电站。在这些发电站中，太阳能电池板不是安装在地面上，而是安装在高塔上，沿着塔身分布。

现有 $n$ 座塔需要安装。塔已经购买完毕，第 $i$ 座塔的高度为 $h_i$。现在工程师们想要选择这些塔的安装位置，以获得最大的总发电功率。

发电厂所在区域的地形由一条包含 $m$ 个顶点的折线描述。地形折线的顶点坐标为 $(x_i, y_i)$，满足 $x_i < x_{i+1}$。

在 Flatland，太阳光照射的角度始终为 $\alpha$ 度。太阳从左上方照射向右下方。塔产生的功率取决于其被太阳照射到的表面长度。

当两座塔安装得非常靠近时，左侧塔的阴影可能会落在右侧塔上，从而降低右侧塔产生的功率。此外，地形本身也可能包含高点，这些高点会向某些塔投下阴影。

你的任务是找到在发电厂区域内安装这些塔的位置，使得被太阳照射到的塔表面总长度最大。

输入格式

第一行包含三个整数 $n, m$ 和 $\alpha$ ($1 \le n \le 10^4, 2 \le m \le 10^4, 1 \le \alpha < 90$)。 第二行包含 $n$ 个整数 $h_i$，表示塔的高度 ($1 \le h_i \le 10^3$)。 接下来的 $m$ 行包含坐标对 $x_i, y_i$，表示地形的顶点坐标 ($|x_i| \le 10^5, x_i < x_{i+1}, |y_i| \le 10^3$)。

输出格式

第一行输出塔被太阳照射到的最大总长度，要求绝对误差不超过 $10^{-6}$。 接下来的 $n$ 行输出安装塔的 $x$ 坐标，以达到该最大值，要求绝对误差不超过 $10^{-9}$。塔的输出顺序应与输入中给出的顺序一致。

样例

输入格式 1

5 4 10
20 10 20 15 10
0 10
40 20
50 0
70 30

输出格式 1

52.342888649592545
16.0
0.0
70.0
65.3
65.3

说明

在此示例中，两座塔安装在同一个点。这是允许的，但在同一个点安装的塔中，只有最高的那一座被视为受到太阳照射。