Problem: Princess, a Strategist

Princess is a strategist

English text is not available in this practice contest.

A brave princess in a poor country is on an adventure to escape the castle and obtain ancient treasures. However, the area around the ancient treasure is protected by multiple guardians and cannot be reached in the usual way. So, the princess deceived you as a servant and thought of a strategy to retrieve the treasure while attracting the attention of the Guardians. It's not enough to have any number of lives to do such a thing, but I can't help but obey the orders of the princess. So, first of all, you scouted in advance and carefully investigated how to move to avoid the Guardian's attack and attract attention. Your job is to write a program based on these findings to calculate when and how many decoy bullets fired by you and the Guardian collided.

First, for simplicity, consider a two-dimensional plane looking down from a sufficiently high place as a field. And you are equipped with armor to protect yourself from Guardian attacks. Therefore, you can think of your shape as a polygon. Note that the line segments of this polygon do not intersect or overlap at all. You can also assume the following about your movement.

* Only constant velocity linear motion.
* Acceleration, deceleration, and turning are all done in an instant.
* Since it does not rotate, the orientation does not change at all from the initial state.
* All parts of the polygon are always in the positive y coordinate.



The following can be assumed for the bullets fired by the Guardian.

* The thickness of the bullet fired by the Guardian is negligible
* The bullets fired by the Guardian have a finite length
* If a bullet of length l is fired from the start coordinates (x, 0) with a velocity vector (vx, vy), the end coordinates of the bullet are at the following points (Note: of the bullet at the moment the bullet is fired) All leading y coordinates are 0):
\ (x-\ (l * vx / sqrt \ (vx ^ 2 + vy ^ 2 \) \), 0-\ (l * vy / sqrt \ (vx ^ 2 + vy ^ 2 \) \)
* For example, in the case where a bullet of velocity vector (3, 4) length 10 is fired from point (4, 0), the bullet ends at (-2, -8).
* All bullet-to-bullet collisions fired by enemy characters are ignored



The definition of a bullet collision between you and the Guardian is given below. Let the bullet collision time be the time when the common point between the polygons that make up you and the line segment fired by the Guardian first occurs. If you collide with a bullet fired by a guardian, you will only be damaged and will not hinder your movement, and the bullet that collides with you will disappear the moment it collides. It is guaranteed that the collision time will change by at most 10-5 even if you translate in any direction from the initial position in the range of 10-6.

Input

The input consists of multiple datasets.

Each dataset is given in the following format.

> N M B
> X1 Y1
> ...
> XN YN
> T1 VX1 VY1
> ...
> TM VXM VYM
> T'1 X'1 VX'1 VY'1 L1
> ...
> T'B X'B VX'B VY'B LB

Three non-negative integers N (3 ≤ N ≤ 20), M (0 ≤ M ≤ 100), and B (0 ≤ B ≤ 100) are given at the beginning of each dataset. These represent the number of vertices of your polygon, the number of information about your movement, and the number of bullets fired by the Guardian, respectively.

In the next N lines, the coordinates of the vertices of the polygon representing you at time 0 are listed in order. (Xi, Yi) (1 ≤ i ≤ N) represent the coordinates of the i-th vertex of the polygon, respectively. All of these values ​​are integers and satisfy -10,000 ≤ Xi ≤ 10,000, 0 <Yi ≤ 10,000.

The next M line gives you M instructions to indicate your move. The i-th (1 ≤ i ≤ M) move instruction consists of three integers Ti, VXi, VYi, which keeps your velocity vector at (VXi, VYi) from time Ti-1 to Ti. It means to do. However, 0 = T0 <T1 <T2 <... <TM ≤ 10,000, -100 ≤ VXi ≤ 100, -100 ≤ VYi ≤ 100. After you have completed all move instructions (ie, after time TM), you shall stop moving and stay in place. Note that bullet collisions can occur even after you stop, and you need to consider such collisions in your output.

The following line B contains information about the B bullets fired by the Guardian. Information about the i-th (1 ≤ i ≤ B) bullet is represented by the five integers T'i, X'i, VX'i, VY'i and Li, which are coordinated (X') at time T'i. It means that a bullet of length Li with a velocity vector (VX'i, VY'i) is fired from i, 0). These values ​​are 0 ≤ T'1 ≤ T'2 ≤ ... ≤ T'B ≤ 10,000, -10,000 ≤ X'i ≤ 10,000, -100 ≤ VX'i ≤ 100, 0 <VY'i ≤ 100, Satisfy 0 <Li ≤ 100.

The last dataset is followed by a line with "0 0 0", which means the end of the dataset. This is not part of the dataset.

Output

At the beginning of the output for each dataset, print n the number of times you hit the bullet fired by the Guardian. In the next n lines, output the time when you hit the bullet fired by the Guardian in ascending order with an accuracy of at most 0.001.

Sample Input


4 1 1
1 1
1 2
-1 2
-1 1
2 1 0
0 1 0 1 2
0 0 0


Output for the Sample Input


1
1.000






Example

Input

4 1 1
1 1
1 2
-1 2
-1 1
2 1 0
0 1 0 1 2
0 0 0


Output

1
1.000

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-9)
#define equals(a,b) (fabs((a)-(b)) < EPS)
#define COUNTER_CLOCKWISE 1
#define CLOCKWISE -1 
#define ONLINE_BACK 2
#define ONLINE_FRONT -2
#define ON_SEGMENT 0

using namespace std;


class Point{
public:
  double x,y;

  Point(double x = 0,double y = 0): x(x),y(y){}

  Point operator + (Point p){return Point(x+p.x,y+p.y);}
  Point operator - (Point p){return Point(x-p.x,y-p.y);}
  Point operator * (double a){return Point(a*x,a*y);}
  Point operator / (double a){return Point(x/a,y/a);}
  Point operator * (Point a){ return Point(x * a.x - y * a.y, x * a.y + y * a.x); }

  bool operator < (const Point& p) const{ return !equals(x,p.x)?x<p.x:(!equals(y,p.y)&&y<p.y); }

  bool operator == (const Point& p)const{ return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS; }

};

struct Segment{
  Point p1,p2;
  Segment(Point p1 = Point(),Point p2 = Point()):p1(p1),p2(p2){}
  bool operator <  (const Segment& s) const { return ( p2 == s.p2 ) ? p1 < s.p1 : p2 < s.p2; }
  bool operator == (const Segment& s) const { return ( s.p1 == p1 && s.p2 == p2 ) || ( s.p1 == p2 && s.p2 == p1 ); }

};

typedef Point Vector;
typedef Segment Line;
typedef vector<Point> Polygon;

ostream& operator << (ostream& os,const Point& a){ os << "(" << a.x << "," << a.y << ")"; }

ostream& operator << (ostream& os,const Segment& a){ os << "( " << a.p1 << " , " << a.p2 << " )"; }

double dot(Point a,Point b){ return a.x*b.x + a.y*b.y; }

double cross(Point a,Point b){ return a.x*b.y - a.y*b.x; }

double norm(Point a){ return a.x*a.x+a.y*a.y; }

double abs(Point a){ return sqrt(norm(a)); }

//rad は角度をラジアンで持たせること
Point rotate(Point a,double rad){ return Point(cos(rad)*a.x - sin(rad)*a.y,sin(rad)*a.x + cos(rad)*a.y); }

// 度をラジアンに変換
double toRad(double agl){ return agl*M_PI/180.0; }

// a => prev, b => cur, c=> next
// prev から cur へ行って next へ行く際の角度を求める
double getArg(Point a,Point b,Point c){
  double arg1 = atan2(b.y-a.y,b.x-a.x);
  double arg2 = atan2(c.y-b.y,c.x-b.x);
  double arg = fabs( arg1 - arg2 );
  while( arg > M_PI ) arg -= 2.0 * M_PI;
  return fabs(arg);
}

int ccw(Point p0,Point p1,Point p2){
  Point a = p1-p0;
  Point b = p2-p0;
  if(cross(a,b) > EPS)return COUNTER_CLOCKWISE;
  if(cross(a,b) < -EPS)return CLOCKWISE;
  if(dot(a,b) < -EPS)return ONLINE_BACK;
  if(norm(a) < norm(b))return ONLINE_FRONT;
  return ON_SEGMENT;
}

bool intersectLL(Line l, Line m) {
  return abs(cross(l.p2-l.p1, m.p2-m.p1)) > EPS || // non-parallel
         abs(cross(l.p2-l.p1, m.p1-l.p1)) < EPS;   // same line
}
bool intersectLS(Line l, Line s) {
  return cross(l.p2-l.p1, s.p1-l.p1)*       // s[0] is left of l
         cross(l.p2-l.p1, s.p2-l.p1) < EPS; // s[1] is right of l
}
bool intersectLP(Line l,Point p) {
  return abs(cross(l.p2-p, l.p1-p)) < EPS;
}
bool intersectSS(Line s, Line t) {
  return ccw(s.p1,s.p2,t.p1)*ccw(s.p1,s.p2,t.p2) <= 0 &&
         ccw(t.p1,t.p2,s.p1)*ccw(t.p1,t.p2,s.p2) <= 0;
}
bool intersectSP(Line s, Point p) {
  return abs(s.p1-p)+abs(s.p2-p)-abs(s.p2-s.p1) < EPS; // triangle inequality
}

Point projection(Line l,Point p) {
  double t = dot(p-l.p1, l.p1-l.p2) / norm(l.p1-l.p2);
  return l.p1 + (l.p1-l.p2)*t;
}
Point reflection(Line l,Point p) {
  return p + (projection(l, p) - p) * 2;
}
double distanceLP(Line l, Point p) {
  return abs(p - projection(l, p));
}
double distanceLL(Line l, Line m) {
  return intersectLL(l, m) ? 0 : distanceLP(l, m.p1);
}

double distanceLS(Line l, Line s) {
  if (intersectLS(l, s)) return 0;
  return min(distanceLP(l, s.p1), distanceLP(l, s.p2));
}
double distanceSP(Line s, Point p) {
  Point r = projection(s, p);
  if (intersectSP(s, r)) return abs(r - p);
  return min(abs(s.p1 - p), abs(s.p2 - p));
}

double distanceSS(Line s, Line t) {
  if (intersectSS(s, t)) return 0;
  return min(min(distanceSP(s, t.p1), distanceSP(s, t.p2)),
             min(distanceSP(t, s.p1), distanceSP(t, s.p2)));
}

Point crosspoint(Line l,Line m){
  double A = cross(l.p2-l.p1,m.p2-m.p1);
  double B = cross(l.p2-l.p1,l.p2-m.p1);
  if(abs(A) < EPS && abs(B) < EPS){
    vector<Point> vec;
    vec.push_back(l.p1),vec.push_back(l.p2),vec.push_back(m.p1),vec.push_back(m.p2);
    sort(vec.begin(),vec.end());
    assert(vec[1] == vec[2]); //同じセグメントかもよ
    return vec[1];
    //return m.p1;
  }
  if(abs(A) < EPS)assert(false);
  return m.p1 + (m.p2-m.p1)*(B/A);
}

double cross3p(Point p,Point q,Point r) { return (r.x-q.x) * (p.y -q.y) - (r.y - q.y) * (p.x - q.x); }

bool collinear(Point p,Point q,Point r) { return fabs(cross3p(p,q,r)) < EPS; }

bool onSegment(Point p,Point q,Point r){
  return collinear(p,q,r) && equals(sqrt(pow(p.x-r.x,2)+pow(p.y-r.y,2)) + sqrt(pow(r.x-q.x,2) + pow(r.y-q.y,2) ),sqrt(pow(p.x-q.x,2)+pow(p.y-q.y,2)) ) ;
}


bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

int N,M,B;
Polygon poly;
vector<double> pT,pVX,pVY;
vector<double> T,X,VX,VY,L;

const int IINF = INT_MAX;

Point vir;
bool comp_dist(const Point& p1,const Point& p2){ return LT(abs(vir-p2),abs(vir-p2)); }

double inner_function(Segment seg,Point p,double vx,double vy){
  const double TIME = 10000000;
  Segment arrow = Segment(p,p+Point(vx*TIME,vy*TIME));  
  if( !intersectSS(seg,arrow) ) return IINF;
  if( equals(cross(seg.p1-seg.p2,arrow.p1-arrow.p2),0.0) ) {
    if( onSegment(seg.p1,seg.p2,p) ) return 0;
    vector<Point> ps;
    ps.push_back(arrow.p2);
    ps.push_back(seg.p1);
    ps.push_back(seg.p2);
    vir = p;
    sort(ps.begin(),ps.end(),comp_dist);
    return TIME * abs(ps[0]-arrow.p1) / abs(arrow.p2-arrow.p1);
  } else {
    Point cp = crosspoint(seg,arrow);
    return TIME * abs(cp-arrow.p1) / abs(arrow.p2-arrow.p1);
  }
}

// 線分seg1 と線分seg2 が交差しなければ -1 を返す
double crossTimeSS(Segment seg1,double vx1,double vy1,
                   Segment seg2,double vx2,double vy2){
  double ret = IINF, temp;

  temp = inner_function(seg1,seg2.p1,vx2-vx1,vy2-vy1);
  if( LT(temp,ret) ) ret = temp;

  temp = inner_function(seg1,seg2.p2,vx2-vx1,vy2-vy1);
  if( LT(temp,ret) ) ret = temp;

  temp = inner_function(seg2,seg1.p1,vx1-vx2,vy1-vy2);
  if( LT(temp,ret) ) ret = temp;

  temp = inner_function(seg2,seg1.p2,vx1-vx2,vy1-vy2);
  if( LT(temp,ret) ) ret = temp;
  
  return equals(ret,IINF) ? -1 : ret;
}

Point move(Point p,double vx,double vy,double t){ return Point(p.x+vx*t,p.y+vy*t); }

void compute(){
  vector<double> answer;
  rep(i,B){
    vector<Point> hit;
    rep(j,N){

      Segment bullet = Segment(Point(X[i],0),Point(X[i]-((L[i]*VX[i])/sqrt(VX[i]*VX[i]+VY[i]*VY[i])),
                                                0-((L[i]*VY[i])/sqrt(VX[i]*VX[i]+VY[i]*VY[i]))));

      Segment vline = Segment(poly[j],poly[(j+1)%N]);

      bool First = true;
      double cur = -1;
      rep(k,(int)pT.size()-1){
        if( !( First && !( LTE(pT[k],T[i]) && LTE(T[i],pT[k+1]) ) ) ) {
          Segment seg = vline;
          if( First ) {
            cur = T[i];
            seg = Segment(move(seg.p1,pVX[k],pVY[k],T[i]-pT[k]),
                          move(seg.p2,pVX[k],pVY[k],T[i]-pT[k]));
          }
          First = false;
        
          double hit_time = crossTimeSS(bullet,VX[i],VY[i],
                                        seg,pVX[k],pVY[k]);
          if( !equals(hit_time,-1) ) {
            if( LTE(pT[k],cur+hit_time) && LTE(cur+hit_time,pT[k+1]) ) {
              hit.push_back(Point(cur+hit_time,0));
              break;
            }
          }
          assert( !equals(cur,-1) );
          bullet = Segment(move(bullet.p1,VX[i],VY[i],pT[k+1]-cur),
                           move(bullet.p2,VX[i],VY[i],pT[k+1]-cur));
          cur = pT[k+1];
        }
        vline = Segment(move(vline.p1,pVX[k],pVY[k],pT[k+1]-pT[k]),
                        move(vline.p2,pVX[k],pVY[k],pT[k+1]-pT[k]));
      }
    }
    if( !hit.empty() ) {
      sort(hit.begin(),hit.end());
      hit.erase(unique(hit.begin(),hit.end()),hit.end());
      answer.push_back(hit[0].x);
    }
  }
  sort(answer.begin(),answer.end());
  printf("%d\n",(int)answer.size());
  rep(i,(int)answer.size()) printf("%.10f\n",answer[i]);
}

int main(){
  while( cin >> N >> M >> B, N|M|B ){
    poly.clear();
    poly.resize(N);
    rep(i,N) cin >> poly[i].x >> poly[i].y;
    pT.clear(), pVX.clear(), pVY.clear();
    
    pT.push_back(0);
    rep(i,M) {
      double a,b,c;
      cin >> a >> b >> c;
      pT.push_back(a), pVX.push_back(b), pVY.push_back(c);
    }
    pT.push_back(10000000), pVX.push_back(0), pVY.push_back(0);

    T.clear(), X.clear(), VX.clear(), VY.clear(), L.clear();
    T.resize(B), X.resize(B), VX.resize(B), VY.resize(B), L.resize(B);
    rep(i,B) cin >> T[i] >> X[i] >> VX[i] >> VY[i] >> L[i];
    compute();
  }
  return 0;
}