310747: CF1879F. Last Man Standing

F. Last Man Standingtime limit per test7 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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 < 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?

Input

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.

Output

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

ExampleInput

3
3
3 1 2
3 11 5
1
100
200
4
5 9 5 1
9 2 9 10

Output

1 1 1 
20000 
0 4 0 0 

Note

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.

题目大意：在游戏中，有n个英雄，每个英雄有健康值h和初始护甲值a。你选择一个值x（一个大于0的整数，可以任意大），然后每轮攻击所有存活的英雄，造成x点伤害。当一个英雄的健康值变为0时，他就死了。当所有英雄都死了，游戏结束。最后一个死去的英雄获得与他唯一存活的那轮游戏数量相等的分数。对于每个可能的x（从1到无穷大），计算每个英雄可能获得的最大分数。

输入数据格式：第一行包含一个整数t（1≤t≤10），表示测试用例的数量。每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示英雄的数量。第二行包含n个整数h1,h2,…,hn（1≤hi≤2×10^5），表示每个英雄的健康值。第三行包含n个整数a1,a2,…,an（1≤ai≤2×10^5），表示每个英雄的初始护甲值。

输出数据格式：对于每个测试用例，输出n个整数，表示每个英雄在所有可能的游戏中可能获得的最大分数。题目大意：在游戏中，有n个英雄，每个英雄有健康值h和初始护甲值a。你选择一个值x（一个大于0的整数，可以任意大），然后每轮攻击所有存活的英雄，造成x点伤害。当一个英雄的健康值变为0时，他就死了。当所有英雄都死了，游戏结束。最后一个死去的英雄获得与他唯一存活的那轮游戏数量相等的分数。对于每个可能的x（从1到无穷大），计算每个英雄可能获得的最大分数。 输入数据格式：第一行包含一个整数t（1≤t≤10），表示测试用例的数量。每个测试用例的第一行包含一个整数n（1≤n≤2×10^5），表示英雄的数量。第二行包含n个整数h1,h2,…,hn（1≤hi≤2×10^5），表示每个英雄的健康值。第三行包含n个整数a1,a2,…,an（1≤ai≤2×10^5），表示每个英雄的初始护甲值。 输出数据格式：对于每个测试用例，输出n个整数，表示每个英雄在所有可能的游戏中可能获得的最大分数。