Description

Xiao K likes playing rhythm games, especially one called dimou. The judgment system of dimou works like this: dimou is a single-sided falling rhythm game (unlike something starting with “dy”). Specifically, there is a judgment line at the bottom of the screen. A song has several hit objects (called keys; you can think of each as a line segment parallel to the judgment line, with only left-right width). Each key falls from the top at a constant speed at some time, and the player needs to click it as accurately as possible when it overlaps the judgment line.

Of course, the player may click before a key touches the judgment line, or click only after the key has already fallen below the judgment line. In that case, we need to consider the game’s judgment system to count how the player finishes the song. dimou has three judgments: perfect, good, and miss. There are six cases in total.

Case $1$: If the click time is $1s$ or more before the time when some key falls to overlap the judgment line (denote this as $\triangle t\ge1$, same below), then no judgment effect is produced (equivalent to a meaningless click).

Case $2$: If $0.6\le\triangle t<1$, then this key produces one miss judgment and disappears.

Case $3$: If $0.2\le\triangle t<0.6$, then this key produces one good judgment and disappears.

Case $4$: If $-0.2<\triangle t<0.2$ (a negative value means clicking after the key reaches the judgment line), then this key produces one perfect judgment and disappears.

Case $5$: If $-0.6<\triangle t\le-0.2$, then this key produces one good judgment and disappears.

Case $6$: If $\triangle t\le-0.6$, then this key will have already fallen out of the screen before the click, counting as one miss judgment and disappearing (that is, it produces one miss judgment by itself after it has been below the judgment line for $0.6s$). Clicking has no judgment effect on this key.

In addition, dimou has a maximum combo statistic (max combo). A combo segment is the total number of judgments from some non-miss judgment to some non-miss judgment (within this interval, in time order, there is no miss judgment). max combo is the maximum value among all combos.

Besides, dimou has some additional rules. The position of a click can be considered as a point on the judgment line. Draw the perpendicular line to the judgment line through this point; only keys that intersect this perpendicular line (the intersection may be at an endpoint) may produce a judgment effect due to this click. Moreover, each click only produces a judgment effect on the one key among those that may produce an effect whose position (vertical height) is the lowest (farthest from the top of the screen). Intuitively, you can only remove a key by clicking somewhere below it, and if two keys fall together with some vertical distance between them, then if a click can remove the lower key, it will definitely not remove the upper key. Specially, if one click may produce a judgment effect on two or more keys with the same position (height), and there is no lower key that may produce a judgment effect, then all these keys will be removed.

To play a song well, Xiao K decides to memorize the chart, i.e., remember the position of every key and the time when it falls to the judgment line. Of course, Xiao K will also decide his play plan in advance, i.e., decide at what time and at what position to click. But Xiao K cannot compute the final score his plan will get. Please help Xiao K calculate how many perfect judgments, how many good judgments, how many miss judgments, and the max combo he will obtain.

Note: Xiao K will not click two or more times at the same time. If there are multiple judgments at the same time, process them in the order miss, good, perfect.

Input Format

The first line contains two positive integers $n,m$, representing the number of keys and the number of clicks by Xiao K.

Then follow $n$ lines, each containing three floating-point numbers (with at most $5$ digits after the decimal point) $t_i,a_i,b_i$, representing, for each key, the time from the start of the song to when it reaches the judgment line, its left endpoint position, and its right endpoint position.

Then follow $m$ lines, each containing two floating-point numbers (with at most $5$ digits after the decimal point) $T_i,x_i$, representing the time from the start of the song for each click and its position.

Output Format

Output one line with four non-negative integers, separated pairwise by a single space, representing the number of perfect, the number of good, the number of miss, and the max combo.

5 6
1 0.0 10.0
1.5 0.0 10.0
2.0 0.0 10.0
2.5 0.0 10.0
3.0 0.0 10.0
0.0 5.0
0.4 5.0
1.3 5.0
2.0 5.0
2.7 5.0
3.6 5.0

1 2 2 3

4 2
0.1 0.0 3.0
0.1 2.0 4.0
0.0 3.0 8.0
0.6 1.0 6.0
0.6 6.0
0.0 2.5

3 0 1 2

Hint

Sample $3$: input, output.

Sample $4$: input, output.

[Sample Explanation]

For sample $1$: The judgments produced by the $5$ keys, in time order, are miss, good, perfect, good, miss. The first and the last click do not produce any judgment effect.

For sample $2$: In time order, for the first click ($T=0.0$), the keys that may produce a judgment effect are keys $1,2,4$ (in input order). Keys $1,2$ reach the judgment line at the same time, and key $4$ is higher than keys $1,2$. Therefore, the first click only makes keys $1,2$ produce perfect judgments. For the second click ($T=0.6$), the keys intersecting its perpendicular line are keys $3,4$, but key $3$ has already produced a miss judgment and disappeared, so this click makes key $4$ produce one perfect judgment. At this time, there are two judgments at the same time: perfect and miss. According to the rule, process miss before perfect. Therefore, all judgments in time order are perfect, perfect, miss, perfect. It is easy to see that the miss splits the judgment sequence into two segments: the first segment has a combo of $2$, the second segment has a combo of $1$, so max combo is $2$.

[Constraints]

For $30\%$ of the data, $n,m\le5000$.

For another $20\%$ of the data, $n\le5000$, $m\le114514$.

For another $10\%$ of the data, all $a_i$ are equal, and all $b_i$ are equal.

For another $10\%$ of the data, $t_i,T_i,a_i,b_i,x_i$ are randomly generated in $[0,10^4]$.

For $100\%$ of the data, $1\le n,m\le114514$, $0\le t_i,T_i,a_i,b_i,x_i\le 10^4$, and $a_i\le b_i$.

Translated by ChatGPT 5