Monocarp 正在玩电脑游戏(再次)。猜猜他在做什么?没错,就是杀怪。
一排有$$$n$$$个怪物,编号从$$$1$$$到$$$n$$$。第 $$$i$$$ 个怪物有两个参数:攻击值等于 $$$a_i$$$,防御值等于 $$$d_i$$$。为了杀死这些怪物,Monocarp 对它们施加了狂暴咒语,所以它们会互相攻击,而不是 Monocarp 的角色。
战斗由 $$$n$$$ 轮组成。每一轮都会发生以下情况:
- 首先,每个活着的怪物 $$$i$$$ 对左边最近的活着的怪物(如果存在)和右边最近的活着的怪物(如果存在)造成 $$$a_i$$$ 伤害;
- 然后,每一个在本轮中受到超过 $$$d_j$$$ 伤害的活着的怪物 $$$j$$$ 都会死亡。 IE。当且仅当其防御值 $$$d_j$$$ 严格小于其本轮受到的总伤害时,第 $$$j$$$ 个怪物才会死亡。
每轮计算该轮期间死亡的怪物数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由三行组成:
- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);
- 第三行包含 $$$n$$$ 整数 $$$d_1, d_2, \dots, d_n$$$ ($$$1 \le d_i \le 10^9$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数。第 $$$i$$$ 整数应等于第 $$$i$$$ 轮中死亡的怪物数量。
示例
输入 #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$$$对怪物$$$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$$$还活着。
在第二轮中,会发生以下情况:
- 怪物$$$1$$$对怪物$$$4$$$造成$$$3$$$伤害;
- 怪物$$$4$$$对怪物$$$1$$$造成$$$5$$$伤害;
- 怪物 $$$1$$$ 死亡,因为它受到 $$$5$$$ 伤害,防御力为 $$$4$$$;
- 怪物 $$$4$$$ 不会死亡,因为它受到了 $$$3$$$ 伤害,防御力为 $$$18$$$。
在接下来的三轮中,只有第$$$4$$$个怪物还活着,所以什么也没有发生。