クレインは, 彼女の愛犬である 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 枚目のフリスビーが取得されると大会は終了する.
言うまでもなく, 犬たちの目標はより多くのフリスビーを取得することである. 犬たちは, 以下のような戦略をとる.
フリスビーが発射されたとき, 犬は可能な限り早い時刻にそれを取得できるように移動し, フリスビーを取得する. ただし, フリスビーを取得できないときは現在いる場所に待機する.
ある犬がフリスビーを取得できるかどうかの判断は, 他の犬の行動に関係なく行われる. つまり, ある犬がフリスビーを取得するために移動したものの, 他の犬に先に取得されてしまうことも有りえる. いずれかの犬がフリスビーを取得し新たなフリスビーが発射された瞬間, 犬たちは新しいフリスビーに対して上記の戦略をとる.
あなたの作成するプログラムは、それぞれの犬が取得したフリスビーの数を出力しなければならない.
入力ファイルは, 複数のデータセットから構成される.
データセットの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 のとき入力の終わりを示す.
それぞれの犬が取得したフリスビーの数を, 空白文字で区切って1行に出力せよ. 出力する順番は, 入力で与えられた順番と等しくなければならない.
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
1 0 2 1