CF1879F.Last Man Standing

There are $n$ heroes in a videogame. Each hero has some health value $h$ and initial armor value $a$. Let the current value of armor be $a_{\mathit{cur}}$, initially equal to $a$.

When $x$ points of damage are inflicted on a hero, the following happens: if $x \lt a_{\mathit{cur}}$, then $x$ gets subtracted from $a_{\mathit{cur}}$; otherwise, $1$ gets subtracted from $h$ and $a_{\mathit{cur}}$ gets assigned back to $a$.

In the start of the game, you choose the value $x$ (an integer strictly greater than $0$, arbitrarily large). Then you keep attacking all heroes in rounds: in one round, you inflict $x$ points of damage to all alive heroes. A hero dies when his health becomes $0$. The game ends when all heroes are dead.

The last hero to die earns the number of points, equal to the number of rounds he was the only hero alive. The other heroes get $0$ points. In particular, if the last round ends with multiple heroes dying, then every hero gets $0$ points.

The game is played for every possible $x$ (from $1$ to infinity). The points are reset between the games. What's the maximum number of points each hero has had?

游戏中有 $n$ 位英雄。每位英雄具有一个生命值 $h$ 和一个初始护甲值 $a$。令当前护甲值为 $a_{\mathit{cur}}$，其初始值等于 $a$。

当对某位英雄造成 $x$ 点伤害时，发生如下过程：若 $x \lt a_{\mathit{cur}}$，则从 $a_{\mathit{cur}}$ 中减去 $x$；否则，该英雄的生命值 $h$ 减少 $1$，且 $a_{\mathit{cur}}$ 被重置为 $a$。

游戏开始时，你需要选定一个值 $x$（$x$ 为严格大于 $0$ 的整数，可任意大）。随后你按轮次持续攻击所有存活的英雄：每轮中，你对所有当前存活的英雄各造成 $x$ 点伤害。当一位英雄的生命值变为 $0$ 时，他即死亡。当所有英雄均死亡时，游戏结束。

最后一位死亡的英雄获得积分，积分数值等于他在整场游戏中“唯一存活的英雄”所持续的轮数。其余英雄获得 $0$ 积分。特别地，若最后一轮中有多个英雄同时死亡，则所有英雄均获得 $0$ 积分。

游戏将对每个可能的 $x$ 值（从 $1$ 到无穷大）分别进行。不同 $x$ 值对应的游戏之间积分相互独立、互不干扰。问：每位英雄在其所有游戏中曾获得过的最高积分是多少？

The first line contains a single integer $t$ ($1 \le t \le 10$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of heroes.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 2 \cdot 10^5$) — the health value of each hero.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — the initial armor value of each hero.

第一行包含一个整数 $t$（$1 \le t \le 10$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 英雄的数量。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$（$1 \le h_i \le 2 \cdot 10^5$）—— 每位英雄的生命值。

第三行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^5$）—— 每位英雄的初始护甲值。

For each testcase, print $n$ integers — the maximum number of points each hero has had over the games played for every possible $x$.

对于每个测试用例，输出 $n$ 个整数——即对每个可能的 $x$，每位英雄在已进行的游戏中所获得的最大分数。

In the first testcase, the game for $x = 1$ is played as follows:

• before all rounds: the heroes have $h = [3, 1, 2]$, $a_{\mathit{cur}} = [3, 11, 5]$;
• round $1$: $1$ damage is inflicted on every hero: $h$ remains $[3, 1, 2]$, $a_{\mathit{cur}}$ becomes $[2, 10, 4]$;
• round $2$: $h = [3, 1, 2]$, $a_{\mathit{cur}} = [1, 9, 3]$;
• round $3$: the first hero runs out of armor, so he loses a health point: $h = [2, 1, 2]$, $a_{\mathit{cur}} = [3, 8, 2]$;
• ...
• round $9$: the first hero dies, since his health reaches $0$: $h = [0, 1, 1]$, $a_{\mathit{cur}} = [0, 2, 1]$;
• round $10$: the third hero dies: $h = [0, 1, 0]$, $a_{\mathit{cur}} = [0, 1, 0]$;
• round $11$: the second hero dies: $h = [0, 0, 0]$, $a_{\mathit{cur}} = [0, 0, 0]$.

The second hero was the last hero to die, and he was the only hero alive during one round. Thus, he gets $1$ point for that game.

The game for $x = 4$ is played as follows:

• round $1$: $h = [2, 1, 2]$, $a_{\mathit{cur}} = [3, 7, 1]$;
• round $2$: $h = [1, 1, 1]$, $a_{\mathit{cur}} = [3, 3, 5]$;
• round $3$: $h = [0, 0, 1]$, $a_{\mathit{cur}} = [0, 0, 1]$;
• round $4$: $h = [0, 0, 0]$, $a_{\mathit{cur}} = [0, 0, 0]$;

The third hero was the last hero to die, and he was the only hero alive during one round.

在第一个测试用例中，当 $x = 1$ 时的游戏过程如下：

• 所有轮次开始前：英雄的生命值为 $h = [3, 1, 2]$，当前护甲值为 $a_{\mathit{cur}} = [3, 11, 5]$；
• 第 $1$ 轮：每位英雄受到 $1$ 点伤害：$h$ 仍为 $[3, 1, 2]$，$a_{\mathit{cur}}$ 变为 $[2, 10, 4]$；
• 第 $2$ 轮：$h = [3, 1, 2]$，$a_{\mathit{cur}} = [1, 9, 3]$；
• 第 $3$ 轮：第一位英雄护甲耗尽，因此损失 $1$ 点生命值：$h = [2, 1, 2]$，$a_{\mathit{cur}} = [3, 8, 2]$；
• …
• 第 $9$ 轮：第一位英雄死亡（生命值降为 $0$）：$h = [0, 1, 1]$，$a_{\mathit{cur}} = [0, 2, 1]$；
• 第 $10$ 轮：第三位英雄死亡：$h = [0, 1, 0]$，$a_{\mathit{cur}} = [0, 1, 0]$；
• 第 $11$ 轮：第二位英雄死亡：$h = [0, 0, 0]$，$a_{\mathit{cur}} = [0, 0, 0]$。

第二位英雄是最后一位死亡的英雄，且他在某一轮中是场上唯一存活的英雄。因此，他在该局游戏中获得 $1$ 分。

当 $x = 4$ 时的游戏过程如下：

• 第 $1$ 轮：$h = [2, 1, 2]$，$a_{\mathit{cur}} = [3, 7, 1]$；
• 第 $2$ 轮：$h = [1, 1, 1]$，$a_{\mathit{cur}} = [3, 3, 5]$；
• 第 $3$ 轮：$h = [0, 0, 1]$，$a_{\mathit{cur}} = [0, 0, 1]$；
• 第 $4$ 轮：$h = [0, 0, 0]$，$a_{\mathit{cur}} = [0, 0, 0]$；

第三位英雄是最后一位死亡的英雄，且他在某一轮中是场上唯一存活的英雄。