Во время последних парламентских выборов в Берландии две политические партии собрали одинаковое количество голосов. Теперь одна из партий наняла Вас чтобы помочь им с их планом революции.

Во время революции они хотят разделить страну на две части. Партия очень демократична, поэтому каждый член имеет свой собственный план разделения.

Границу Берландии можно рассматривать как выпуклый многоугольник на плоскости. Многоугольник может иметь три или более последовательных вершины, лежащих на одной прямой. Каждый план разделения представлен линией разреза.

Ваша программа должна рассчитать площадь наименьшей части Берландии для каждого плана разделения.

Входные данные

Первая строка содержит число n (3 ≤ n ≤ 50 000). Следующие n строк содержат координаты xi, yi границы Берландии по или против часовой стрелки. Многоугольник является невырожденным. Следующая строка содержит число p (1 ≤ p ≤ 50 000). Следующие p строк содержат координаты x1,j, y1,j, x2,j, y2,j двух различных точек разделительной прямой. Все координаты - действительные числа, не превосходящие по модулю 10 000. Они заданы с не более чем 4 десятичными знаками.

Выходные данные

Выведите p строк. Каждая строка должна содержать площадь меньшей части после раздела Берландии соответствующей линией. Ответ выводить с не менее 6 цифрами после десятичной точки. Абсолютная или относительная ошибка должна быть меньше 10-5.

Пример