该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

小雨暴打小怪兽

时间限制：2s

空间限制：256MB

题目描述

小雨又在玩电脑游戏（为什么是又？）。猜猜他在干什么？没错，杀怪。

有 $n$ 个怪物，编号从 $1$ 到 $n$，其中第 $i$ 个怪物有两个参数：攻击值 $a_i$ 和防御值 $d_i$。为了杀死这些怪物，小雨给他们施加了咒语，因此它们会互相攻击。

战斗由 $n$ 个回合组成，每回合会发生以下事件：

• 首先，每只怪物会对自己左侧的第一只与右侧的第一只存活的怪物（如果存在）造成 $a_i$​ 的伤害。
• 所有攻击结束后，若一只怪物在本轮中受到的伤害总和大于 $d_i$ 它就会退场。

小雨想知道，每一轮有多少怪物会退场。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示数据组数。

每组数据包含以下三行：

• 第一行一个整数 $n$，表示怪物的数量。
• 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示怪物的攻击值。
• 第三行 $n$ 个整数 $d_1,d_2,\cdots,d_n$，表示怪物的防御值。

输出格式

对于每组数据，输出一行 $n$ 个数。第 $i$ 个数表示第 $i$​ 回合退场的怪物数量。

样例 #1

样例输入 #1

3
5
3 4 7 5 10
4 9 1 18 1
2
2 1
1 3
4
1 1 2 4
3 3 4 2

样例输出 #1

3 1 0 0 0 
0 0 
1 1 1 0

数据范围

对于所有数据，满足 $1 \le T \le 10^4$，$1\le\sum n\le 3\times 10^5$，$1\le a_i,d_i\le 10^9$。

提示

对于第一组样例：

第一回合，发生了以下事情：

• 怪物 $1$ 对怪物 $2$ 造成 $3$ 点伤害。
• 怪物 $2$ 对怪物 $1$ 和怪物 $3$ 造成 $4$​ 点伤害。
• 怪物 $3$ 对怪物 $2$ 和怪物 $4$ 造成 $7$​ 点伤害。
• 怪物 $4$ 对怪物 $3$ 和怪物 $5$ 造成 $5$​ 点伤害。
• 怪物 $5$ 对怪物 $4$ 造成 $10$​ 点伤害。
• 怪物 $1$ 共受到 $4$ 点伤害，其防御值为 $4$​，存活。
• 怪物 $2$ 共受到 $10$ 点伤害，其防御值为 $9$，死亡。
• 怪物 $3$ 共受到 $9$ 点伤害，其防御值为 $1$，死亡。
• 怪物 $4$ 共受到 $17$ 点伤害，其防御值为 $18$，存活。
• 怪物 $5$ 共受到 $5$ 点伤害，其防御值为 $1$，死亡。

第二回合，发生了以下事情：

• 怪物 $1$ 对怪物 $4$ 造成 $3$ 点伤害。
• 怪物 $4$ 对怪物 $1$ 造成 $5$​ 点伤害。
• 怪物 $1$ 共受到 $5$ 点伤害，其防御值为 $4$，死亡。
• 怪物 $4$ 共受到 $3$ 点伤害，其防御值为 $18$​，存活。

剩余回合无事发生。