2471: Seeing People

There are two kinds of people.

If person i is the first kind of people, it locates at position (pi, 0) initially, starts moving at time ti with a constant velocity of (0, v1), and then sees every person sits at the line segment (xi, yi), (xi + wi, yi), include the two points, where (xi, yi) is the position of person i at that time and wi is its vision.

If person i is the second kind of people, it locates at position (0, pi) initially, starts moving at time ti with a constant velocity of (v2, 0), and then sees every person sits at the line segment (xi, yi), (xi, yi + wi), include the two points, where (xi, yi) is the position of person i at that time and wi is its vision.

Now given the position of people, please calculate the number of distinct people every person has finally seen.

There are multiply test cases.

The first line contains an integer T(T<=10), indicates the number of cases.

For each test case, the first line contains three integers n, v1, v2(1<=n,v1,v2<=10^5), indicating the total number of two kinds of people, the speed of the first kind, and the speed of the second kind.

Then comes N lines, the i-th line contains four integers ai, ti, pi, wi (1<=ai<=2, 1<=ti,pi,wi<=10^5), describing a person, where ai is the type, ti is time the person starts moving, pi is the location and wi is the vision.

It is granted that for the same kind of people, all ti, pi are different.

For each case, you should output "Case #k:" first, where k indicates the case number and counts from 1.

Then output N lines, each lines is an integer, indicates the number of distinct people the i-th person finally recorded.

1
2 1 1
1 1 1 1
2 2 2 1

Case #1:
1
1