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 <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <ctime>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <unordered_map>
#include <iterator>
#include <functional>
#include <cassert>
using namespace std;
typedef long long int ll;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
#define ALL(container) (container).begin(), (container).end()
#define RALL(container) (container).rbegin(), (container).rend()
#define SZ(container) ((int)container.size())
#define mp(a,b) make_pair(a, b)
#define pb push_back
#define eb emplace_back
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"["; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"]"; return os;
}
template<class T> ostream& operator<<(ostream &os, const set<T> &t) {
os<<"{"; FOR(it,t) {if(it!=t.begin()) os<<","; os<<*it;} os<<"}"; return os;
}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class S, class T> pair<S,T> operator+(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first+t.first, s.second+t.second);}
template<class S, class T> pair<S,T> operator-(const pair<S,T> &s, const pair<S,T> &t){ return pair<S,T>(s.first-t.first, s.second-t.second);}

namespace geom{
#define X real()
#define Y imag()
#define at(i) ((*this)[i])
#define SELF (*this)
	enum {TRUE = 1, FALSE = 0, BORDER = -1};
	typedef int BOOL;
	typedef double R;
	const R INF = 1e8;
	R EPS = 1e-4;
	const R PI = 3.1415926535897932384626;
	inline int sig(const R &x) { return (abs(x) < EPS ? 0 : x > 0 ? 1 : -1); }
	inline BOOL less(const R &x, const R &y) {return sig(x-y) ? x < y : BORDER;}
	typedef complex<R> P;
	inline R norm(const P &p){return p.X*p.X+p.Y*p.Y;}
	inline R inp(const P& a, const P& b){return (conj(a)*b).X;}
	inline R outp(const P& a, const P& b){return (conj(a)*b).Y;}
	inline P unit(const P& p){return p/abs(p);}
	inline P proj(const P &s, const P &t){return t*inp(s, t)/norm(t);}
	inline int ccw(const P &s, const P &t, const P &p, int adv=0){
		int res = sig(outp(t-s, p-s));
		if(res || !adv) return res;
		if(sig(inp(t-s, p-s)) < 0) return -2;	// p-s-t
		if(sig(inp(s-t, p-t)) < 0) return 2;	// s-t-p
		return 0;								// s-p-t
	}
	
	
	struct L : public vector<P>{	// line
		L(const P &p1, const P &p2){this->push_back(p1);this->push_back(p2);}
		L(){}
		P dir()const {return at(1) - at(0);}
		BOOL online(const P &p)const {return !sig(outp(p-at(0), dir()));}
	};
	struct S : public L{	// segment
		S(const P &p1, const P &p2):L(p1, p2){}
		S(){}
		BOOL online(const P &p)const {
			if(!sig(norm(p - at(0))) || !sig(norm(p - at(1)))) return BORDER;
			// ??§?¨????????????¨EPS???????????§??????????????????????????¨???
			return !sig(outp(p-at(0), dir())) && inp(p-at(0), dir()) > EPS && inp(p-at(1), -dir()) > -EPS;
			//return !sig(abs(at(0)-p) + abs(at(1) - p) - abs(at(0) - at(1)));
		}
	};
	struct C : public P{
		C(){}
		C(const P& p, const R r):P(p), r(r){}
		R r;
		BOOL inside(const P& p)const { return less(norm(p-SELF), r*r);}
	};

	inline P proj(const P &s, const L &t){return t[0] + proj(s-t[0], t[1]-t[0]);}
	inline P reflect(const P &s, const L &t){return (R)2.*proj(s, t) - s;}
	inline S reflect(const S &s, const L &t){return S(reflect(s[0], t), reflect(s[1], t));}
	BOOL intersect(const S &s, const S &t){
		const int p = ccw(t[0], t[1], s[0], 1) * ccw(t[0], t[1], s[1], 1);
		const int q = ccw(s[0], s[1], t[0], 1) * ccw(s[0], s[1], t[1], 1);
		return (p>0||q>0) ? FALSE : (!p||!q) ? BORDER : TRUE;
	}
	BOOL intersect(const S &s, const L &l){
		if(l.online(s[0]) || l.online(s[1])) return BORDER;
		return (sig(outp(l.dir(), s[0]-l[0])) * sig(outp(l.dir(), s[1]-l[0])) <= 0);
	}
	R dist2(const L &l, const P &p){return norm(outp(l.dir(), p - l[0])) / norm(l.dir());}
	R dist2(const S &s, const P &p){
		if(inp(p-s[0],  s.dir()) < EPS) return norm(p - s[0]);
		if(inp(p-s[1], -s.dir()) < EPS) return norm(p - s[1]);
		return dist2((const L &)s, p);
	}
	R dist2(const S &s, const L &l){
		return intersect(s, l) ? .0 : min(dist2(l, s[0]), dist2(l, s[1]));
	}
	R dist2(const S &s, const S &t){
		return intersect(s, t) ? .0 : min(min(dist2(s, t[0]), dist2(t, s[0])), 
									   	  min(dist2(s, t[1]), dist2(t, s[1])));
	}
	template<class S, class T> R dist(const S& s, const T& t){return sqrt(dist2(s, t));}
	inline BOOL intersect(const C &a, const C &b){
		return less((a.r-b.r)*(a.r-b.r), norm(a-b)) + less(norm(a-b), (a.r+b.r)*(a.r+b.r)) - 1;
	}
	inline P crosspoint(const L &l, const L &m){
		R A = outp(l.dir(), m.dir()), B = outp(l.dir(), l[1] - m[0]);
		if(!sig(abs(A)) && !sig(abs(B))) return m[0]; // same line
		if(abs(A) < EPS) assert(false); // !!!PRECONDITION NOT SATISFIED!!!
		return m[0] + B / A * (m[1] - m[0]);
	}
	
	template<class Func> R simpson(R s, R t, Func func){
		return (t-s)/6*(func(s+2*EPS) + func(t-2*EPS) + 4*func((s+t)*(R).5));
	}

#undef SELF
#undef at
}

using namespace geom;

int f = 0;
namespace std{
	bool operator<(const P &a, const P &b){return sig(a.X-b.X) ? a.X < b.X : a.Y+EPS < b.Y;}
	bool operator==(const P &a, const P &b){return abs(a-b) < EPS;}
	istream& operator>>(istream &is, P &p){R x,y;is>>x>>y;p=P(x, y);return is;}
	istream& operator>>(istream &is, L &l){l.resize(2);return is >> l[0] >> l[1];}
	istream& operator>>(istream &is, C &c){return is >> (P &)c >> c.r;}
	const R B = 500;
	const R Z = 2;
//	ostream& operator<<(ostream &os, const C &c){return os << "circle("<<B+Z*(c.X)<<", "<<1000-B-Z*(c.Y)<<", "<<Z*(c.r)<<")";}
//	ostream& operator<<(ostream &os, const P &p){return os << "circle("<<B+Z*(p.X)<<", "<<1000-B-Z*(p.Y)<<", 2)";}
//	ostream& operator<<(ostream &os, const S &s){return os << "line("<<B+Z*(s[0].X)<<", "<<1000-B-Z*(s[0].Y)<<", "<<B+Z*(s[1].X)<<", "<<1000-B-Z*(s[1].Y)<<")";}

}

struct G : public vector<P>{
	P v;
	R l, r;
	
	G(size_type size=0):vector(size){}
	S edge(int i)const {return S(at(i), at(i+1 == size() ? 0 : i+1));}
	S edge(int i, R t)const {return S(at(i)+v*t, at(i+1 == size() ? 0 : i+1)+v*t);}
};

int T, n, m, b;

R conflict(P p1, P p2, P p3, P v, R l, R r){
	if(r + EPS < l) return INF;
	R o = outp(p2-p1, v);
	R res = INF;
	if(!ccw(p1, p2, p3 + v*l, 1)) return l;
	do{
		if(abs(o) < EPS){
			if(abs(outp(p2 - p1, p3 - p1)) > EPS) break;
			res = min(abs(p1-p3), abs(p2-p3))/abs(v);
		}else res = -outp(p2 - p1, p3 - p1) / o;
		if(res > INF - EPS || res < l - EPS || r + EPS < res) break;
		if(ccw(p1, p2, p3 + v*res, 1)) break;
		return res;
	}while(0);
	return INF;
}

R conflict(G a, G b){
	R ans = INF;
	REP(i, a.size())REP(j, b.size()){
		R res = conflict(a[i], a[(i+1) % a.size()], b[j], b.v-a.v, max(a.l, b.l), min(a.r, b.r));
		ans = min(ans, res);
	}
	return ans;
}

int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	while(cin >> n >> m >> b, n){
		G g(n);
		vector<G> polys;
		REP(i, n) cin >> g[i];
		R pt = 0;
		REP(i, m){
			R t;
			P v;
			polys.pb(g);
			cin >> t >> v;
			for(auto &p : polys[i]) p -= v*pt;
			polys[i].v = v; polys[i].l = pt; polys[i].r = t;
			for(auto &p : g) p += v*(t-pt);
			pt = t;
		}
		polys.pb(g);
		polys[m].v = P(0, 0);
		polys[m].l = pt;
		polys[m].r = INF;
		vector<R> ans;
		REP(i, b){
			P p, v;
			R x, t, l;
			cin >> t >> x >> v >> l;
//			cout << "!" << t << " " << x << " " << v << " " << l << endl;
			p = P(x, 0) - v*t;
			G bullet(2);
			bullet[0] = p;
			bullet[1] = p - unit(v)*l;
			bullet.v = v;
			bullet.l = t;
			bullet.r = INF;
			R res = INF;
			REP(j, m+1) res = min(res, min(conflict(polys[j], bullet), conflict(bullet, polys[j])));
			if(res < INF-EPS) ans.pb(res);
		}
		sort(ALL(ans));
		printf("%d\n", (int)ans.size());
		REP(i, ans.size()) printf("%.15f\n", (double)ans[i]);
	}
	return 0;
}