题目描述

弗拉特兰国的科技发展令人瞩目。举例来说，今年当地将要建造一批新型太阳能电站。这类电站的太阳能电池板不铺设在地面上，而是沿着高塔的竖直高度进行安装。

一共有 $n$ 座高塔待安装。第 $i$ 座高塔的高度为 $h_i$。现在工程师需要选定这些塔的安装位置，使得总发电量最大。

电站所在区域的地势由一条折线描述，折线共有 $m$ 个顶点，第 $i$ 个顶点为 $(x_i,y_i)$，满足 $x_i<x_{i+1}$。

在弗拉特兰国，太阳光的照射角度恒为 $\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}$ 范围内。

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