题目描述

You are studying the history of the Great Wall of China, which was built by the Chinese to protect against military incursions from the North. For the purposes of this problem, the Great Wall stretches from infinity in the East to minus infinity in the West. As this is a lot of distance to cover, the Great Wall was not built at once. Instead, for this problem we assume that the builder used a reactive strategy: whenever a part of the border was attacked successfully, the Wall on this part of the border would be raised to the height sufficient to stop an identical attack in the future.

The north border of China was frequently attacked by nomadic tribes. For the purposes of this problem, we assume that each tribe attacks the border on some interval with some strength $S$. In order to repel the attack, the Wall must have height $S$ all along the defended interval. If even a short stretch of the Wall is lower than needed, the attack will breach the Wall at this point and succeed. Note that even a successful attack does not damage the Wall. After the attack, every attacked fragment of the Wall that was lower than $S$ is raised to height $S$ — in other words, the Wall is increased in the minimal way that would have stopped the attack. Note that if two or more attacks happened on the exact same day, the Wall was raised only after they all resolved, and is raised in the minimum way that would stop all of them.

Since nomadic tribes are nomadic, they did not necessarily restrict themselves to a single attack. Instead, they tended to move (either to the East or to the West), and periodically attack the Wall. To simplify the problem, we assume they moved with constant speed and attacked the Wall at constant intervals; moreover we assume that the strength with which a given tribe attacked the Wall changed by a constant amount after each attack (either decreased from attrition, or grew from experience).

Assuming that initially (in 250 BC) the Wall was nonexistent (i.e., of height zero everywhere), and given the full description of all the nomadic tribes that attacked the Wall, determine how many of the attacks were successful.

输入格式

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line containing a single integer $N$: the number of the tribes attacking the Wall. $N$ lines follow, each describing one tribe. The $i$th line contains eight integers $d_i$, $n_i$, $w_i$, $e_i$, $s_i$, $\text{delta\_d}_i$, $\text{delta\_p}_i$ and $\text{delta\_s}_i$ separated by spaces, describing a single nomadic tribe:

• $d_i$ – the day of the tribe's first attack (where 1st January, 250BC, is considered day 0)
• $n_i$ – the number of attacks from this tribe
• $w_i$, $e_i$ – the westmost and eastmost points respectively of the Wall attacked on the first attack
• $s_i$ – the strength of the first attack
• $\text{delta\_d}_i$ – the number of days between subsequent attacks by this tribe
• $\text{delta\_p}_i$ – the distance this tribe travels to the east between subsequent attacks (if this is negative, the tribe travels to the west)
• $\text{delta\_s}_i$ – the change in strength between subsequent attacks

输出格式

For each test case, output one line containing "Case #x: y", where $x$ is the case number (starting from 1) and $y$ is the number of attacks that succeed.

2
2
0 3 0 2 10 2 3 -2
10 3 2 3 8 7 2 0
3
1 2 0 5 10 2 8 0
0 3 0 1 7 1 2 2
3 3 0 5 1 1 4 0

Case #1: 5
Case #2: 6

提示

Sample Explanation

In the first case, the first tribe attacks three times: on day $0$ it hits the interval $[0,2]$ at height $10$, on day $2$ it hits $[3,5]$ at height $8$ and on day $4$ it hits $[6,8]$ at height $6$; all three attacks succeed. Then the second tribe attacks three times, each time at height $8$ - on day $10$ it hits $[2,3]$ (this succeeds, for example at position $2.5$, where the Wall has still height $0$), on day $17$ it hits $[4,5]$ (this fails, the Wall is already of height $8$ in the interval $[3, 5]$, which covers $[4, 5]$), and on day $24$ it hits $[6,7]$ (this succeeds, as the Wall there was of height $6$).

In the second case there are three tribes, and their attacks intermingle. The sequence is as follows:

• On day $0$, Tribe $2$ attacks $[0,1]$ at height $7$ and succeeds.
• On day $1$, Tribe $1$ attacks $[0,5]$ at height $10$, and Tribe $2$ attacks $[2,3]$ at height $9$. Both attacks succeed (as they were simultaneous, the Wall built after the attack of the first tribe isn't there in time to stop the second tribe).
• On day $2$, Tribe $2$ attacks $[4,5]$ at height $11$ and succeeds (the Wall there was at height $10$).
• On day $3$, Tribe $1$ attacks $[8,13]$ at height $10$ and succeeds. Simultaneously, Tribe $3$ attacks $[0,5]$ at height $1$ and fails (there's a Wall of heights $10$ and $11$ there).
• On day $4$ Tribe $3$ attacks $[4,9]$ at height $1$ and succeeds (there was no Wall between $5$ and $8$).
• Finally, on day $5$ Tribe $3$ attacks $[8,13]$ at height $1$ and fails (since a Wall of height $10$ is there).

Limits

• $1 \leq T \leq 20$.
• $0 \leq d_i$.
• $1 \leq \text{delta\_d}_i \leq 676060$.
• $d_i + (n_i - 1) \times \text{delta\_d}_i \leq 676060$.
• $1 \leq s_i \leq 10^6$.
• $-10^5 \leq \text{delta\_s}_i \leq 10^5$.
• $s_i + (n_i - 1) \times \text{delta\_s}_i \geq 1$.

Small dataset (9 Pts, Test set 1 - Visible)

• $1 \leq N \leq 10$.
• $1 \leq n_i \leq 10$.
• $-100 \leq w_i < e_i \leq 100$.
• $-10 \leq \text{delta\_p}_i \leq 10$.

Large dataset (28 Pts, Test set 2 - Hidden)

• $1 \leq N \leq 1000$.
• $1 \leq n_i \leq 1000$.
• $-10^6 \leq w_i < e_i \leq 10^6$.
• $-10^5 \leq \text{delta\_p}_i \leq 10^5$.