#P1412. 小雨暴打小怪兽

小雨暴打小怪兽

小雨暴打小怪兽

时间限制:2s

空间限制:256MB

题目描述

小雨又在玩电脑游戏(为什么是又?)。猜猜他在干什么?没错,杀怪。

nn 个怪物,编号从 11nn,其中第 ii 个怪物有两个参数:攻击值 aia_i 和防御值 did_i。为了杀死这些怪物,小雨给他们施加了咒语,因此它们会互相攻击。

战斗由 nn 个回合组成,每回合会发生以下事件:

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

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

输入格式

本题有多组测试数据。

第一行一个整数 TT,表示数据组数。

每组数据包含以下三行:

  • 第一行一个整数 nn,表示怪物的数量。
  • 第二行 nn 个整数 a1,a2,,ana_1,a_2,\cdots,a_n,表示怪物的攻击值。
  • 第三行 nn 个整数 d1,d2,,dnd_1,d_2,\cdots,d_n,表示怪物的防御值。

输出格式

对于每组数据,输出一行 nn 个数。第 ii 个数表示第 ii​ 回合退场的怪物数量。

样例 #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

数据范围

对于所有数据,满足 1T1041 \le T \le 10^41n3×1051\le\sum n\le 3\times 10^51ai,di1091\le a_i,d_i\le 10^9

提示

对于第一组样例:

第一回合,发生了以下事情:

  • 怪物 11 对怪物 22 造成 33 点伤害。
  • 怪物 22 对怪物 11 和怪物 33 造成 44​ 点伤害。
  • 怪物 33 对怪物 22 和怪物 44 造成 77​ 点伤害。
  • 怪物 44 对怪物 33 和怪物 55 造成 55​ 点伤害。
  • 怪物 55 对怪物 44 造成 1010​ 点伤害。
  • 怪物 11 共受到 44 点伤害,其防御值为 44​,存活。
  • 怪物 22 共受到 1010 点伤害,其防御值为 99,死亡。
  • 怪物 33 共受到 99 点伤害,其防御值为 11,死亡。
  • 怪物 44 共受到 1717 点伤害,其防御值为 1818,存活。
  • 怪物 55 共受到 55 点伤害,其防御值为 11,死亡。

第二回合,发生了以下事情:

  • 怪物 11 对怪物 44 造成 33 点伤害。
  • 怪物 44 对怪物 11 造成 55​ 点伤害。
  • 怪物 11 共受到 55 点伤害,其防御值为 44,死亡。
  • 怪物 44 共受到 33 点伤害,其防御值为 1818​,存活。

剩余回合无事发生。