p00787 Digital Racing Circuil_33290
You have an ideally small racing car on an x-y plane (0 ≤ x, y ≤ 255, where bigger y denotes upper coordinate). The racing circuit course is figured by two solid walls. Each wall is a closed loop of connected line segments. End point coordinates of every line segment are both integers (See Figure 1). Thus, a wall is represented by a list of end point integer coordinates (x1, y1), (x2, y2), ...,(xn, yn). The start line and the goal line are identical.

<image>
Figure 1. A Simple Course

For the qualification run, you start the car at any integer coordinate position on the start line, say (sx, sy).

At any clock t (≥ 0), according to the acceleration parameter at t, (ax,t, ay,t), the velocity changes instantly to (vx,t-1 + ax,t, vy,t-1 + ay,t), if the velocity at t - 1 is (vx,t-1, vy,t-1). The velocity will be kept constant until the next clock. It is assumed that the velocity at clock -1, (vx,-1, vy,-1) is (0, 0). Each of the acceleration components must be either -1, 0, or 1, because your car does not have so fantastic engine and brake. In other words, any successive pair of velocities should not differ more than 1 for either x-component or y-component. Note that your trajectory will be piecewise linear as the walls are.

Your car should not touch nor run over the circuit wall, or your car will be crashed, even at the start line. The referee watches your car's trajectory very carefully, checking whether or not the trajectory touches the wall or attempts to cross the wall.

The objective of the qualification run is to finish your run within as few clock units as possible, without suffering from any interference by other racing cars. That is, you run alone the circuit around clockwise and reach, namely touch or go across the goal line without having been crashed. Don't be crashed even in the last trajectory segment after you reach the goal line. But we don't care whatever happens after that clock

Your final lap time is the clock t when you reach the goal line for the first time after you have once left the start line. But it needs a little adjustment at the goal instant. When you cross the goal line, only the necessary fraction of your car's last trajectory segment is counted. For example, if the length of your final trajectory segment is 3 and only its 1/3 fraction is needed to reach the goal line, you have to add only 0.333 instead of 1 clock unit.

Drivers are requested to control their cars as cleverly as possible to run fast but avoiding crash. ALAS! The racing committee decided that it is too DANGEROUS to allow novices to run the circuit. In the last year, it was reported that some novices wrenched their fingers by typing too enthusiastically their programs. So, this year, you are invited as a referee assistant in order to accumulate the experience on this dangerous car race.

A number of experienced drivers are now running the circuit for the qualification for semi-finals. They submit their driving records to the referee. The referee has to check the records one by one whether it is not a fake.

Now, you are requested to make a program to check the validity of driving records for any given course configuration. Is the start point right on the start line without touching the walls? Is every value in the acceleration parameter list either one of -1, 0, and 1? Does the length of acceleration parameter list match the reported lap time? That is, aren't there any excess acceleration parameters after the goal, or are these enough to reach the goal? Doesn't it involve any crash? Does it mean a clockwise running all around? (Note that it is not inhibited to run backward temporarily unless crossing the start line again.) Is the lap time calculation correct? You should allow a rounding error up to 0.01 clock unit in the lap time.



Input

The input consists of a course configuration followed by a number of driving records on that course.

A course configuration is given by two lists representing the inner wall and the outer wall, respectively. Each line shows the end point coordinates of the line segments that comprise the wall. A course configuration looks as follows:


ix,1 iy,1 ..... ix,N iy,N 99999
ox,1 oy,1 ..... ox,M oy,M 99999


where data are alternating x-coordinates and y-coordinates that are all non-negative integers (≤ 255) terminated by 99999. The start/goal line is a line segment connecting the coordinates (ix,1, iy,1) and (ox,1, oy,1). For simplicity, iy,1 is assumed to be equal to oy,1; that is, the start/goal line is horizontal on the x-y plane. Note that N and M may vary among course configurations, but do not exceed 100, because too many curves involve much danger even for experienced drivers. You need not check the validity of the course configuration.

A driving record consists of three parts, which is terminated by 99999: two integers sx, sy for the start position (sx, sy), the lap time with three digits after the decimal point, and the sequential list of acceleration parameters at all clocks until the goal. It is assumed that the length of the acceleration parameter list does not exceed 500. A driving record looks like the following:


sx sy
lap-time
ax,0 ay,0 ax,1 ay,1 ... ax,L ay,L 99999


Input is terminated by a null driving record; that is, it is terminated by a 99999 that immediately follows 99999 of the last driving record.

Output

The test result should be reported by simply printing OK or NG for each driving record, each result in each line. No other letter is allowed in the result.

Example

Input

6 28 6 32 25 32 26 27 26 24 6 24 99999
2 28 2 35 30 35 30 20 2 20 99999

3 28
22.667
0 1 1 1 1 0 0 -1 0 -1 1 0 0 0 1 0 -1 0 0 -1 -1 -1 -1 0 -1 0 -1 -1 -1 1 -1 1
-1 1 -1 0 1 0 1 1 1 1 1 0 1 1 99999

5 28
22.667
0 1 -1 1 1 0 1 -1 1 -1 1 0 1 0 1 0 -1 -1 -1 0 -1 -1 -1 0 -1 1 -1 -1 -1 1
-1 0 -1 1 -1 0 1 0 1 0 1 1 1 1 1 1 99999

4 28
6.333
0 1 0 1 1 -1 -1 -1 0 -1 0 -1 0 -1 99999

3 28
20.000
0 -1 1 -1 1 0 1 1 1 1 1 0 -1 0 -1 0 -1 1 -1 1
-1 1 -1 0 -1 -1 -1 -1 -1 -1 -1 0 1 0 1 -1 1 -1 1 -1 99999

99999


Output

OK
NG
NG
NG
#include<iostream>
#include<cmath>
#include<vector>
#include<complex>
#include<cassert>

using namespace std;

#define OVER 0x01
#define RIGHT 0x02
#define LEFT 0x04
#define FRONT 0x08
#define BACK 0x10

typedef long long elem;
typedef complex<elem> point, vec;
typedef pair<point,point> line, seg;

elem dot(point a, point b){ return a.real() * b.real() + a.imag() * b.imag(); }
elem cross(point a, point b){ return a.real() * b.imag() - a.imag() * b.real(); }
elem abs2(point a){ return dot(a,a); }

inline int ccw(const point &a, point b, point x){
  b-=a;
  x-=a;
  if( cross(b,x) == 0 && dot(b,x) < 0 ) return BACK;
  if( cross(b,x) == 0 && abs2(b) < abs2(x) ) return FRONT;
  if( cross(b,x) == 0 ) return OVER;
  if( cross(b,x) > 0 ) return LEFT;
  return RIGHT;
}

inline bool intersectedSS(const seg &a, const seg &b){
  int cwaf=ccw(a.first,a.second,b.first);
  int cwbf=ccw(b.first,b.second,a.first);
  int cwas=ccw(a.first,a.second,b.second);
  int cwbs=ccw(b.first,b.second,a.second);
  if( !( (cwaf|cwas)&(RIGHT|LEFT) ) ) return false;
  if(cwaf == OVER || cwas == OVER || cwbf == OVER || cwbs==OVER) return true;
  return (cwaf|cwas)==(LEFT|RIGHT) && (cwbf|cwbs)==(LEFT|RIGHT);
}

complex<double> intersectionLL(const line &a, const line &b){
  vec va=a.second-a.first;
  vec vb=b.second-b.first;
  assert(cross(vb,va)!=0);
  double t = cross(vb,b.first-a.first)/(double)cross(vb,va);
  return complex<double>(a.first.real() + t * va.real(), a.first.imag() + t * va.imag());
}

bool inSimple(const point &x, const vector<point> &p){
  const int n = p.size();
  if(n<3)return false;
  int cnt=0;
  for(int i=0;i<n;++i){
    point a=p[i]-x,b=p[(i+1)%n]-x;
    if(b.imag()>a.imag())swap(a,b);
    int cw=ccw(a,b,point(0,0));
    if(cw==LEFT&&0<=a.imag()&&b.imag()<0)++cnt;
    if(cw==OVER)return true;
  }
  if(cnt&1)return true;
  else return false;
}

bool goal(const seg &orbit, const seg &gline, complex<double> &ret){
  if( intersectedSS(orbit,gline) ){
    ret = intersectionLL( orbit, gline );
    return true;
  }
  return false;
}

double dist2(const point &a, const complex<double> &b){
  double dx = b.real() - a.real();
  double dy = b.imag() - a.imag();
  return pow(dx,2) + pow(dy,2);
}

bool crashed(const seg &orbit, const vector<point> &inner, const vector<point> &outer,  complex<double> &nearest){
  bool ret = false;
  double n_dist = 1e40;
  for(int k = 0; k < 2; ++k){
    vector<point> c;
    if( k == 0 ){ c = inner; }else{ c = outer; }
    for(int i = 0; i < (int)c.size(); ++i){
      seg s = seg( c[i], c[(i+1)%c.size()] );
      if( intersectedSS( orbit, s ) ){
        // cout << i << ' ' << orbit.first << '-' << orbit.second << " + " << s.first << '-' << s.second << endl;
        ret = true;
        complex<double> tmp;
        tmp = intersectionLL( orbit, s );
        if( n_dist > dist2( orbit.first, tmp ) ){
          nearest = tmp;
          n_dist = dist2(orbit.first, tmp);
        }
      }
    }
  }
  return ret;
}

int main(){
  int T;
  //cin >> T;
  T = 1;
  for(int tc=1;tc<=T;++tc){
    vector<point> inner, outer;
    elem start_y;
    elem start_x1, start_x2;
    line gline;
    bool rev = false;
    
    while(true){
      elem x,y;
      cin >> x;
      if( x == 99999 ) break;
      cin >> y;
      inner.push_back( point(x,y) );
    }
    while(true){
      elem x,y;
      cin >> x;
      if( x == 99999 ) break;
      cin >> y;
      outer.push_back( point(x,y) );
    }

    if(tc>1)cout<<endl;
    
    if( inSimple( outer.front(), inner ) ){
      swap( inner, outer );
    }
    
    assert( inner.size() > 2 );
    assert( outer.size() > 2 );
    
    start_y = outer.front().imag();
    start_x1 = outer.front().real();
    start_x2 = inner.front().real();
    
    if( start_x1 > start_x2 ){
      swap( start_x1, start_x2 );
      rev = true;
    }
    
    gline = line( point(start_x1, start_y), point(start_x2, start_y) );

    while(true){
      bool ng = false;
      bool cleared = false;
      double clear_time = 0;
      int vx = 0, vy = 0;
      int counter = 0;
      elem sx, sy;
      
      cin >> sx;
      if( sx == 99999 ) break;
      cin >> sy;
      
      if( sy != start_y ) ng = true;
      if( !(start_x1 < sx && sx < start_x2) ) ng = true;
      
      double laptime;
      cin >> laptime;
      
      elem x = sx, y = sy;
      elem px=-1,py=-1;
      bool under_y = false;
      bool above_y = false;
      bool cont_on_line = false;

      while(true){
        int ax, ay;
        
        cin >> ax;
        if( ax == 99999 ) break;
        cin >> ay;

        ++counter;
        vx += ax;
        vy += ay;
        
        if( !(ax == -1 || ax == 0 || ax == 1) ) ng = true;
        if( !(ay == -1 || ay == 0 || ay == 1) ) ng = true;

        if( cleared ){
          cleared = false;
          ng = true;
          continue;
        }
        if( ng ) continue;

        if( start_x1 < x && x < start_x2 && y == start_y ){
          cont_on_line = true;
          if( start_x1 < x+vx && x+vx < start_x2 && y+vy == start_y ){
            x += vx;
            y += vy;
            continue;
          }
        }
        if( cont_on_line && py >= 0 ){
          if( (py-start_y) * (y-start_y) < 0 ){
            ng = true;
          }
        }

        cont_on_line = false;

        if( ng ) continue;
        if( vx == 0 && vy == 0 ) continue;
        
        seg orbit( point(x,y), point(x+vx, y+vy) );
        complex<double> tmp, gpoint;
                
        if( crashed( orbit, inner, outer, tmp ) ){
          ng = true;
        }
        
        if( goal( orbit, gline, gpoint ) ){
          if( ( rev ? y > start_y : y < start_y ) && under_y && above_y ){
            // cross the goal line
            if( ng ){
              if( dist2( orbit.first, gpoint ) < dist2( orbit.first, tmp ) - 1e-6 ){
                cleared = true;
              }
            }else{
              cleared = true;
            }
            if( cleared ){
              clear_time = counter - sqrt(dist2(orbit.second,gpoint))/sqrt((vx*vx+vy*vy));
            }
          }else if( dist2( orbit.second, gpoint ) > 1e-6 ){
            // cross the start line
            if( counter > 1 ){
              ng = true;
            }else{
              if( rev ){ if( orbit.second.imag() > start_y ) ng = true; }
              else     { if( orbit.second.imag() < start_y ) ng = true; }
            }
          }
        }

        px = x;
        py = y;
        x += vx;
        y += vy;
        
        if( y < start_y ) under_y = true;
        if( y > start_y ) above_y = true;
      }
      
      if( !ng && cleared && abs(laptime - clear_time) <= 0.01  ){
        cout << "OK" << endl;
      }else{
        cout << "NG" << endl;
      }
      
    }
    
  }
  return 0;
}