Frisbee Dogs

Time Limit : 5 sec, Memory Limit : 65536 KB

Problem E: Frisbee Dogs

クレインは, 彼女の愛犬である Jack をフリスビードッグ大会に出場させようとしている. しかし, 彼女は Jack がよい成績を取れるか自信が無い. 彼女のために, 大会をシミュレートして Jack の成績を見積もるプログラムを作成してほしい.

この大会は, 2次元平面上にいる N 匹の犬によって行われる. 大会の開始時点において, i 番目の犬は (Dix, Diy) の位置にいる. i 番目の犬は Vi [m/s] で走ることができ, 全ての犬は十分小さいので点とみなせる. ある時刻に, 2 匹以上の犬が同じ位置にいても構わない.

1枚目のフリスビーの発射をもって大会は開始し, この瞬間から犬たちは動くことを許される. フリスビーもまた点とみなすことができ, i 枚目のフリスビーは (FPix, FPiy) の位置から (FVix, FViy) [m/s] の速度ベクトルで発射され, 等速直線運動を続ける. ある犬の位置とフリスビーの位置が等しくなったとき, その犬はフリスビーを取得することができる.

1枚目のフリスビーがいずれかの犬に取得された瞬間, 2枚目のフリスビーが発射される. 2枚目のフリスビーが取得された瞬間3枚目が発射され, 以下同様にフリスビーが取得された直後に次のフリスビーが発射される. M 枚目のフリスビーが取得されると大会は終了する.

言うまでもなく, 犬たちの目標はより多くのフリスビーを取得することである. 犬たちは, 以下のような戦略をとる.

フリスビーが発射されたとき, 犬は可能な限り早い時刻にそれを取得できるように移動し, フリスビーを取得する. ただし, フリスビーを取得できないときは現在いる場所に待機する.

ある犬がフリスビーを取得できるかどうかの判断は, 他の犬の行動に関係なく行われる. つまり, ある犬がフリスビーを取得するために移動したものの, 他の犬に先に取得されてしまうことも有りえる. いずれかの犬がフリスビーを取得し新たなフリスビーが発射された瞬間, 犬たちは新しいフリスビーに対して上記の戦略をとる.

あなたの作成するプログラムは、それぞれの犬が取得したフリスビーの数を出力しなければならない.

Input

入力ファイルは, 複数のデータセットから構成される.

データセットの1行目には, 犬の数 N (1 ≤ N ≤ 10) とフリスビーの数 M (1 ≤ M ≤ 1000)が与えられる.

続く N 行には, 犬の初期位置と速度 Dix, Diy, Vi が1つの空白区切りで与えられる.

続く M 行には, フリスビーの発射位置と速度 FPix, FPiy, FVix, FViy が1つの空白文字区切りで与えられる.

与えられる座標値は実数であり、その絶対値は 1000 を越えない. 与えられる速度は実数であり 1 ≤ DVi ≤ 100, -25 ≤ FVix, FViy ≤ 25 である. どの犬にも取得できないフリスビーはないと仮定してよい.

任意のフリスビーがある犬に時刻 t で取得されたとき、時刻 t + 1e-6 以前にそれを取得できる犬はいない.

シミュレーションの間, 犬の x 座標, y 座標の絶対値は 1e+8 を越えない.

N, M がともに 0 のとき入力の終わりを示す.

Output

それぞれの犬が取得したフリスビーの数を, 空白文字で区切って1行に出力せよ. 出力する順番は, 入力で与えられた順番と等しくなければならない.

Sample Input

2 1
12 5 3
0 17 3
0 0 2 2
2 3
2 0 2
100 100 2
0 0 -1 0
-2 -5 0 3
100 100 1 1
0 0

Output for the Sample Input

1 0
2 1

Source: University of Aizu, ACM-ICPC Japan Domestic Contest 2009 Warm Up II , Aizu-Wakamatsu, Japan, 2009-06-28
Problem Setter:  Takashi Tayama