В компьютерной игре есть $$$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$$$.
333 1 23 11 5110020045 9 5 19 2 9 10
1 1 1 20000 0 4 0 0
В первом наборе входных данных игра на $$$x = 1$$$ играется так:
Второй герой погиб последним, и был единственным живым героев в течение одного раунда. Поэтому он получает $$$1$$$ очко за эту игру.
Игра на $$$x = 4$$$ играется так:
Третий герой погиб последним, и был единственным живым героев в течение одного раунда.
Название |
---|