Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Остаться в живых
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В компьютерной игре есть $$$n$$$ героев. У каждого героя есть здоровье $$$h$$$ и изначальная броня $$$a$$$. Пусть текущее количество брони равно $$$a_{\mathit{cur}}$$$, изначально равное $$$a$$$.

Когда герою наносится $$$x$$$ урона, происходит следующее: если $$$x < a_{\mathit{cur}}$$$, то из $$$a_{\mathit{cur}}$$$ вычитается $$$x$$$; иначе из $$$h$$$ вычитается $$$1$$$, а $$$a_{\mathit{cur}}$$$ снова становится равно $$$a$$$.

В начале игры вы выбираете значение $$$x$$$ (целое число, строго большее $$$0$$$). Затем вы атакуете героев, пока все не погибнут: за один раунд вы наносите $$$x$$$ урона каждому живому герою. Герой погибает, когда его здоровье становится равно $$$0$$$. Игра заканчивается, когда все герои погибают.

Последний погибший герой получает количество очков, равное количеству раундов, в течение которых он был единственным живым героем. Остальные герои получают $$$0$$$ очков. В частности, если в последнем раунде погибают несколько героев, то все герои получают $$$0$$$ очков.

Вы сыграли по одной игре на каждое возможное значение $$$x$$$ (от $$$1$$$ до бесконечности). Между играми очки сбрасывались. Какое наибольшее количество очков было у каждого героя?

Входные данные

В первой строке записано одно целое число $$$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$$$) — изначальное количество брони каждого героя.

Выходные данные

На каждый набор входных данных выведите $$$n$$$ целых чисел — максимальное количество очков, которое было у героя в течение игр, сыгранных для каждого возможного $$$x$$$.

Пример
Входные данные
3
3
3 1 2
3 11 5
1
100
200
4
5 9 5 1
9 2 9 10
Выходные данные
1 1 1 
20000 
0 4 0 0
Примечание

В первом наборе входных данных игра на $$$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$$$: у первого героя заканчивается броня, поэтому он теряет очко здоровья: $$$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]$$$;

Третий герой погиб последним, и был единственным живым героев в течение одного раунда.