Problem: Some of you know an old story of Voronoi Island. There were N liege lords and they are always involved in territorial disputes. The residents of the island were despaired of the disputes.

One day, a clever lord proposed to stop the disputes and divide the island fairly. His idea was to divide the island such that any piece of area belongs to the load of the nearest castle. The method is called Voronoi Division today.

Actually, there are many aspects of whether the method is fair. According to one historian, the clever lord suggested the method because he could gain broader area than other lords.

Your task is to write a program to calculate the size of the area each lord can gain. You may assume that Voronoi Island has a convex shape.



Input

The input consists of multiple datasets. Each dataset has the following format:

N M
Ix1 Iy1
Ix2 Iy2
...
IxN IyN
Cx1 Cy1
Cx2 Cy2
...
CxM CyM


N is the number of the vertices of Voronoi Island; M is the number of the liege lords; (Ixi, Iyi) denotes the coordinate of the i-th vertex; (Cxi, Cyi ) denotes the coordinate of the castle of the i-the lord.

The input meets the following constraints: 3 ≤ N ≤ 10, 2 ≤ M ≤ 10, -100 ≤ Ixi, Iyi, Cxi, Cyi ≤ 100. The vertices are given counterclockwise. All the coordinates are integers.

The last dataset is followed by a line containing two zeros. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print the area gained by each liege lord with an absolute error of at most 10-4 . You may output any number of digits after the decimal point. The order of the output areas must match that of the lords in the input.

Example

Input

3 3
0 0
8 0
0 8
2 2
4 2
2 4
0 0


Output

9.0
11.5
11.5

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

#define EPS (1e-10)
#define PI (3.141592653589793238462643383279)
template<class T>
struct point{
	T x, y;
	point &operator+=(const point &a ){ x += a.x; y += a.y; }
	point &operator-=(const point &a ){ x -= a.x; y -= a.y; }
	point operator+(const point &a )const{ return (point){x+a.x, y+a.y }; }
	point operator-(const point &a )const{ return (point){x-a.x, y-a.y }; }
	operator point<double>()const{ return (point<double>){x, y }; }
};

template<class T>
point<T> operator*(T c, const point<T> &a ){ return (point<T>){c*a.x, c*a.y }; }
point<double> &operator/=(point<double> &a, double c ){ a.x /= c; a.y /= c; return a; }
template<class T>
point<double> operator/(const point<T> &a, double c ){ return (point<double>){ a.x/c, a.y/c }; }

// for integar number
template<class T>
bool operator<(const point<T> &a, const point<T> &b ){
	return (a.x < b.x || ((a.x == b.x ) && (a.y < b.y ) ) );
}

template<class T>
bool operator==(const point<T> &a, const point<T> &b ){
	return a.x == b.x && a.y == b.y;
} 

template<class T>
bool operator!=(const point<T> &a, const point<T> &b ){
	return a.x != b.x || a.y != b.y;
}

//  for real number
bool operator<(const point<double> &a, const point<double> &b ){
	return (a.x + EPS < b.x || (abs (a.x - b.x ) < EPS && (a.y + EPS < b.y ) ) );
}

bool operator==(const point<double> &a, const point<double> &b ){
	return abs (a.x - b.x) < EPS && abs (a.y - b.y ) < EPS;
}

bool operator!=(const point<double> &a, const point<double> &b ){
	return abs (a.x - b.x ) > EPS || abs (a.y - b.y ) > EPS;
}

// inner product
template<class T>
T dot(const point<T> &a, const point<T> &b ){ return a.x*b.x + a.y*b.y; }

// outer product
template<class T>
T cross(const point<T> &a, const point<T> &b ){ return a.x*b.y - a.y*b.x; }

// distance between origin(0,0) to point a
template<class T>
double abs(const point<T> &a ){ return sqrt (a.x*a.x + a.y*a.y ); }

template<class T>
T abs2(const point<T> &a ){ return a.x*a.x + a.y*a.y; }

point<double> rot(const point<double> &a, double theta ){
	return (point<double>){a.x*cos(theta) - a.y*sin(theta), a.x*sin(theta) + a.y*cos(theta ) };
}

// x 軸の正方向を基準とした場合のベクトル a の角度を [0, 2*PI) の範囲で求める
template<class T> double arg(const point<T> &a ){
	double t = atan2(a.y, a.x );
	return t<0.? t+2.*PI : t;
}

template<class T>
struct line{
	point<T> a, b;
	operator line<double>()const{ return (line<double>){a, b}; }
};

template<class T>
struct segment{
	point<T> a, b;
	operator line<T>()const { return (line<T>){a,b}; }
};

template<class T>
struct polygon:vector< point<T> >{
	polygon(){}
	polygon(int n ):vector< point<T> >(n){}
};

template<class T>
struct circle{
	point<T> c;
	T r;
};

// 点 p を直線 L 上に射影した点を求める
// 	Verified: AOJ 0081 A Symmetric Point
template<class T>
point<double> proj(const point<T> &p, const line<T> &L ){
	return L.a + dot (p-L.a, L.b-L.a )/abs2 (L.b - L.a )*(L.b - L.a );
}

/*
	三角形の面積（外積）

	説明
		三頂点で定まる三角形の面積（の２倍）を求める
	引数
		a : 頂点
		b : 頂点
		c : 頂点
	戻り値
		三角形の面積の２倍
		縮退しているときは 0
	制約
		なし
	計算量
		O(1)
	備考
		２倍を返しているのは、座標値が整数のときにはこの値も整数になるから。
*/
template<class T>
T area2(const point<T> &a, const point<T> &b, const point<T> &c ){
	return abs(cross(b-a,c-a));
}
/*
	三角形の面積（Heron）

	説明
		三辺の長さで定まる三角形の面積を求める
	引数
		a : 一辺の長さ
		b : 一辺の長さ
		c : 一辺の長さ
	戻り値
		三角形の面積
		三角形が作れないとき、縮退しているときには 0
	制約
		a>=0, b>=0, c>=0
		a<b+c, b<c+a, c<a+b（三角形の成立条件）
	計算量
		O(1)
	備考
		三角形が縮退しているときは nan を返すかもしれない
*/
double area(double a, double b, double c ){
	return sqrt((a+b-c)*(b+c-a)*(c+a-b)*(a+b-c))/4.;
}

/*
	多角形の面積

	説明
		多角形の面積（２倍）を求める
	引数
		G : 多角形
	戻り値
		三角形の面積の２倍
		縮退しているときは 0
	制約
		G は単純
	計算量
		O(n)
	備考
		２倍を返しているのは、座標値が整数のときにはこの値も整数になるから。
		多角形は CCW でも CW でもよい

		Verified: AOJ 0079 Area of Polygon
*/
template<class T>
T area2(const polygon<T> &G ){
	int n = G.size();
	T a = 0;
	rep (i, n ) a+=cross(G[i], G[(i+1)%n] );
	return abs (a );
}

/*
	二円の共通部分の面積を求める
*/

/*
	回転方向

	説明
		３点の位置関係を求める
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		a : 点
		b : 点
		c : 点
	戻り値
		a-b-c の順に反時計回りに回転しているとき CCW
		a-b-c の順に時計回りに回転しているとき CW
		a-b-c が同一直線上にあるとき ON
	制約
		なし
	計算量
		O(1)
	備考
		2 点以上が同一の点であれば常に ON を返すことに注意

*/

// (A)
enum{CCW = 1, CW = -1, ON = 0 };
template<class T>
int ccw(const point<T> &a, const point<T> &b, const point<T> &c ){
	T rdir = cross (b-a, c-a );
	if (rdir > 0 ) return CCW;
	if (rdir < 0 ) return CW;
	return ON;
}

// (B)

//enum{CCW = 1, CW = -1, ON = 0 };
int ccw (const point<double> &a, const point<double> &b, const point<double> &c ){
	double rdir = cross (b-a, c-a );
	if (rdir > 0 ) return CCW;
	if (rdir < 0 ) return CW;
	return ON;
}

/*
	反時計回りに変換

	説明
		多角形の頂点の順番が CW であれば CCW に変換する
		元々 CCW であれば何もしない
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		G : 多角形
	戻り値
		なし（引数 G が更新される）
	制約
		G は単純
	計算量
		O(n)
	備考
		単純多角形とは自己交差しない多角形のこと
		Verified: AOJ 0035 Is it Convex?
*/
// (A)
template<class T>
void to_ccw(polygon<T> &G ){
	int n = G.size();
	T A = 0;
	rep (i, n ) A+=cross(G[i], G[(i+1)%n] );
	if (A < 0 ) reverse (ALL (G ) );
}

// (B)
void to_ccw(polygon<double> &G ){
	int n = G.size();
	double A = 0.;
	rep (i, n ) A+=cross(G[i], G[(i+1)%n] );
	if (A<-EPS ) reverse (ALL (G ) );
}

/*
	点と点の距離

	説明
		点と点の距離を求める
		dist : 距離そのもの
		dist2 : 距離の二乗
	引数
		a : 点
		b : 点
	戻り値
		点 a と 点 b の距離
	制約
		なし
	計算量
		O(1)
	備考
*/
template<class T>
double dist(const point<T> &a, const point<T> &b ){
	return sqrt ((a.x - b.x )*(a.x - b.x ) + (a.y - b.y )*(a.y - b.y ) );
}

template<class T>
T dist2(const point<T> &a, const point<T> &b ){
	return (a.x - b.x )*(a.x - b.x ) + (a.y - b.y )*(a.y - b.y );
}

/*
	直線と点の距離
点と
	説明
		直線と点の距離を求める
		dist : 距離そのもの
		dist2 : 距離の二乗
	引数
		L : 直線
		p : 点
	戻り値
		直線 L と点 p の距離
	制約
		なし
	計算量
		O(1)
	備考

*/
template<class T>
double dist(const line<T> &L, const point<T> &p ){
	return abs (cross (L.b-L.a, p-L.a))/dist(L.a, L.b );
}

/*
	線分と点の距離

	説明
		線分と点の距離を求める
		dist : 距離そのもの
		dist2 : 距離の２乗
	引数
		S : 線分
		p : 点
	戻り値
		線分 S と点 p の距離
	計算量
		O(1)
	備考
		dist2 は <= 0 で正しい。(ESP を使わなくてよい. )
	
*/
template<class T>
double dist(const segment<T> &S, const point<T> &p ){
	if (dot (S.b-S.a, p-S.a ) <= 0 ) return dist (p, S.a );
	if (dot (S.a-S.b, p-S.b ) <= 0 ) return dist (p, S.b );
	return abs (cross (S.b-S.a, p - S.a ) )/dist (S.a, S.b );
}

template<class T>
double dist2(const segment<T> &S, const point<T> &p ){
	if (dot (S.b-S.a, p-S.a ) <= 0 ) return dist2 (p, S.a );
	if (dot (S.a-S.b, p-S.b ) <= 0 ) return dist2 (p, S.b );
	return (double)cross (S.b-S.a, p - S.a )*cross (S.b-S.a, p - S.a )/dist (S.a, S.b );
}
/*
	二直線の交点

	説明
		二直線の交点を求める
		(A)（直線を特徴付ける点の）座標値が整数
		(B)（直線を特徴付ける点の）座標値が実数
	引数
		L1 : 直線
		L2 : 直線
	戻り値
		L1 と L2 の交点
	制約
		二直線は交点を持つこと。（平行でない or L1 == L2 )
	計算量
		O(1)
	備考
		交点が複数あるとき（L1 == L2）は L1.a を返す。
		この仕様は線分 S と直線 L の交点を求めたいとき重要。
		（ S と L が同一直線上にあるときにも、S を第１引数に指定することで交点が正しく求まる。）
*/
// (A)
template<class T>
point<double> get_intersect(const line<T> &L1, const line<T> &L2 ){
	double a1=cross(L1.b-L1.a,L2.b-L2.a);
	double a2=cross(L1.b-L1.a,L1.b-L2.a);
	if (a1==0) return L1.a;	// L1 == L2
	return (point<double>)L2.a+a2/a1*(point<double>)(L2.b-L2.a);
}
// (B)
point<double> get_intersect(const line<double> &L1, const line<double> &L2 ){
	double a1=cross(L1.b-L1.a,L2.b-L2.a);
	double a2=cross(L1.b-L1.a,L1.b-L2.a);
	if (abs(a1)<EPS) return L1.a;	// L1 == L2
	return L2.a+a2/a1*(L2.b-L2.a);
}

/*
	線分と線分の交差判定

	説明
		線分と線分が交わるかどうかを判定する
		(A) 座標値が整数
		(B) 座標値が実数
	引数
		S1 : 線分
		S2 : 線分
	戻り値
		交わるなら true, 交わらないなら false
	制約
		なし
	計算量
		O(1)
	備考
		bounding box によるラフチェックは必要。（ ccw による判定だと、二線分が同一直線上にあるとき間違う。)

		Verified: AOJ 2003 Railroad Conflict
*/
// (A)
template<class T>
bool intersect(const segment<T> &S1, const segment<T> &S2 ){
	if (max (S1.a.x, S1.b.x ) < min (S2.a.x, S2.b.x )
	|| max (S1.a.y, S1.b.y ) < min (S2.a.y, S2.b.y )
	|| max (S2.a.x, S2.b.x ) < min (S1.a.x, S1.b.x )
	|| max (S2.a.y, S2.b.y ) < min (S1.a.y, S1.b.y ) ) return false;
	return ccw (S1.a, S1.b, S2.a )*ccw (S1.a, S1.b, S2.b ) <= 0
		&& ccw (S2.a, S2.b, S1.a )*ccw (S2.a, S2.b, S1.b ) <= 0;
}

/*
	垂直二等分線

	説明
		二点 a, b の垂直二等分線を求める
	引数
		a : 点
		b : 点
	戻り値
		a と b の垂直二等分線
	計算量
		O(1)
	備考
		垂直二等分線を L とすると、L.a から L.b の方向を見たとき、左手に点 a が来る。
		AOJ 0081 A_Symmetric_Point では上手く動かなかった。

*/
template<class T>
line<double> perp_bisector(const point<T> &a, const point<T> &b ){
	return (line<double>){(point<double>){(a.x-a.y+b.x+b.y)/2.0, (a.y+a.x+b.y-b.x)/2.0 },
							(point<double>){(a.x+a.y+b.x-b.y)/2.0, (a.y-a.x+b.y+b.x)/2.0 }};
}

/*
	凸多角形の切断

	凸多角形と半平面の交差

	説明
		凸多角形と半平面の共通部分を求める
	引数
		G : 凸多角形
		L : 直線
	戻り値
		G と L の左側の半平面の共通部分
	制約
		なし
	計算量
		O(n)
	備考
		半平面は L.a から L.b へ向いたときの左側の部分として指定されている。
		共通部分は凸多角形になる。（凸集合の全体は intersection について閉じている。）
		L 上に G の点 p があっても、出力される多角形には p が一度だけ表れる。

*/
template<class T>
polygon<double> convex_cut(const polygon<T> &G, const line<T> &L ){
	int n=G.size();
	polygon<double> H; H.clear();
	rep (i, n ){
		int d1=ccw(L.a,L.b,G[i] );
		int d2=ccw(L.a,L.b,G[(i+1)%n] );
		if (d1!=CW )H.push_back(G[i] );
		if (d1==CCW && d2==CW || d1==CW && d2==CCW ){
			H.push_back (get_intersect(L,(line<T>){G[i],G[(i+1)%n]}));
		} // end if
	} // end rep

	return H;
}

/*
	ボロノイ図

	説明
		k番目の点のボロノイ領域を求める
	引数
		g : 多角形（外枠）
		v : 点の集合
		k : 点の集合の中の k 番目の点	
	戻り値
		res : 多角形
	制約
		多角形 g は反時計回りに配置されている事が前提。
		外枠が凸多角形でないときも動く？
		g は破壊される。
		(多角形の切断で g は書き換えられるため。)
	計算量
		O(n*(n+m))
	備考
	
*/
template<class T>
polygon<T> voronoi_cell(polygon<T> g, const polygon<T> &v, int k ){
	int n = v.size();
	rep (i, n ) if (i != k ) g = convex_cut (g, perp_bisector (v[k], v[i] ) );

	return g;
}
int main()
{
//	cut here before submit 
//	freopen ("testcase.2160", "r", stdin );
	int n, m;
	while (scanf ("%d %d", &n, &m ), n, m ){
		polygon<double> g(n );
		rep (i, n ) scanf ("%lf %lf", &g[i].x, &g[i].y );
		polygon<double> v(m );
		rep (j, m ) scanf ("%lf %lf", &v[j].x, &v[j].y );
		rep (j, m ){
			polygon<double> tg = g;
			polygon<double> ans = voronoi_cell (tg, v, j );
			double res = area2 (ans );
			printf ("%.5lf\n", res/2. );
		} // end rep
	} // end loop
		
	return 0;
}