Problem: Klein is trying to get her dog Jack into the Frisbee Dog Tournament. But she's not sure if Jack will get a good grade. For her, she simulates the tournament to get Jack's grade. I want you to create a program to estimate.

The tournament is held by N dogs on a two-dimensional plane. At the start of the tournament, the i-th dog is in the (Dix, Diy) position. The i-th dog is Vi [m / s] All dogs are small enough to be considered points. At any given time, two or more dogs may be in the same position.

The tournament begins with the launch of the first Frisbee, from which the dogs are allowed to move. Frisbee can also be considered a point, the i Frisbee from the (FPix, FPiy) position ( FVix, FViy) Fired at a velocity vector of [m / s] and continues a constant velocity linear motion. When a dog's position and a Frisbee's position are equal, the dog can get a Frisbee.

The moment the first Frisbee is acquired by one of the dogs, the second Frisbee is fired. The moment the second Frisbee is acquired, the third is fired, and so on. Immediately after, the next Frisbee will be fired. The tournament will end when the Mth Frisbee is acquired.

Needless to say, the dogs' goal is to get more Frisbee. Dogs take the following strategies.

When the Frisbee is fired, the dog moves to get it at the earliest possible time and gets the Frisbee. However, if it cannot get the Frisbee, it waits where it is.

The determination of whether a dog can get a frisbee is made regardless of the behavior of the other dog. That is, one dog moves to get a frisbee, but the other dog gets it first. The moment one of the dogs gets the Frisbee and a new Frisbee is launched, the dogs take the above strategy against the new Frisbee.

The program you create must output the number of Frisbees obtained by each dog.



Input

The input file consists of multiple datasets.

The first row of the dataset gives the number of dogs N (1 ≤ N ≤ 10) and the number of Frisbees M (1 ≤ M ≤ 1000).

The following N lines are given the dog's initial position and velocity Dix, Diy, Vi, separated by a single blank.

The following M lines are given the Frisbee launch position and velocity FPix, FPiy, FVix, FViy, separated by a single space character.

The coordinate values ​​given are real numbers and their absolute values ​​do not exceed 1000. The speeds given are real numbers 1 ≤ DVi ≤ 100, -25 ≤ FVix, FViy ≤ 25. Frisbees that cannot be obtained by any dog You can assume that there is no.

When a dog with any Frisbee was obtained at time t, no dog could get it before time t + 1e-6.

During the simulation, the absolute values ​​of the dog's x and y coordinates do not exceed 1e + 8.

When both N and M are 0, the end of input is indicated.

Output

Output the number of Frisbees obtained by each dog on one line separated by a space character. The order of output must be the same as the order given in the input.

Example

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

1 0
2 1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

// ベクトル
namespace Geom {

    const double eps = 1e-9;

    struct Point {
        double x, y;
        explicit Point(double x=0, double y=0): x(x), y(y) {}
        Point& operator+=(const Point& v){ x += v.x; y+= v.y; return *this;}
        Point operator+(const Point& v) const{return Point(*this) += v;}
        Point& operator-=(const Point& v){x -= v.x; y-= v.y; return *this;}
        Point operator-(const Point& v) const{return Point(*this) -= v;}
        Point& operator*=(double s){x *= s; y *= s; return *this;}
        Point operator*(double s) const{return Point(*this) *= s;}
        Point& operator/=(double s){x /= s; y /= s; return *this;}
        Point operator/(double s) const{return Point(*this) /= s;}
        double dot(const Point& v) const {return x*v.x + y*v.y;}        /* 内積 */
        double cross(const Point& v) const {return x*v.y - v.x*y;}      /* 外積 */
        double norm2() const {return x*x + y*y;}                        /* ノルムの二乗*/
        double norm() const {return sqrt(norm2());}                     /* ノルム */
        int quadrant() const { if(y > 0) return x>0 ? 1:2; else return x>0 ? 4:3;} /* 象限判定 */
        Point rot(double theta) {return Point(cos(theta) * x - sin(theta) * y, sin(theta) * x + cos(theta) * y);} // 回転
        Point rot90() {return Point(-y, x);} // 90度回転
    };

    ostream& operator<<(ostream& os, const Point& v) {os<<"("<<v.x<<","<<v.y<<")"; return os;}
    istream& operator>>(istream& is, Point& v){ is >> v.x >> v.y; return is;}

    // 点a, b, cからなる三角形の面積
    double calc_triangle_area(Point a, Point b, Point c) {
        Point v1 = b - a;
        Point v2 = c - a;
        return abs(v1.cross(v2)) / 2;
    }

    // 点a, bを通る直線と点cとの距離
    double calc_distance_between_point_and_line(Point a, Point b, Point c) {
        return abs((b-a).cross(c-a)) / (b-a).norm();
    }

    // 点a, bを端点とする線分と点cとの距離
    double calc_distance_between_point_and_segment(Point a, Point b, Point c) {
        if ((b-a).dot(c-a) < eps) return (c-a).norm();
        if ((a-b).dot(c-b) < eps) return (c-b).norm();
        return calc_distance_between_point_and_line(a, b, c);
    }

    // 点a, bを端点とする線分と点cと点dを端点とする線分の距離
    double calc_distance_between_segments(Point a, Point b, Point c, Point d) {
        double d0 = calc_distance_between_point_and_segment(a, b, c);
        double d1 = calc_distance_between_point_and_segment(a, b, d);
        double d2 = calc_distance_between_point_and_segment(c, d, a);
        double d3 = calc_distance_between_point_and_segment(c, d, b);
        return min(min(d0, d1), min(d2, d3));
    }

    enum RELATION_BETWEEN_SEGMENT_AND_POINT {
        COUNTER_CLOCKWISE = 1,     // p1とp2のp0を挟んだ位置関係が反時計回り
        CLOCKWISE = -1,            // 時計回り
        ONLINE_BACK = 2,           // p1とp2がp0を挟んで直線状にある
        ONLINE_FRONT = -2,         // p0とp2の間にp1がある
        ON_SEGMENT = 0,            // p0とp1の間にp2がある
    };

    // 点cが点a, bを端点とする線分のどちら側にあるか、enumで返す
    RELATION_BETWEEN_SEGMENT_AND_POINT ccw_ex(Point p0, Point p1, Point p2) {
        Point v1 = p1 - p0;
        Point v2 = p2 - p0;
        if(v1.cross(v2) > eps) return COUNTER_CLOCKWISE;    // 1
        if(v1.cross(v2) < -eps) return CLOCKWISE;           // -1
        if(v1.dot(v2) < -eps) return ONLINE_BACK;           // 2
        if(v1.norm() < v2.norm()) return ONLINE_FRONT;      // -2
        return ON_SEGMENT;                                  // 0
    }

    // 点cが点a, bを端点とする線分のどちら側にあるか
    int ccw(Point p0, Point p1, Point p2) {
        Point v1 = p1 - p0;
        Point v2 = p2 - p0;
        if(v1.cross(v2) > eps) return 1;
        if(v1.cross(v2) < -eps) return -1;
        return 0;
    }

    // p1,p2を端点とする線分Aとp3,p4を端点とする線分Bの交差判定
    // include_end=trueなら端点が重なっていても交差しているとみなす
    bool intersect(Point p1, Point p2, Point p3, Point p4, bool include_end=true) {

        bool is_otherside;
        bool is_inside;

        if (include_end){
            is_otherside = ccw(p1,p2,p3) * ccw(p1,p2,p4) <= 0; // Aの両側にBの端点があるかどうか。どちらかがAの直線状にいてもOK
            is_inside = ccw(p3,p4,p1) * ccw(p3,p4,p2) <= 0;    // Aの端点の内側にBがいるかどうか。
        } else {
            is_otherside = ccw(p1,p2,p3) * ccw(p1,p2,p4) < 0; // Aの両側にBの端点があるかどうか
            is_inside = ccw(p3,p4,p1) * ccw(p3,p4,p2) < 0;    // Aの端点の内側にBがいるかどうか
        }
        return is_otherside && is_inside;
    }


    // 円
    struct Circle {
        Point c;
        double r;
        Circle(){}
        Circle(Point c, double r):c(c),r(r){}

        // 円が点pを含むかどうか　include_circumは円周上を含むとするかどうか
        bool does_include_point(Point p, bool include_circum = true){
            double d = (p - c).norm();
            if (include_circum){
                return d < r + eps;
            } else {
                return d < r - eps;
            }
        }
    };

    // 点p1, p2を通る半径rの円を返す
    vector<Circle> calc_circle_on_two_points(Point p1, Point p2, double r){

        Point p12_half = (p2 - p1) / 2.0;

        double n_vec_norm2 = r*r - p12_half.norm2();
        if (n_vec_norm2 < 0) return vector<Circle>();

        double n_vec_norm = sqrt(n_vec_norm2);
        Point n_vec = p12_half.rot90() * n_vec_norm / p12_half.norm();

        vector<Circle> ret;
        ret.emplace_back(p1 + p12_half + n_vec, 1.0);
        ret.emplace_back(p1 + p12_half - n_vec, 1.0);
        return ret;
    }
}


int main(){
#ifdef LOCAL
    ifstream in("../in.txt"); cin.rdbuf(in.rdbuf());
#endif
    using namespace Geom;

    while(1){
        int n, m;
        cin >> n >> m;
        if(n == 0 && m == 0){
            break;
        }

        vector<int> ans(n, 0);
        double time;

        vector<Point> d_pos(n);
        vector<Point> d_dst(n);
        vector<double> d_speed(n);

        vector<Point> f_pos(m);
        vector<Point> f_dst(m);
                
        REP(i, n) cin >> d_pos[i] >> d_speed[i];
        REP(i, m) cin >> f_pos[i] >> f_dst[i];

        for(int i=0; i<m; i++){
            double min_t = INF;
            int min_dog = n;

            time = INF;

            /* 最小の時間を求める */
            for(int j=0; j<n; j++){
                double ds = d_speed[j];
                Point dd = f_pos[i] - d_pos[j];
                double a = f_dst[i].norm2() - ds*ds;
                double b = 2 * dd.dot(f_dst[i]);
                double c = dd.norm2();
                if(abs(a) < eps){
                    time = -c/b;
                    if(time < 0) time = INF;
                    //print("asdf");
                } else {
                    double D = b*b - 4*a*c;
                    if(D < 0) {
                        time = INF;
                    }else{
                        double ans_t1 = (-b + sqrt(D)) / (2*a);
                        double ans_t2 = (-b - sqrt(D)) / (2*a);
                        if(ans_t1 < 0) ans_t1 = INF;
                        if(ans_t2 < 0) ans_t2 = INF;
                        time = min(ans_t1, ans_t2);                    
                    }
                }


                if(time < min_t){
                    min_t = time;
                    min_dog = j;
                }

                d_dst[j] = (f_pos[i] + f_dst[i] * time - d_pos[j]) / time; 
                if(time == INF) d_dst[j] = Point(0, 0);
            }

            /* 犬の座標を更新する */
            for(int j=0; j<n; j++){
                d_pos[j] += d_dst[j] * min_t;
            }

            ans[min_dog]++;
        }

        for(int i=0; i<n-1; i++){
            cout << ans[i] <<" ";
        }
        print(ans[n-1]);
    }

    return 0;
}