Problem: <image>


As shown in the figure above, cut a convex polygon g by a line p1p2 and print the area of the cut polygon which is on the left-hand side of the line.

g is represented by a sequence of points p1, p2,..., pn where line segments connecting pi and pi+1 (1 ≤ i ≤ n−1) are sides of the convex polygon. The line segment connecting pn and p1 is also a side of the polygon.

Constraints

* 3 ≤ n ≤ 100
* 1 ≤ q ≤ 100
* -10000 ≤ xi, yi ≤ 10000
* -10000 ≤ p1x,p1y,p2x,p2y ≤ 10000
* No point in g will occur more than once.
* p1 ≠ p2

Input

The input is given in the following format:


g (the sequence of the points of the polygon)
q (the number of queries = the number of target lines)
1st query
2nd query
:
qth query


g is given as a sequence of points p1,..., pn in the following format:


n
x1 y1
x2 y2
:
xn yn


The first integer n is the number of points. The coordinate of the i-th point pi is given by two integers xi and yi. The coordinates of points are given in the order of counter-clockwise visit of them. Note that all interior angles of given convex polygons are less than or equal to 180.

For each query, a line represented by two points p1 and p2 is given. The coordinates of the points are given by four integers p1x, p1y, p2x and p2y.

Output

For each query, print the area of the cut polygon. The output values should be in a decimal fraction with an error less than 0.00001.

Example

Input

4
1 1
4 1
4 3
1 3
2
2 0 2 4
2 4 2 0


Output

2.00000000
4.00000000

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;

// 参考サイト
// http://www.prefield.com/algorithm/index.html

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> Point; //複素数で平面定義
using P = Point ;

// system {{{
// オペレーター< を定義、後々楽
namespace std{
    bool operator < ( const P& a, const P& b) {
        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
}

// 外積
double cross( const P& a, const P& b ){
    return imag(conj(a)*b);
}
// 内積
double dot( const P& a, const P& b ){
    return real(conj(a)*b);
}
// }}}
// Line L:vector<P> Polygon G:vector<P> Circle C(P,int rad) {{{
// 直線 Line 線分 Segment {{{
struct L : public vector<P> {
    L(const P &a, const P &b ){
        push_back(a); push_back(b);
    }
};
using Line = L;
// }}}
// 単純多角形 Polygon {{{
struct G : public vector<P> {
    Point curr( int i ){
        return *(begin()+i);
    }
    Point next( int i ){
        return *(begin()+(i+1)%size());
    }
    Point prev( int i ){
        i += size();
        return *(begin()+(i-1)%size());
    }
    double area2(){
        double A = 0.0;
        for( int i = 0; i < size(); i++ ){
            A += cross( curr(i),next(i) );
        }
        return A;
    }
    int contains( P &p ){
        bool in = false;
        for( int i = 0; i < size(); i++ ){
            Point a = curr(i) - p, b = next(i) - p;
            if( imag(a) > imag(b) ) {
                Point c = a;
                a = b; b = c;
            }
            if( imag(a) <= 0 && 0 < imag(b))
                if( cross(a,b) < 0) in = !in;
            if( cross(a,b) == 0 && dot(a, b) <= 0 ) return 1;
        }
        return in*2;
    }
    Point& operator []( size_t i ){
        return *(begin()+i%size());
    }
    const Point& operator []( size_t i ) const {
        return *(begin()+i%size());
    }
};
using Polygon = G;
//}}}
// 円 cirlce {{{
struct C {
    P p; double r;
    C(const P &p, double r ) : p(p), r(r) {}
};
// }}}
// }}}
// counter clockwise {{{
//
int ccw( P a, P b, P c ){
    b -= a; c -= a;
    if( cross(b,c) > 0 )   return +1; //counter clockwise
    if( cross(b,c) < 0 )   return -1; //clockwise
    if( dot(b,c) < 0 )     return +2; //online_back
    if( norm(b) < norm(c)) return -2; //online_front
    return 0; // on_segment
} //}}}
// 交点判定 交点座標 LSPtoLSP {{{
bool intersectLL( const L &l, const L &m ){
    return abs( cross(l[1]-l[0], m[1]-m[0]) ) > EPS || // cross(l,m) != 0 <-> not paralell
           abs( cross(l[1]-l[0], m[0]-l[0]) ) < EPS;   // cross(l,(m-l)) == 0 <-> same line
}
bool intersectLS( const L &l, const L &s ){
    return cross( l[1]-l[0], s[0]-l[0] ) *
           cross( l[1]-l[0], s[1]-l[0] ) < EPS;
}
bool intersectLP( const L &l, const P &p ){
    return abs( cross(l[0]-p, l[1]-p) );
}
bool intersectSS( const L &s, const L &t ){
    return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
           ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}
bool intersectSP( const L &s, const P &p ){
    return abs( s[0]-p )+abs( s[1]-p )-abs(s[1]-s[0]) < EPS;
}
P crossPoint( const L &l, const L &m ){
    double A = cross( l[1] - l[0], m[1] - m[0] );
    double B = cross( l[1] - l[0], l[1] - m[0] );
    // A は に直線の成す平行四辺形
    // B は そのA のうちの片側
    // 書いたら分かる
    // 参考サイト
    // http://www.fumiononaka.com/Business/html5/FN1312003.html
    if( abs(A) < EPS && abs(B) < EPS ) return m[0];
    return m[0] + B / A * ( m[1] - m[0] );
}
// }}}
// 射影 反射 距離 LSPtoLSP  {{{
P projection( const L &l, const P &p ){
    double t = dot( p-l[0], l[0]-l[1] ) / norm( l[0]-l[1] );
    return l[0] + t*(l[0]-l[1]);
}
P reflection( const L &l, const P &p ){
    return p + 2.0*( projection(l,p) - p );
}
double distanceSP( const L &s, const P &p ){
    const P r = projection(s,p);
    if( intersectSP(s,r) ) return abs(r-p);
    else return min( abs(s[0] - p), abs(s[1] - p) );
}
double distanceSS( const L &s, const L &t ){
    if( intersectSS(s,t) ) return 0.0;
    return min( min( distanceSP(s,t[0]), distanceSP(s,t[1]) ),
                min( distanceSP(t,s[0]), distanceSP(t,s[1]) ) );
}
// }}}
// 多角形面積 G {{{
double area2( const Polygon &P ){
    double A = 0.0;
    for( int i = 0; i < P.size(); i++ ){
        A += cross( P[i], P[(i+1)%P.size()] );
    }
    return A;
}
// }}}
// 凸包 {{{
Polygon convexHull( Polygon pl ){
    int n = pl.size(), k=0;
    sort( pl.begin(), pl.end() , []( Point& a, Point& b ) -> bool {
        return imag(a) != imag(b) ? imag(a) < imag(b) : real(a) < real(b);
    } );
    // sort( pl.begin(), pl.end());
    Polygon ch;
    ch.resize(2*n);
    for( int i = 0; i < n; ch[k++] = pl[i++] )
        while( k >= 2 && ccw( ch[k-2], ch[k-1], pl[i] ) == -1 )k--;
    for( int i = n-2, t = k+1; i >= 0; ch[k++] = pl[i--] )
        while( k >= t && ccw( ch[k-2], ch[k-1], pl[i] ) == -1 )k--;
    ch.resize(k-1);
    return ch;

}
// }}}
// 凸多角形の直径 {{{
double convexDiameter( const Polygon &pt ){
    const int n = pt.size();
    int is = 0, js = 0;
    for (int i = 1; i < n; i++){
        if( imag(pt[i]) > imag(pt[is]) ) is = i;
        if( imag(pt[i]) < imag(pt[js]) ) js = i;
    }
    double maxd = norm( pt[is] - pt[js] );
    int i,maxi,j,maxj;
    i = maxi = is;
    j = maxj = js;
    do{
        Point pi = pt[i+1] - pt[i];
        Point pj = pt[j+1] - pt[j];
        if( cross(pi , pj) >= -EPS ) j++;
        else i++;
        i %= n;
        j %= n;
        if( norm( pt[i] - pt[j] ) > maxd ){
            maxd = norm( pt[i] - pt[j] );
            maxi = i; maxj = j;
        }
    } while ( i != is || j != js );
    return maxd; /* farthest pair is (maxi, maxj). */
}
// }}}
// 凸多角形の切断 {{{
pair<Polygon,Polygon> convexCut( const Polygon& P , const Line &l ){
    pair<Polygon, Polygon> Q;
    // Q.first:LeftRemain
    // Q.right:RightRemain
    for( int i = 0; i < P.size(); i++ ){
        Point A = P[i]; Point B = P[i+1];
        if( ccw( l[0], l[1], A ) != -1 ) Q.first.push_back(A);
        else Q.second.push_back(A);
        if( ccw( l[0], l[1], A ) * ccw( l[0], l[1], B ) < 0)
            A = crossPoint( Line(A,B), l ),
            Q.first.push_back(A),
            Q.second.push_back(A);
    }
    return Q;
}
// }}}
// imagePointDescription(点表示) {{{ 
void imagePointDescription( const vector<P> &p, double scale = 1 ){
    int here[51][51] = {};
    int i = 0;
    for( P t : p ){
        i++;
        int y = round(imag(t)/scale);
        int x = round(real(t)/scale);
        if( abs(y) > 25 ) continue;
        if( abs(x) > 25 ) continue;
        here[y+25][x+25] = i;
    }

    for( i = 50; i >= 0; i-- ){
        for( int j = 0; j <= 50; j++ ){
            if( here[i][j] ) printf ("%2d", here[i][j] );
            else if( i == 25 && j == 25 ) printf ("-+");
            else if( i == 25 ) printf ("--");
            else if( j == 25 ) printf (" |");
            else if( j % 5 == 0 && i % 5 == 0)printf (" .");
            else printf ("  ");
        }
        printf ("\n");
    }

}
// }}}

int main() {

    double a,b,c,d;


    G pol;
    int q;
    int n;
    cin >> n;
    while(n--){
        cin >> a >> b;
        P p(a,b);
        pol.push_back(p);
        // printf ("%1.10lf %1.10lf\n", real(x), imag(x) );
    }
    // imagePointDescription(pol,1);

    cin >> q;
    while(q--){
        cin >> a >> b >> c >> d;
        // G gg = 
        // convexCut(pol,L(P(a,b),P(c,d))).first;
        // imagePointDescription(gg,1);
        printf ("%1.13lf\n", area2(convexCut(pol,L(P(a,b),P(c,d))).first)/2.0 );
    }


    return 0;
}