Description

平地上的技术进步令人惊叹。今年正要建造一种新型的太阳能发电站。在这些发电站中，太阳能电池板不是安装在地面上，而是安装在高塔上。

在二为世界中有要安装$i$个高塔。这些塔塔高固定。第$i$座塔的高度是$h_i$。现在，工程师们想要选择安装点，以获得最大的总功率。

电厂区域由有$m$顶点的线连接。这些线的顶点坐标为$(x_i,y_i)$满足$x_i<x_{i+1}$ 在平地上，太阳的角度总是$\alpha$度。太阳从左上角照射到右下角。塔产生的功率取决于其表面被太阳照射的面积(其实是长度)。

当安装的两个塔彼此靠近时，左侧塔的阴影可能落在右侧塔上，从而右侧塔产生的功率降低。此外，电厂区域本身可能包含在某些塔楼上投下阴影的高点。

你的任务是在电厂区域内找到安装给定塔架的点，以得到太阳照射下塔架最大总表面积(长度)。

Input Format

输入第一行包含三个整数：$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)$

Output Format

第一行:以至少$10^{-6}$精度输出可被太阳照亮的塔的最大可能汇总面积（长度)。在后n行上，输出此时塔安装点的x坐标，绝对精度至少为$10^{-9}$。塔的输出顺序应与输入顺序相同。

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

52.342888649592545
16.0
0.0
70.0
65.3
65.3

Hint

时间限制：1h

空间顺序：128PB