During the last parliament elections in Berland two political parties collected the same amount of votes. Now the first party hired you to help them with their plan of a revolution.

During the revolution they want to split the country into two parts. The party is very democratic, so each member has its own separation plan.

The border of Berland can be considered as a convex polygon on the plane. The polygon can have three or more consecutive vertices lay on one line. Each separation plan is represented by the line of the cut.

Your program should calculate the area of the smallest part of the Berland for each separation plan.

Input

The first line contains integer n (3 ≤ n ≤ 50 000). Next n lines contain coordinates xi, yi of the Berland border in the clockwise or counterclockwise order. The polygon is non-degenerate. The next line contains integer p (1 ≤ p ≤ 50 000). Next p lines contain coordinates x1,j, y1,j, x2,j, y2,j of two distinct points on the separation line. All coordinates are real and do not exceed 10 000 by the absolute value. They are given with no more than 4 significant digits after decimal point.

Output

Print p lines. Each line should contain the area of the smallest part after separating Berland with the corresponding line. Print value with at least 6 digits after decimal point. Absolute or relative error must be less than 10-5.

Example