Description

给定一个N个顶点的凸多边形，多边形可能有多个点在一条直线上。

给定M条直线，对于每条直线，问这条直线将多边形划分成的两个区域中，面积较小的那个区域的面积。

Format

Input

第1行包含一个正整数 N ，表示了多边形顶点数。

接下来N行，每行两个绝对值不超过10000的整数 x , y ，按顺时针或者逆时针顺序给出了多边形每个顶点坐标。

第 N +2行包含一个正整数 M ，表示了询问直线的个数。

接下来M行，每行4个绝对值不超过10000的整数x -1~ , y ~1~ , x ~2~ , y ~2~ ，表示了询问直线过(x ~1~ , y ~1~ ), (x ~2~ , y ~2~ )两点，并保证了(x ~1~ , y ~1~ ) ≠ (x ~2~ , y ~2~ )。若直线将凸多边形划分成两部分，则输出较小那部分的面积，否则输出 0 。

Output

应包含M行，对于每条直线输出对应结果，保留****4 位小数 。

Samples

5
0 0
0 5
0 10
10 10
10 0
4
0 0 10 10
9 10 10 9
10 -1 12 11
10 10 0 5

50.0000
0.5000
0.0000
25.0000

Limitation

对于100%的数据，有N, M ≤ 50000

保留小数点后6位或以上，SPJ检查精度为小数点后4位