Description

你正在研究中国长城的历史。长城是中国人为防御来自北方的军事入侵而修建的。为了简化问题，我们假设长城从东边的正无穷一直延伸到西边的负无穷。由于需要覆盖的距离太长，长城并不是一次性建成的。本题假设修建者采用了一种“被动应对”的策略：每当某段边境被成功攻破，长城就会在该段加高到足以抵御相同强度攻击的高度。

中国北部边境经常遭到游牧部落的进攻。为简化问题，我们假设每个部落在某个区间内以强度 $S$ 发起攻击。要抵御这次攻击，长城在该区间上必须处处高度不低于 $S$。只要有哪怕一小段低于 $S$，攻击就会在那里突破并成功。注意，即使攻击成功，也不会损坏长城。每次攻击结束后，所有被攻击且高度低于 $S$ 的长城段都会被加高到 $S$——也就是说，长城会以最小的方式加固到足以抵御本次攻击的高度。需要注意的是，如果在同一天有多次攻击，这些攻击都在当天结束后统一加固，且加固到能同时抵御所有当天攻击的最低高度。

由于游牧部落是游牧的，他们不一定只进攻一次。实际上，他们会不断东移或西移，并定期进攻长城。为简化问题，假设他们以恒定速度移动，并以恒定时间间隔发起攻击；此外，假设同一部落每次进攻的强度变化也是恒定的（可能因消耗而减弱，也可能因经验而增强）。

假设最初（公元前 250 年）长城尚未修建（即任意位置高度为 0），并给出所有游牧部落的完整攻击描述，请你求出有多少次攻击是成功的。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例第一行为一个整数 $N$，表示进攻长城的部落数。接下来的 $N$ 行，每行描述一个部落，包含八个整数 $d_i$、$n_i$、$w_i$、$e_i$、$s_i$、$\text{delta\_d}_i$、$\text{delta\_p}_i$ 和 $\text{delta\_s}_i$，含义如下：

• $d_i$ —— 该部落首次攻击的日期（以公元前250年1月1日为第0天）
• $n_i$ —— 该部落的攻击次数
• $w_i$、$e_i$ —— 首次攻击时进攻区间的最西端和最东端
• $s_i$ —— 首次攻击的强度
• $\text{delta\_d}_i$ —— 该部落每次攻击之间的天数
• $\text{delta\_p}_i$ —— 该部落每次攻击后向东（正数）或向西（负数）移动的距离
• $\text{delta\_s}_i$ —— 该部落每次攻击后强度的变化量

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从1开始），$y$ 为成功的攻击次数。

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

Hint

样例说明

在第一个样例中，第一个部落攻击三次：第0天攻击 $[0,2]$，强度为 $10$，第2天攻击 $[3,5]$，强度为 $8$，第4天攻击 $[6,8]$，强度为 $6$；这三次都成功。然后第二个部落攻击三次，每次强度为 $8$——第10天攻击 $[2,3]$（例如在 $2.5$ 处，长城高度仍为 $0$，所以成功），第17天攻击 $[4,5]$（失败，因为 $[3,5]$ 区间长城已经加高到 $8$），第24天攻击 $[6,7]$（成功，因为那里长城高度只有 $6$）。

在第二个样例中，有三个部落，攻击交错进行。顺序如下：

• 第0天，部落2攻击 $[0,1]$，高度 $7$，成功。
• 第1天，部落1攻击 $[0,5]$，高度 $10$，部落2攻击 $[2,3]$，高度 $9$。由于是同一天，这两次都成功（加固是在所有攻击结束后才进行的）。
• 第2天，部落2攻击 $[4,5]$，高度 $11$，成功（那里的长城高度原本为 $10$）。
• 第3天，部落1攻击 $[8,13]$，高度 $10$，成功。同时部落3攻击 $[0,5]$，高度 $1$，失败（该区间长城已有高度 $10$ 和 $11$）。
• 第4天，部落3攻击 $[4,9]$，高度 $1$，成功（$[5,8]$ 区间没有长城）。
• 第5天，部落3攻击 $[8,13]$，高度 $1$，失败（该区间长城高度为 $10$）。

限制条件

• $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$

小数据集（9 分，测试集 1 - 可见）

• $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$

大数据集（28 分，测试集 2 - 隐藏）

• $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$

翻译由 ChatGPT-4.1 完成。